Many of my programming students get asked to implement Linked Lists as a way to learn about data structures in programming. Now I am going to be very honest about this topic when it comes to Python. Python does not use fixed sized arrays list Java or C++ use. Instead, Python has a list object as a built in data type that grows and shrinks as needed.

For this reason, I can’t see any practical purpose to implementing a Linked List in Python other than for learning purposes (of course, that said, Java and C++ libraries have data structures that shrink and grow as needed also, so again, not sure why we would ever need to write our own linked list). That being said, I think there is value in learning about data structures such as Linked Lists.

Arrays

Many programming languages have a data structure called an array. Arrays are a lot like an egg carton. There are x number of slots in which you can place an egg. Here is an example of an array in Java.

String [] phoneNumbers = new String[12];
phoneNumbers[0] = "867-5309";
phoneNumbers[1] = "978-6410";
//and so on...

We use arrays for the same reason that we use lists in Python. They allow us to group common data together into a single variable. So we could iterate through this example array like this…

for (String num : phoneNumbers){
    System.out.println(num);
}

Arrays are extremely efficient in that you can easy create an array, fill it with data, and process that data. Nevertheless, Array’s have a major limitation. They are a fixed size. We are not able to grow or shrink and Array.

Linked List

Linked Lists are a data structure that give us the convience that is offered by an Array, but also allows us to grow and shrink the data structure as needed. We even get the added bonus of being able to insert elements into random positions in the array.

Linked list work on the idea that inside of the Linked List we have a Node object that contains the data for that particular node and a reference to the next node in the list. By manipulating where the node points, we can expand or shrink the list as needed. We can also insert items into the middle of the list by pointing the node at different Node objects within the list.

The Linked List itself is a container class for the Nodes. It does the work of creating Nodes, removing Nodes, and updating Nodes. Before we get into complete detail, here is the code for a simple Singly Linked List written in Python.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node


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

    def size(self):
        count = 0
        current = self.head

        while current is not None:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head)
        self.head = node

    def insert_last(self, data):
        if not self.head:
            self.head = Node(element=data)
        else:
            current_node = self.head
            while current_node.next_node is not None:
                current_node = current_node.next_node
            current_node.next_node = Node(element=data)

    def insert(self, data, position):
        if self.head is None:
            self.head = Node(element=data)
        else:
            if position > self.size() or position < 0:
                raise IndexError
            else:
                if position == 0:
                    self.insert_front(data)
                elif position == self.size():
                    self.insert_last(data)
                else:
                    temp = self.head
                    pos = 0
                    while pos < (position - 1):
                        temp = temp.next_node
                        pos += 1

                    next_node = temp.next_node
                    temp.next_node = Node(element=data, next_node=next_node)

    def remove_first(self):
        if self.head is not None:
            self.head = self.head.next_node

    def remove_last(self):
        if self.head is not None:
            current_node = self.head
            prev = None

            while current_node.next_node is not None:
                prev = current_node
                current_node = current_node.next_node

            if prev is None:
                self.head = None
            else:
                prev.next_node = None

    def remove(self, position):
        if self.head is not None and position == 0:
            self.remove_first()
        elif self.head is not None and position == self.size():
            self.remove_last()
        else:
            if position  self.size():
                raise IndexError
            pos = 0
            current_node = self.head
            next_node = self.head.next_node
            while pos < (position - 1):
                pos += 1
                current_node = next_node
                next_node = current_node.next_node

            current_node.next_node = next_node.next_node

    def fetch(self, position):
        if self.head is None:
            return None
        elif position  self.size():
            raise IndexError
        else:
            current_node = self.head
            pos = 0
            while pos != position:
                pos += 1
                current_node = current_node.next_node

            return current_node.element


import unittest
from random import randint


class TestSinglyLinkedList(unittest.TestCase):
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    def test_init(self):
        sll = SinglyLinkedList()
        self.assertIsNone(sll.head)

    def test_insert_front(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_front(name)

        self.assertEqual(sll.fetch(0), TestSinglyLinkedList.names[4])
        self.assertEqual(sll.fetch(1), TestSinglyLinkedList.names[3])
        self.assertEqual(sll.fetch(2), TestSinglyLinkedList.names[2])
        self.assertEqual(sll.fetch(3), TestSinglyLinkedList.names[1])
        self.assertEqual(sll.fetch(4), TestSinglyLinkedList.names[0])

    def test_insert_last(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        for i in range(len(TestSinglyLinkedList.names) - 1):
            self.assertEqual(sll.fetch(i), TestSinglyLinkedList.names[i])

    def test_insert(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        pos = randint(0, len(TestSinglyLinkedList.names) - 1)

        sll.insert('Teddy', pos)
        self.assertEqual(sll.fetch(pos), 'Teddy')

    def test_remove_first(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        for i in range(sll.size(), 0, -1):
            self.assertEqual(sll.size(), i)
            sll.remove_first()

    def test_remove_last(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        for i in range(sll.size(), 0, -1):
            self.assertEqual(sll.size(), i)
            sll.remove_last()

    def test_remove(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        sll.remove(1)

        self.assertEqual(sll.fetch(0), 'Bob Belcher')
        self.assertEqual(sll.fetch(1), 'Tina Belcher')
        self.assertEqual(sll.fetch(2), 'Gene Belcher')
        self.assertEqual(sll.fetch(3), 'Louise Belcher')

if __name__ == '__main__':
    unittest.main()

Implementation Details

As you can see, we are using Python’s OOP features to implement this linked list. That being said, this could have been down procedurally also. There is nothing that says linked lists have to be implemented in terms of classes and objects.

Node

The Node is the most basic element in the linked list. It has the responsibility to contain the data and point to the next node. That’s all it does. Here is the code for our Node class

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

SinglyLinkedList

The SinglyLinkedList class is the actualy linked list implementation. This is called SinglyLinkedList because each of the Nodes only link in a single direction (as opposed to a doubly linked list, which is bi-directional).

Here is the code for SinglyLinkedList followed by an explanation of each method.

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

    def size(self):
        count = 0
        current = self.head

        while current is not None:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head)
        self.head = node

    def insert_last(self, data):
        if not self.head:
            self.head = Node(element=data)
        else:
            current_node = self.head
            while current_node.next_node is not None:
                current_node = current_node.next_node
            current_node.next_node = Node(element=data)

    def insert(self, data, position):
        if self.head is None:
            self.head = Node(element=data)
        else:
            if position > self.size() or position < 0:
                raise IndexError
            else:
                if position == 0:
                    self.insert_front(data)
                elif position == self.size():
                    self.insert_last(data)
                else:
                    temp = self.head
                    pos = 0
                    while pos < (position - 1):
                        temp = temp.next_node
                        pos += 1

                    next_node = temp.next_node
                    temp.next_node = Node(element=data, next_node=next_node)

    def remove_first(self):
        if self.head is not None:
            self.head = self.head.next_node

    def remove_last(self):
        if self.head is not None:
            current_node = self.head
            prev = None

            while current_node.next_node is not None:
                prev = current_node
                current_node = current_node.next_node

            if prev is None:
                self.head = None
            else:
                prev.next_node = None

    def remove(self, position):
        if self.head is not None and position == 0:
            self.remove_first()
        elif self.head is not None and position == self.size():
            self.remove_last()
        else:
            if position  self.size():
                raise IndexError
            pos = 0
            current_node = self.head
            next_node = self.head.next_node
            while pos < (position - 1):
                pos += 1
                current_node = next_node
                next_node = current_node.next_node

            current_node.next_node = next_node.next_node

    def fetch(self, position):
        if self.head is None:
            return None
        elif position  self.size():
            raise IndexError
        else:
            current_node = self.head
            pos = 0
            while pos != position:
                pos += 1
                current_node = current_node.next_node

            return current_node.element

__init__

The __init__ method in SinglyLinkedList is small but important. This method creates the self.head variable, which is the first Node in the list. You will notice that we set it to None to indicate an empty list.

def __init__(self):
    self.head = None

size

The size method is used to calculate the size of the linked list. It works by traversing every single node in the list and keeping a count of each node it passes.

def size(self):
    count = 0
    current = self.head

    while current is not None:
        count += 1
        # Advance to the next node by setting
        # current to the next node
        current = current.next_node

    return count

This is a good method to help us understand the mechanics of the linked list. You will notice how each node has a next_node object attached to it. That next_node is either a Node or it is None. None is used to indicate that we have reached the end of the list.

We begin by creating a varaible current and referring it to self.head. Next we start a loop that terminates when current is None. Inside of the loop, we increment count by one, then advance to the next node. When current is None, we are at the end of the list and we can return the count as the size of the list.

insert_front

This method let’s us quickly add an item to the beginning of the linked list.

def insert_front(self, data):
    node = Node(element=data, next_node=self.head)
    self.head = node

We create a new node and set it’s next_node to self.head. Then we just update self.head to refer to the new node. Since the new node is now the head of the list, we have added the item to the front of the list.

insert_last

This method let’s us add an item to the end of the list really quickly.

def insert_last(self, data):
    if not self.head:
        # If this is the first insertion,
        # then we can just make it the head
        self.head = Node(element=data)
    else:
        # We need to advance to the 
        # end of the list
        current_node = self.head
        while current_node.next_node is not None:
            current_node = current_node.next_node
        
        # Now we can grow the list by adding
        # a new node and pointing current_node.next_node at it
        current_node.next_node = Node(element=data)

The first thing to do is check if the list if empty. We know it’s empty if self.head is None. If that’s the case, then just make self.head point at a brand new node.

If the list isn’t empty, then we need to advance to the end of the list and insert the new new node there. It’s not hard to do this. We start by creating a current_node variable and referring it to self.head. Then we just loop until current_node.next_node is None. In each iteration of the loop, we point current_node at current_node.next_node.

Finally we just set current_node.next_node to a new Node object. At this point, current_node referring to the last node in our list, so pointing it’s next_node at the new node is what adds to the list.

insert

The insert method is a little more complicated than the other two inserts. In this case, we are trying to insert a new Node into the middle of the list at an arbitrary position. The mechanics of this isn’t that difficult. What we need to do is find the node at the specified position and store it’s next_node in a variable. Then we create a new Node and set current_node.next_node to the new Node. The new Node’s next_node becomes the old curent_node.next_node.

However, we have a couple of conditions to check for first. For one thing, the list may be empty. The client may try to insert an item at a negative position or a position that is beyond the list’s size. They may also pass in a position that is 0, which means they are inserting in the front of the list. They could also specify a position that is equal to size, which means they could be trying to add to the end of the list. Therefore, our insert method needs to consider all of these cases.

def insert(self, data, position):
    if self.head is None:
        # This is the empty list case
        # Once again, we can just insert at head
        self.head = Node(element=data)
    else:
        if position > self.size() or position < 0:
            # This is the case where they are
            # trying to insert at a negative index
            # or beyond the size of the list.
            # Just raise an exception since that's a
            # programming error on the client's part
            raise IndexError
        else:
            if position == 0:
                # If they are trying to insert at 0, we
                # can use self.insert_front to do the work
                # for us.
                self.insert_front(data)
            elif position == self.size():
                # Likewise, we can just use
                # self.insert_last to handle cases
                # where position is the size() of the list
                self.insert_last(data)
            else:
                # Start with a temp variable
                # to hold the current node
                temp = self.head
                pos = 0 # track the position

                # We actually want to stop at right before
                # the position so that the new node is
                # inserted at the specified position
                while pos < (position - 1):
                    # Advance to the next node
                    temp = temp.next_node
                    # Update position
                    pos += 1

                # Store the next node into a tempory variable
                next_node = temp.next_node
                
                # Now set temp.next_node to a new Node object (and set the
                # now node's next_node to the old next_node)
                temp.next_node = Node(element=data, next_node=next_node)

You'll want to read through the comments of this code to get a better understanding of what is happening. Most of the code here we have seen already and we are just reusing code when possible. The important part to understand is when we do the insertion. We need to traverse the linked list to one node before where we want to insert the node.

Now keep in mind, that the current node, temp, has a next_node variable. We need to store that so that we don't lose the last half of the list. So we store it in a next_node variable. Now to actually perform the insertion, we point temp.next_node to a new Node object. Since the Node's __init__ method can take an option next_node argument, we just pass the next_node that we saved to the __init__ method. Thus, we insert a new node at the expected position.

remove_first

When we want to remove the first element in a linked list, we just need to set head to the next node in the list.

def remove_first(self):
    if self.head is not None:
        self.head = self.head.next_node

The only real thing we need to watch out for is if the list is empty. As long as the list isn’t empty, we just set self.head to self.head.next_node and the first item will get garbage collected by the Python runtime.

remove_last

In the case of removing the last item from the list, we can just traverse to the end of the linked list and set the 2nd to last Node’s next_node to None.

def remove_last(self):
    if self.head is not None:
        # Start at the head
        current_node = self.head
        prev = None

        # Loop 
        while current_node.next_node is not None:
            prev = current_node
            current_node = current_node.next_node

        if prev is None:
            self.head = None
        else:
            prev.next_node = None

Once again, we need to make sure the list isn’t empty. Then we go through the list until we get to the end of the list. While we traverse the list, we keep a reference to the node that is before current_node. It is this node’s next_node that we are setting to None, rather than current_node.next_node. The result will be that current_node is disconnected from the linked list and garbage collected.

We do have to account for the possibility that we are removing all items in the linked list. If prev is none, then we need to set self.head to None, which results in an empty linked list.

remove

This method let’s us remove a node at a specified position. It has the same special cases as it’s insert counter part so we aren’t going to cover them here. The idea is that we are taking a Node out of the list by taking the previous nodes next_node and pointing it at the deleted node’s next_node. The deleted Node gets garbage collected by the runtime.

def remove(self, position):
    if self.head is not None and position == 0:
        # Just use remove_first() remove the first item
        self.remove_first()
    elif self.head is not None and position == self.size():
        # or remove_last() to get rid of the last item
        self.remove_last()
    else:
        # Throw an exception if we are out of bounds
        if position  self.size():
            raise IndexError
        # Track the current position
        pos = 0
        
        # Track the current and next_nodes
        current_node = self.head
        next_node = self.head.next_node

        # Traverse through the list but stop at the node
        # right before the one we are deleting
        while pos < (position - 1):
            pos += 1
            current_node = next_node
            next_node = current_node.next_node
        
        # Now, make current_node.next_node point to
        # next_node.next_node. This removes next_node
        current_node.next_node = next_node.next_node

Once again, the comments will be helpful here. The idea is that we want to remove the node that is in between current_node and next_node.next_node. We can do that very easily by pointing current_node.next_node to next_node.next_node. The next_node object in between the two is severed from the list and garbage collected.

fetch

Our final method is used to retreive items from the list. By now, you have seen plenty of examples on how to traverse the list. In this case, we just traverse the list to the specified position and then return Node.element

def fetch(self, position):
    if self.head is None:
        return None
    elif position  self.size():
        raise IndexError
    else:
        current_node = self.head
        pos = 0
        while pos != position:
            pos += 1
            current_node = current_node.next_node

       return current_node.element

Of course, we need to check for empty lists and perform bounds checking. Otherwise, it’s simple enough to look up the value at the specified position.

Unit Testing

We aren’t going to cover unit testing in detail here, but I did provide an example class that tests this linked list implementation. Not only does it provide an example of Python’s unit testing framework, but it also shows how this class could be used. However, don’t use this class in production code. Python’s list object is a much better choice.

Conclusion

Linked lists are a way to create dynamically expanding collections of data. This tutorial demonstrated how to create a singly linked list. The key to understanding linked lists is to understand how the lists makes use of it’s Nodes. Once you have a solid understanding of how the nodes work, it’s relatively straight forward to make a linked list.