Singly Linked Lists

Introduction

Singly Linked Lists are dynamic list or array structure that allows us to store an arbitrary number of elements. The overall concept of singly linked lists is very simple: It consists of an arbitrary number of nodes, where each nodes stores the content (or data) of that node and a pointer or reference to the next node. One major advantage of a singly linked lists is that we can grow it arbitrarily in size, which is very useful if we don't know the number of elements we want to store upfront. Furthermore, the insertion of new elements at the beginning of the list is very cheap, since it only requires us to change one reference or pointer as we will see later.

Algorithm Complexity Overview:

• inserting an element at the head: O(1)
• counting the number of elements: O(n)
• searching for an element: O(n) [worst case]
• deleting an element: O(n) [worst case]

(We will discuss this in more detail in the following sections.)

Code Overview

The Node Class

If you glanced over the code overview above, you noticed that we are going to implement the Singly Linked List using two classes, a Singly Linked List Node (SLLNode) and the Singly Linked List itself (SinglyLinkedList). First, let's have a look at the SLLNode object.

class SLLNode(object):
    def __init__(self, data, next_node=None):
        self.data = data
        self.next_node = next_node

This simple class takes a data argument as input as well as an argument next_node, which defaults to None. When we instantiate a new node, we typically want to have some data associated with it -- why would we want to create a new node, otherwise? The reason why we don't want to require a next_node attribute is that the last node in the Singly Linked List does not have a next_node.

To summarize, a SLLNode object is a simple object that consists of two attributes only, the data, which it is meant to store, and a "pointer" to the next node.

The SinglyLinkedList Class

Let's go through the SinglyLinkedList implementation step by step. The rough skeleton of this class would look like this:

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

    def __repr__(self):
        ...

    def insert(self, data):
        ...

    def size(self):
        ...

    def search(self, data):
        ...      

    def delete(self, data):
        ...

__init__ and __repr__

• __init__ : The SinglyLinkedList objects only have one single attribute, head, which points to the first node in our data structure.

• __repr__: This method is not really required; we implement this "operator overloading" for our own convenience, so that we can use the print function to display the SinglyLinked list. Unfortunately, this __repr__ method may look a bit complex at first glance, but it will become much more intuitive later when we talk about the other SinglyLinkedList methods. If you are interested, let's take a quick look at it now, anyway; however, please feel free to skip this section since it is not really relevant for implementing a singly linked list -- it's just an additinional method for convenience:

def __repr__(self):
    s = ''
    if self.head is not None:
        current_node = self.head
    else:
        current_node = None

    while current_node is not None:
        s += ' --> %s' % current_node.data
        current_node = current_node.next_node
    return 'Size: %s\nData: ' % self.size() + s[5:]

First, we initialize an empty string variable s. If our SinglyLinkedList variable is empty, which we check via the head attribute, we set the current_node to None so that the while loop that follows will not be exectuted; otherwise, we sed the current_node variable to the linked list's head. Now, via the while loop, we now traverse through the linked list as long as the current_node points to a next_node. If the current_node is not None, we add its data to the string variable s, which we initialized at the beginning of this method; then, we set the current_node variable to the next node via its next_node pointer. The while loop stops if current_node is None in the next iteration, which happens if the current_node in the previous iterations does not point to a next_node.
Finally, we return the string variable after we made some additional modifications to it. First of all, we compute the size of the linked list (i.e., the number of nodes in the list) using the size method, which we will discuss a little bit later. Then, we add the string that we created inside the while loop to it. Note that we "slice" the list (s[5:]) to get rid of the prepending " --> " at the beginning of the string.

Now, let us initialize an empty linke list and exectute the print method:

As we can see, the the print method displays a string consisting of 2 lines: The first line shows the size of the list, which is obviously 0 since we didn't add any nodes to it, yet. The second line prints the contents of the nodes. Since we don't have a node in the linked list, there's no data to be printed.

insert

Let's go ahead and insert some data into our newly created Singly Linked List object using the insert method:

def insert(self, data):
    new_node = SLLNode(data=data, next_node=None)
    new_node.next_node = self.head
    self.head = new_node

This implementation of insert creates a new node that points to the current head node of the list (if it exists). Then, the new node becomes the head node itself. In other words, we insert a new node at the beginning of the linked list as a head node, which points to the previous head node; this moves all exisiting nodes in the linked list back by one position. Since we only create a new node, i.e., change one single pointer, the insert method is very efficient with constant complexity O(1).

Let's give it a try by insert a node that holds a Python list as its data element:

Before we discuss the search method in the next section, let's add two more nodes to our linked list:

search

The complexity of searching a singly linked list is O(n) (where n is the number of nodes or the size of the linked list), since we have to traverse through the whole list in the worst case scenario, i.e., if the item we are looking for is the last item or if the search key isn't contained in the linked list at all.

Searching a linked list is pretty straight forward:

def search(self, data):
    current_node = self.head
    target_node = None
    while current_node is not None and target_node is None:
        if current_node.data == data:
            target_node = current_node
        else:
            current_node = current_node.next_node
    return target_node

We start with the head node, and in a while loop, we look for the data (search key) until we find it in the current node current_node.data == data: or until we are running out of nodes in the list while current_node is not None. Finally, we return the target note that contains our data search key, or return None if no node matched our query. Let's see it in action:

If we don't find a node in our linked list that contains the search key, we return None:

delete

Deleting an element from a singly linked list is also a O(n) operation; it's actually very similar to search, which we discussed above.

def delete(self, data):
    current_node = self.head
    previous_node = None
    found = False

    while current_node is not None and not found:
        if current_node.data == data:
            found = True
            if previous_node is None:
                self.head = current_node.next_node
            else:
                previous_node.next_node = current_node.next_node

        else:
            previous_node = current_node
            current_node = current_node.next_node

The difference between search and delete is that we also keep track of the previous node now. Again, we start with the head node as the current node, and we excecute a while loop that runs until we reach the last node in the linked list or deleted the respective node -- note that we are modifying the linked list in place in this implementation.
The deletion, on a conceptual level, works like this: If we find a node that contains our search key, let's call it out current_node, we move the pointer of the previous_node to the node that comes after the current_node (i.e., the current_node.next_node. By doing so, we are essentially removing the reference to the deleted node from the linked list so that Python's garbage collector can get rid of it since it is no longer needed. If our search query matches the head node, that is, if there is no "previous node," we simply re-assign the head node to the second element in the linked list.

Let's give it a try by removing an element from the middle of the list:

Now, let's remove the head node:

And finally, we remove the last remaining element from our linked list:

So, that's basically "Single Linked Lists" in a nutshell!

Ordered Lists

The singly-linked-list implementation above can is a so-called unordered data structure or list. The reason is that it collects items in an unsorted manner. On the other hand, ordered lists store items sorted by their values. For example, in our unordered singly-linked example, we may have a list of items in the following order:

• [5, 1, 3]

and and we can add items at an aribtrary position. For example, we can add a new number 4 as follows

• [4, 5, 1, 3]
• [5, 4, 1, 3]
• [5, 1, 4, 3]
• [5, 1, 3, 4]

In an ordered list, the sorting order is always maintained. Assuming that we have an ordered list that keeps the items in ascending order, [1, 3, 5], the "add" method will add the number 4 only as follows:

• [1, 3, 4, 5]