Problem with iteration in linked list structure

Question

I have a problem with my __iter__() implementation for a Linked List structure. I wanted to implement it without using yield and iter().

With one loop it works fine, but when I add a nested loop, the outer loop only iterates once and exits after the inner loop has finished:

class LinkedList:
    class Node:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, seq=None):
        self.head = self.tail = None
        self.extend(seq)
        self.current = self.head

    def __iter__(self):
        return self

    def __next__(self):
        if not self.current:
            raise StopIteration
        else:
            temp = self.current.data
            self.current = self.current.next
            return iter(self.current)

    def extend(self, seq):
        for val in reversed(seq):
            node = self.Node(val, self.head)
            if self.tail is None:
                self.tail = node
            self.head = node

ll = LinkedList(range(10, 101, 10))
for val in ll:
    for val2 in ll:
        print((val, val2))

This produces the wrong output:

(10, 20) (10, 30) (10, 40) (10, 50) (10, 60) (10, 70) (10, 80) (10, 90) (10, 100)

While I expect to also get tuples where the first value is 20, 30, ...etc.

The linked list should return a separate iterator object (of its own class) on `__iter__()`. It must also return a new, independent object on each call. This object (its class) must implement `__next__`. — Michael Butscher, Oct 14 '20 at 16:49
[what-makes-something-iterable-in-python](https://stackoverflow.com/questions/5262235/what-makes-something-iterable-in-python) — Patrick Artner, Oct 14 '20 at 17:21

trincot · Accepted Answer · 2020-10-15T09:29:29.203

The problem with a nested loop like this:

ll = LinkedList([1,2,3,4])
for val in ll:
    for val2 in ll:
        print((val, val2))

...is that for the nested loop, you'll have the same iterator instance, which is the linked list itself, which has just one current property. So when the inner loop has finished, that current will be None, and the outer loop will then call __next__ only to find that current is None. So it exits.

You need to move away from return self in the __iter__ function. Instead you should return something unique every time __iter__ is called.

So define a class specifically for that purpose.

NB: there is also an error in the last line of your __next__ implementation: it should return temp.

class LinkedList:
    class Iterator:
        def __init__(self, current):
            self.current = current

        def __next__(self):
            if not self.current:
                raise StopIteration
            else:
                temp = self.current.data
                self.current = self.current.next
                return temp  # <-- correction

    class Node:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, seq=None):
        self.head = self.tail = None
        self.extend(seq)
        self.current = self.head

    def __iter__(self):
        return self.Iterator(self.head)  # <--- new instance!

    def extend(self, seq):
        for val in reversed(seq):
            self.head = self.Node(val, self.head)
            if self.tail is None:
                self.tail = self.head

# now the nested iteration works...
ll = LinkedList([1,2,3,4])
for val in ll:
    for val2 in ll:
        print((val, val2))

Problem with iteration in linked list structure

1 Answers1