Linked lists

Let's define the following class.

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

Using this, we can build up a chain of Node objects.

a = Node('A', None) b = Node('B', a) c = Node('C', b)

We call such a chain a linked list. Of course, we've used this word list before in Python, as a word for a structure such as [2, 3, 5]. As it happens, that list is handled differently from a linked list. We'll regularly use the full phrase linked list when we want to refer to a chain of objects, but the unmodified word list refers to Python's structure.

After defining Node, it can be handy to have an object referring to a list. We do this below.

class List:
    def __init__(self):
        self.head = None

This allows us to have a structure such as the following.

Now let's suppose we want to build a function that takes a LinkedList as a parameter.

We can build several functions to support operating on such a linked list.

# Returns the number of nodes in the linked list given as a parameter.
def count_nodes(list_obj):
    cur = list_obj.head
    steps = 0
    while cur is not None:
        steps += 1
        cur = cur.next
    return steps

We'll see this same pattern over and over again: In processing lists, we'll often want to iterate through each node of the list. We can accomplish this by introducing a variable (called cur above) that tracks which node we're “at,” and we'll have a loop that with each iteration steps the variable forward to the next node in the list (“cur = cur.next”). We want to continue this until cur becomes None, in which case we've completed processing each node in the list.

As another example of this pattern, consider the below function that displays the value in each node of the linked list given as a parameter.

# Displays each value in the linked list given as a parameter.
def print_values(list_obj):
    cur = list_obj.head
    while cur is not None:
        print(cur.data)
        cur = cur.next