This lesson's interactive features are locked, please to keep using them

Iterating

Even though iterating with linked lists kinda sucks compared to the simplicity of arrays (normal lists), we've got to do it. Although the implementation is more complex and slow, we can still make it easy for users of our class by providing an __iter__ method. If __iter__ is a generator function, Python can use it to drive a for loop over our class.

Assignment

The LinkedList class is a wrapper class that uses the Node class we already wrote.

Complete the __init__ method. It should set the head field to None.

No other node points to the linked list's head (first) node, so the LinkedList class itself needs to keep track of it. We'll use the term head and tail like this:

head node -> node -> node -> node -> tail node

The direction of flow above might feel opposite to what you're used to with a Queue, but it's really the same. Above I'm using arrows to show which nodes are pointing to which other nodes. In a future lesson when we implement a Queue using a LinkedList, we'll add elements to the tail and remove elements from the head.

Complete the __iter__ method. It should be a generator function that yields each node in the linked list, from the head to the tail.
1. Create a reference to the head node (e.g. node = self.head)
2. Use a while loop to iterate over the linked list until node is None
  1. Yield the current node
  2. Set node to the next node

We need to change which node is the next to be yielded, but the set_next method of the Node class changes which is the next to be pointed to – don't use it!

By overriding the __iter__ method, Python will allow us to use a for loop to iterate over the linked list:

from node import Node

ll = LinkedList()
ll.head = Node("first")
ll.head.next = Node("second")
ll.head.next.next = Node("third")

for node in ll:
    print(node.val)