Linked Lists

Sat 17 January 2015

Filed under Python

Working with linked lists:

First: What is a 'linked list'?

In very short, a linked list is comprised of nodes that are linked together to create a collection of nodes, in other words a list. The nodes reside anywhere in the memory, not necessarily one right after the other as they do in an array.

So what's a node? You can think of it as a nugget of data that contains 2 sections:

1 – the data, the value, the cargo (different words for the same thing).

2 – the pointer, the reference, the 'next' which points to the next node in the linked list. (Technically, it really holds the address of where the next node resides in memory. But for our discussion here, we will refer to it as the 'pointer' or the 'next'.)

To kind of visualize it ...

| val | next | ----> |val | None |

Here, the first node points to the second node. And since there is no third node, the second node doesn't have a next or pointer, so it is None. Of course, there can be many nodes (with pointers pointing the next node) in a linked list.

or:

| val | address | ----> |val | None |

Technically, the first node holds the value and the address of where the second node lives. The second node holds the value, but since it is not linked to anything, there is no address; it holds a None.

and as an example:

| 1 | 300 | ----> |2 | None |

The first node lives at an address (not shown here) - see more about this below. The first node holds the value 1 and the address of its next node, here we made up the address as 300. The second node resides at the address 300 - which is what the first node was storing.

Technically, we need a reference to the address of the first node. That will be called the head.

To simplify for our discussion and in general, the first node is generally called the head of the linked list. The rest is referred to as the tail. The entire linked list is referenced by its head. In most cases, the head doesn't change too often, but the tail might. (The head would change if that first node is deleted or changed.)

How to set up a linked list?

We first set up a Node Class and instantiate the val and the next.

class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
    def __str__(self):
        return str(self.val)

So, a simple node can be set up:

>>node = Node(4)

This creates an instance of the Node class. - The val is 4. And next is still at the default of None

• node.val = 4

• node.next = None

There are several ways to actually set up the nodes and the whole list. And add or delete or modify the nodes. Here's my preferred way, several methods in the LinkedList class.

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

Start off by instantiating the list itself – defining the head and the tail. Both start off as None.

Here's the method for adding nodes.

  def add_node(self, val):
        new_node = Node(val)

        if self.head == None:
            self.head = new_node

        if self.tail != None:
            self.tail.next = new_node

        self.tail = new_node

In this add_node method, we will set the head of the list- when adding the first node. If the new node doesn't yet point to anywhere, the next remains as the default None.

With each new node, we set the next of the previous node – because only now we know where it will point to. And we add that new node – only the value; the next will remain None until it knows where to point to.

1. new_node is an instance of Node. (ex: if Node(6) then new_node is 6.)

2. Then, we see if we need to set the head or if it was already set. If head is still None, then this new_node is the head. If it is already set to something, then the head remains the same.

3. Next, we check if there is anything in the tail. If there is something other than None - meaning that there is a 'previous node' that is waiting to find out what it will point to - then the tail.next should be set to new_node. In other words, we now know where it should point to - to the new node.

4. Lastly, we add the new_node to the tail of the list.

In other words …

When we first instantiate – Node #0, there is no new_node yet, the head and tail are set to None.

Adding Node #1 = Node(6)

1. the new_node = 6

2. We check if the head (here shown as row above) is None and since it is the first added node, it is indeed None. Then we set the head to 6. Which it will be from hereon until we change that first node.

3. We check if the tail (here shown as row above) is not None. When adding this first node, it is still None. So we leave the next as None. When we will add the next node, we will change it (hence the arrow indicating that it was first none and then when adding the next node, we change the next to point to it.

4. We add the 6 to the tail.

When we add the second node (the 8), the head remains the same. We see that the previous tail now is not equal to None. So we need to add the 8 to next to that previous node.

And so it goes!

The last node has a value, and its next is None.

Now onto searching for something in that linked list

The basic idea is that we'll traverse through the linked list until we find what we are looking for. I've created it as another method of the LinkedList class.

def search(self, item):
    node = self.head
    while node != None:
        if node.val == item:
            return node.val
        else:
            node = node.next
    return 'not found'

1. We start off by setting the node to the 'head' of the list.

2. And use a 'while loop' to loop through the list.

3. If the node.val matches the searchitem, return that node.val

4. And if that node.val is not the search item, then move to the next node – by setting the node to the node.next.

5. And if after it goes through all nodes (when it does equal None) and it still has not been found, return 'not found'.

Pretty straight forward. We'll use this as the base for removing nodes.

Removing Nodes

An important point to remember as we think about removing nodes.

1. When nothing points to a node, it simply hangs about until Python's 'garbage collection' just throws it out. So removing the pointer that points to that node is part of the way we remove a node.

2. If we simply remove the next from a node, then anything after that is also disconnected from the first part of the list and thus lost. Like those long linked Xmas lights.

3. The best way to remove a node is to have the pointer that was pointing to it just point to something else, to the next node on the link. So for example if node 4 points to 5, and 5 points to 7, and 7 points to 8. If we want to remove node 7, we can change the pointer of 5 (which currently points to 7) to point to 8. And then nothing points to 7 and it's gone to garbage collection.

So we traverse the list searching for that node and then point the previous node – that was pointing to the one we want to remove – the next one. That's the idea.

But once we pass the previous node, we can't reference it anymore. So we have to keep track of the current node and the previous node.

Here's the code and then I'll explain:

def remove(self, item):
    node = self.head
    previous = None

    while node != None:
        current = node

        if node.val == item:
            previous.next = current.next
            return 'removed {}'.format(node.val)
        else:
            previous = current
            node = node.next
    return 'not found'

We set the node to the head and previous to None. We will use this previous to keep track of the previous node.

Use a while loop to traverse through the list. We set the current to the current node.

Next, we check if the node.val is the item we are searching for.

• And if it is, then next of the previous node is now set to th next of what is the current node.

• And if it is not, then we move both the previous and the current along the traversal of the list. The previous gets the value of the current one. And the current gets the value from the next. Until it is found. Or not.

This works great for searching any item in the list, or even something not in the list. But if the search item is the very first node – the head, then there is no previous as there simply is no previous. And also we set it to None. So the line previous.next = current.next won't work since previous is None, it can't have the next attribute. You'll get this error: AttributeError: 'NoneType' object has no attribute 'next'

Here's a solution. Add these lines before the while

    if self.head.val == item:

        self.head = node.next
        return 'removed {}'.format(node.val)

If the item == the self.head.val (the val of the first node), then we have found the node to be removed. But before we remove it, we need to set the new head. So the node.next of that node, of the self.head will be the new self.head. And we jump out of the method. (Read it slowly a second time, it does make sense.)