Linked Lists made simple with dummy nodes

NOTE: This article will also discuss the runtime complexity of different operations performed on a linked list. If you need a refresher on runtime complexity, please visit our article on the subject.

What are linked lists?

A linked list is a data structure that is built of nodes that have a certain order. Each node points to the next element in the list.
The first element in the list is called the head, while the last element is called the tail. The tail points to nothing as the next element (null).

When working with lists we usually have access to the head of the list (sometimes also the tail), from which we can traverse the rest of it.

In practice, it is usually recommended to also have a dummy node before the head. We’ll soon see why.
The dummy not is not part of the “actual data” in the linked list, meaning that an empty list will have only one node, which is the dummy node that points to nothing. The dummy node always exists and is only an implementation detail.

A linked list implementation in Python would look something like this:

class ListNode:
    def __init__(self, value, next_node):
        self.value = value
        self.next_node = next_node


class LinkedList:
    def __init__(self):
        self._dummy = ListNode(value=-1, next_node=None)
        self._size = 0
        self._tail = None

    @property
    def size(self):
        return self._size

We define a ListNode class, that has 2 properties, a value and a “next” element to point to. We also define our main LinkedList class which:

• Creates the dummy node that points to no element because the list is empty
• A size data member to keep track of the size of the list
• A tail pointer that starts as None because the list is empty

in this implementation we have no head pointer, as it is not really needed, we can just call dummy.next.

Common Operations

Get the element at the beginning of the list

Runtime complexity: O(1)

def head(self):
    if self._size == 0:
        return None
    return self._dummy.next_node.value

This is pretty simple. If the list is empty we return None, otherwise we return the value of the head.

Find if a node with a specific value exists

Runtime complexity: O(n)

def find(self, value):
    curr_node = self._dummy.next_node

    # Start traversing the list until we find the wanted node
    while curr_node is not None:
        if curr_node.value == value:
            # Node is found
            return True
        curr_node = curr_node.next_node

    # Node was not found
    return False

When finding an element in a list, we traverse from the head (actually the dummy) and go over each element until we reach the element that we are looking for.
The pattern of using a while loop until we reach None for our current value (or the next value) is common with linked lists. We keep assigning curr_node to the next element in each iteration, this is how linked list traversal is done.

Add an element at a specific index position

Runtime complexity: O(n)

def add(self, value, index):
    # Make sure index is in bounds
    if (index < 0) or (index > self._size):
        return
    curr_node = self._dummy

    # Traverse until we reach the node before the index where we want to add
    for _ in range(index):
        curr_node = curr_node.next_node

    # Add the new node at the found position
    new_node = ListNode(value=value, next_node=curr_node.next_node)
    curr_node.next_node = new_node

    # Update the tail pointer if needed
    if index == self._size:
        self._tail = new_node
    self._size += 1

The complexity is actually linear because we can potentially, in the worst case, add an element to the end (or middle / any amount of steps that is dependent on n) of the list.
Note that if you implemented this function where you only add an element to the start of the list (for the case index = 0) you would have a runtime complexity of O(1) because you only do a constant number of operations and don’t need the traversal over the list.

In addition, the implementation shows why using a dummy node is a powerful technique. Consider the case where we had “head” pointers and the list was empty, or we add an element at the first index. We would have to handle edge cases like setting our “head” pointer to be the new element. This implementation covers all cases without handling any edge cases.

Remove an element at a specific index position

Runtime complexity: O(n)

def remove(self, index):
    # Make sure index is in bounds
    if (index < 0) or (index > self._size - 1):
        return
    curr_node = self._dummy

    # Traverse until we reach the node before the one we want to delete
    for _ in range(index):
        curr_node = curr_node.next_node

    removed_value = curr_node.next_node.value

    # Delete the node by skipping the pointer over it
    curr_node.next_node = curr_node.next_node.next_node

    # Update the tail pointer if needed
    if index == self._size:
        self._tail = curr_node
    self._size -= 1

    return removed_value

We traverse the list until we reach the node that is before the node that we want to delete, and then set it to point to to element after the one we want to delete. (Line 9)

Note again that the dummy node is very powerful, no edge case handling is required.

Insert at the beginning of the list

Runtime complexity: O(1)

def insert_at_beginning(self, value):
    self.add(value, 0)

We can just reuse our add function. Note this has a constant time complexity.

Remove from the beginning of the list

Runtime complexity: O(1)

def remove_from_beginning(self):
    return self.remove(0)

Insert at the end of the list

Runtime complexity: O(1)

def insert_at_end(self, value):
    self._tail.next_node = ListNode(value=value, next_node=None)
    self._tail = self._tail.next_node
    self._size += 1

This is where our tail pointer comes in handy. We could use our add(value, index) function to add to the end of the list, but that would have a linear time complexity. Having the tail pointer let’s us perform this operation with a constant time complexity.

Different Linked List Variations

Until now we described the regular linked list, also known as “Singly linked list”. Let’s discuss a few other types.
We will not be implementing all common operations for every list type, as we keep this as an exercise for you. You are strongly encouraged to do it as it will help you practice and get comfortable working with lists.

Doubly Linked List

A doubly linked list has pointers pointing in both directions from every node (hence the name doubly), a previous pointer, and a next pointer.

A typical change that would be needed in our ListNode class would be this:

class ListNode:
    def __init__(self, value, next_node, prev_node):
        self.value = value
        self.next_node = next_node
        self.prev_node = prev_node

The main advantage of such an implementation is that now we can traverse in both directions, allowing for easier implementation and quicker implementation is some cases.

Circular Linked List

A circular linked list is a list where the tail of the list points to the head of the list, creating a cycle.
Note that in this case the list has no real beginning or ending, as it is just a cycle, so you have to make sure not to traverse the list infinitely.

Circular Doubly Linked List

This type of linked list is the combination of the 2 previous types. You can traverse in both directions, while the tail node also points to the head node, closing a cycle.

Final Words

Linked lists are commonly used for quick insertion and deletion (for example, when adding or removing from the head only) and also when implementing other data structures, such as Stacks, and Queues, which we will talk about next.
Being comfortable traversing and manipulating linked lists is very important for coding interviews, so it’s important that you practice.