0

I'm trying to learn linked lists and I'm stuck at the point where the instructor wrote down the __iter__ method.

Although I particularly don't understand the part where it says while node, node = node.next and print(node.value for node in singlyLinkedList) I would be very grateful if you could explain __iter__ and print parts in detail.

# step 1: defining class for creating head and tail pointers
class SLinkedList:
    def __init__(self) -> None:
        self.head = None
        self.tail = None
        # we cannot print this bcoz this is a custom data structure. 
        # so to be able to print this, we need to define 
        # a helper function
    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.next

# step 2: class for creating node
class Node:
    def __init__(self, value=None) -> None:
        self.value = value
        self.next = None

# step 3: assign value (create nodes)
singlyLinkedList = SLinkedList()
node1 = Node(1)
node2 = Node(2)
# step 4: create link between nodes and head & tail
singlyLinkedList.head = node1
singlyLinkedList.head.next = node2
singlyLinkedList.tail = node2

print(node.value for node in singlyLinkedList)
trincot
  • 317,000
  • 35
  • 244
  • 286
VRM
  • 83
  • 1
  • 7

1 Answers1

0

this is one of these cases where Typing annotations makes thinks more easier, see Python typing for more info. You are in the case of Singly linked list. Where a Singly linked list contains nodes. Each node has a data field self.value and a next field self.next which points to the next Node. Therefore:

class SLinkedList:
    def __init__(self, head: Node = None, tail: Node = None) -> None:
       self.head = head
       self.tail = tail

    ## here comes your iter dunder method

class Node:
    def __init__(self, value: int = None, next: Node = None) -> None:
        self.value = value
        self.next = next

Then you need to iterate through this nodes, but... Singly linked list only knows the value of the first node and the last node... There is where your instructor comes with the idea of representing the iteration through the __iter__ dunder method and the yield keyword.

The yield keyword is like a return, but it returns a Generator, see the answer from Neuron on this post to know more about Generators and iterators, he explains it very well.

The __iter__ dunder method in short words, is the pythonic method where to define the iteration process, you can define it in a custom named method 'customIterable' if you like, but __iter__ is the best place, for standard purpose. Then, your __iter__ method can be read like this:

  1. Take the first Node from the the Single linked list and store it locally in the variable called node
  2. While node is different from None return the Node instance object stored in it. Then, set to the local variable node the Node instance stored in the next attribute of the current Node.

As you see at first glance seems a bit confusing, because the yield keyword seems exiting the loop, she is returning the current Node instance, how it continues looping?. The imperative to understand the yield keyword is to know that when you set yield in the body of a function, when the function is called, the code inside it is not run, instead, a Generator object is returned This way, when you call your SLinkedList object instance inside a for .. in .. loop you are executing the code inside __iter__ until reach yield then again, and again, ad nauseam.

This way, in the code executed in the first loop of the for loop is:

node = self.head
    while node:
        yield node

On the second iteration of the for loop the next line to execute is node = node.next, cronologically the code is executed until next yieldlike this:

node = node.next
# check the condition 'while node:'
yield node

In your case you only have two Nodes, a way to see your code better organized could be, using the code from below:

class SLinkedList:
    def __init__(self, head: Node = None, tail: Node = None) -> None:
        self.head = head
        self.tail = tail
    
    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.next


class Node:
    def __init__(self, value: int = None, next: Node = None) -> None:
        self.value = value
        self.next = next


# Create nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)    

# Link the nodes
node1.next = node2
node2.next = node3 

# Create the Single Linked List 
singlyLinkedList = SLinkedList(node1, node3)

print([node.value for node in singlyLinkedList])
# [1, 2, 3]
KermitTheCoder
  • 1
  • 3