An Introduction to Linked List Data Structures

Linked lists are one of the fundamental linear data structures alongside stacks, queues, arrays, and lists.

A linked list is a continuous list of nodes where a node is a block structure housing the node value and a pointer (or memory) address to the next node. Each node from the head node has a next pointer that keeps the address of the next node till it gets to the last node, which points to nothing.

Linked lists are used in web browsers to keep track of web pages visited and moves in multi-player board games. Linked lists also find usage in implementing other linear data structures and graphs, dynamic memory allocation, and performing arithmetic operations on long integers.

The connection from one node to another node differentiates linked lists from a regular list or array. Unlike the linked lists, arrays don’t keep track of their next or other values.

Here is a visual representation of a linked list:

Types of Linked Lists

The last node always points to NULL, except for circular linked lists.

Types of Linked Lists

There are three types of linked lists:

1. Singly-linked list
2. Doubly linked list
3. Circular linked list

You can derive other linked lists from the basic ones, e.g., circular doubly linked lists. This article teaches you how to implement the singly and doubly linked list and briefly discusses the circular linked list.

💡 In this article, we’ll use the Python programming language for the implementations.

Singly-linked list

You’re tasked with building a tool to retrieve documents connected to each other but stored at random memory locations. You’re puzzled as to what data structure to use to fit this use case, as arrays store documents sequentially. The good news is that you can use the singly linked list for this task.

A singly linked list is defined by its node. A singly linked list node has a value and the next pointer. The diagram below is an example of a singly linked list.

To implement the linked list, start with the node class:

class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.next = NoneCode language: Python (python)

In the code block above, the node class comprises two attributes:

• value: The value to be stored in the node.
• next: The pointer address to the next node. It has a default value of None ( NULL ).

Next, you need to implement the linked list class.

The linked list class

The linked list class is a wrapper for adding methods for node operations, such as appending a node, prepending a node, and deleting a node. Let’s say you want to append a node to the middle of a long chain of nodes. Doing so manually would look like this:

nodes = Node(10)
nodes.next = Node(11)
nodes.next.next = Node(13)
nodes.next.next.next = Node(14)

# Insert a new node after 11.

new_node = Node(12)
new_node.next = nodes.next.next
nodes.next.next = new_nodeCode language: Python (python)

The process above is stressful. In a scenario where you need to perform this same operation for a couple of nodes, say 10, you have to do this manually every time. This operation brings forth unnecessary code bulkiness and complexity – known as space complexity. Having a linked list class with a method solves this all.

ℹ️ Each new variable defined in a program takes a significant amount of space. For example, a node costs 48 bytes of space, and a thousand nodes will cost 48000 bytes. Each time the program is executed, this amount of space is used for a single node initialization operation ignoring the internal space used by the linked list methods. Not only does this extra space slow down your application, but it also impacts the planet via poor eco-design.

The linked list class is independent. The LinkedList class implementation is:

class LinkedList: 
    def __init__(self) -> None: 
        self.head = None
        self.tail = None
        Self.size = 0Code language: Python (python)

In the code block above, the linked list class comprises three attributes:

• head: The head of the linked list, which is the first node.
• tail: The tail of the linked list, which is the last node.
• size: The size of the linked list.

Singly-linked list operations

The primary operations of a singly linked list include:

1. Traversal
2. Insertion
3. Deletion

To perform the operations mentioned above, you need to define the methods under the linked list class. 

Before you begin to implement the primary operations, however, you will need to implement the __len__ method in the LinkedList class to return the length of your linked list stored in the self.size variable:

def __len__(self) -> int:
   return self.sizeCode language: PHP (php)

With the __len__ method implemented, you can return the size of the linked list with len(linkedlist).

Traversal

In simple words, traversal is a process of accessing elements stored in an object. A traversal operation is executed to print the elements in a linked list. 

Let’s implement our first method, __str__, to print out the elements in the linked list:

def __str__(self) -> str:
    linkedlist = ""
    current = self.head
 
    while current and current.next is not None:
        linkedlist += str(current.value) + "->"
        current = current.next
 
    linkedlist += str(current.value)
    return linkedlistCode language: Python (python)

The __str__ method in Python returns the string representation of an object. This method returns the node values in your linked list as a string separated by ->.

Insertion

The insertion operation enables you to add nodes to your linked list. You can add nodes to your linked list by prepending the node, appending the node, or by adding nodes at specific positions in the linked list.

Prepending a node

The prepend method adds a new node at the head of the linked list, making it the new head node. The previous head node is automatically set as the next node after the new node. 

Implement the prepend method in the LinkedList class:

def prepend(self, element) -> None:
    new_node = Node(element)
    new_node.next = self.head

    self.head = new_node
 
    if self.tail == None:
        self.tail = self.head
 
    self.size += 1Code language: Python (python)

In the code block above, the prepend method takes an argument element, which is, in turn, passed to the Node class to form a node new_node. The new_node has its next pointer set to the head of the linked list self.head, and the linked list’s head node also points to the new node created. 

The method then checks if the tail of the linked list does not exist; if the tail doesn’t exist, it is set to the value of the head node.

Lastly, the method increments the size of the linked list.

Appending a node

The append method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to None – signifying the end of the linked list. The new node is attached to the tail’s node pointer, and the size of the linked list is incremented.

Implement the method in the linked list class:

def append(self, element) -> None:
    node = self.head
    while node.next != None:
        node = node.next
 
    node.next = Node(element)
    self.tail = node.next
    self.size += 1Code language: Python (python)

Appending at a specific position

The last insertion operation is to append at a specific position. In this operation, a new node is added to the position specified. For example, if the linked list has four values, you can insert a new node at the third position. The node in the second position will have its next pointer pointing at the new node, and the new node points at the node originally in the third position.

In the LinkedList class, add the method:

def add_at_position(self, position, element) -> None:
    if position < 1 or position > self.size:
        raise IndexError("Position is invalid")

    if position == 1:
        self.prepend(element)
        return

    index = 1
    prev = None
    current = self.head
    new_node = Node(element)

    while index != position:
        index += 1
        prev = current
        current = current.next
    prev.next = new_node
    new_node.next = current
    self.size += 1Code language: Python (python)

With the insertion methods in place, create a new linked list and perform some operations:

ll = LinkedList()
ll.prepend(40)
ll.append(50)
ll.add_at_position(2, 45)
 
print(len(ll)) # 3
print(ll) # 40 -> 45 -> 50Code language: Python (python)

Deletion

The deletion operation involves removing a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the LinkedList class:

def delete_node(self, position) -> None:
    if position < 1 or position > self.size:
        raise IndexError("Invalid position!")
 
    if position == 1:
        self.head = self.head.next
        return
 
    if position == self.size:
        prev = None
        current = self.head
 
        while current.next is not None:
            prev = current
            current = current.next
 
        prev.next = None 
        self.tail = prev
 
        self.size -= 1
        return
 
   # Position specified isn't head nor tail.
     index = 1
     prev = None
     current = self.head
 
     while index != position:
         index += 1
         prev = current
         current = current.next
 
     prev.next = current.next
 
     self.size -= 1
 
     return current.elementCode language: Python (python)

In the code block above, the delete_node function performs three delete operations:

1. Deleting the head node: If the position specified is 1, the head node is deleted by setting the value of the head node to the second node in the linked list.
2. Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to None to eliminate the tail node.
3. Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. The node preceding the node at the specified position will have its next pointer set to the node located after the deleted node.

All of the operations above decrease the size of the linked list. An IndexError will be returned if a wrong position is passed to the method.

If you delete the second node you created earlier, the new linked list will be:

ll.delete_node(2)
print(ll, len(ll)) # Prints 40 -> 50, 2Code language: Python (python)

Doubly linked list

You’re tasked with implementing a new feature in a multiplayer board game (chess, checkers, tic-tac-toe, etc.) that enables a user to go back to their previous move. To implement this feature, you’ll likely need to use a doubly linked list data structure. 

A doubly linked list has two node pointers—one pointer pointing to the previous node and the other pointing to the next node.

Here is a graphical representation:

To implement a doubly linked list, implement the node class first:

class Node:
    def __init__(self, value):
        self.value = value
        self.previous = None
        self.next = NoneCode language: Python (python)

The Node class above comprises three attributes:

• value: The value to be stored in the node.
• previous: The pointer address of the previous node.
• next: The pointer address of the next node.

The linked list class

The linked list class is a wrapper for adding methods for node operations. The LinkedList class definition for a doubly linked list is:

class LinkedList: 
    def __init__(self) -> None: 
        self.head = None
        self.tail = None
        self.size = 0Code language: Python (python)

Doubly linked list operations

Just as before, the primary operations of a doubly linked list include:

1. Traversal
2. Insertion
3. Deletion

To perform the above-mentioned operations, you need to define the methods under the linked list class.

Before you begin to implement the primary operations, implement the __len__ method in the LinkedList class to return the length of your linked list stored in the self.size variable:

def __len__(self) -> int:
       return self.sizeCode language: Python (python)

With the __len__ method implemented, you can return the size of the linked list with len(linkedlist).

This should look familiar, because it is the exact same method definition as a singly linked list.

Traversal

Let’s implement our first method, __str__, to print out the elements in the linked list:

def __str__(self) -> str:
    linkedlist = ""
    current = self.head
 
    while current and current.next is not None:
        linkedlist += str(current.value) + "<->"
        current = current.next
 
    linkedlist += str(current.value)
    return linkedlistCode language: Python (python)

In the code block above, the __str__ method will iterate through the linked list and store each node value separated by the delimiter <-> in a variable linkedlist which is returned when a linked list object is to be printed.

ℹ️ The __str__ and __len__ methods are the same for all linked lists. The only difference is the delimiter -> for singly and  <-> for the doubly linked list.

Insertion

The insertion operation enables you to add nodes to your linked list either by prepending the node, appending the node, or adding the node at specific positions in the linked list.

Prepending a node

The prepend method adds a new node at the head of the linked list. Implement the prepend method in the LinkedList class:

def prepend(self, element) -> None:
    new_node = Node(element)
    new_node.next = self.head
 
    if self.head is not None:
        self.head.previous = new_node
 
    self.head = new_node
 
    if self.tail == None:
        self.tail = self.head
 
    self.size += 1Code language: Python (python)

In the code block above, the method starts by creating a new node, new_node, with the argument passed to the prepend method. The method assigns the next pointer to the head node. It then checks if the linked list is not empty and assigns the head node’s previous pointer to the new node.

Once the pointer assignments are complete, the new node is assigned as the new head of the linked list.

Appending a node

The append method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to None (the end of the linked list). Once the end of the linked list is reached, the new node is attached to the tail’s node pointer, and the size of the linked list is incremented.

Implement the method in the linked list class:

def append(self, element) -> None:
    if self.tail is None:
        self.prepend(element)
        return
 
    new_node = Node(element)
 
    self.tail.next = new_node
 
    new_node.previous = self.tail
 
    self.tail = new_node
 
    self.size += 1Code language: Python (python)

In the code block above, the append method checks if the tail of the linked list is None. If the tail is None, the method performs a prepend operation and exits.

However, if the tail exists, a new node is created and its previous pointer is set to the linked list tail node. The tail node as well sets its next pointer to the new node. Once the pointer assignment is completed, the new node is made the new tail by assigning the node to the self.tail variable.

Appending at a specific position

Linked list nodes can be appended at a specified position. An example is inserting a new node at the fourth position in a linked list with five values.

The node before the position specified will have its next pointer pointing at the new node and its next pointer pointing at the node originally at the position specified.

In the LinkedList class, add the method:

def add_at_position(self, position, element):
    if position < 1 or position > self.size:
        raise IndexError("Position is invalid")
    if position == 1:
        self.prepend(element)
        return
 
    index = 1
    current = self.head
    new_node = Node(element)
 
    while index != position:
        index += 1
        current = current.next
 
    prev = current.previous
 
    prev.next = new_node
    new_node.previous = prev
    new_node.next = current
    current.previous = new_node
 
    self.size += 1Code language: Python (python)

In the code block above, the method first checks if the position is valid before proceeding. If the position is invalid, the method returns an IndexError.

If the position specified is the head node position 1, the method invokes the prepend method for the insertion. Otherwise, the method traverses the whole linked list until it gets to the position and performs the following:

• The method assigns the preceding node’s next pointer to the new node
• Sets the new node’s previous pointer to the preceding node
• Sets the new node’s next pointer to the current node
• Sets the current node’s previous pointer to the new node

With the insertion methods in place, create a new linked list and perform some operations:

dll = LinkedList()
dll.prepend(40)
dll.prepend(30)
dll.append(50)
dll.add_at_position(1, 10)
 
print(dll) # 10<->30<->40<->50Code language: Python (python)

Deletion

The deletion operation removes a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the LinkedList class:

def delete_node(self, position):
    if position < 1 or position > self.size:
        raise IndexError("Invalid position!")

    if position == 1:
        node_to_remove = self.head
        newHead = self.head.next
        node_to_remove.next = None
        node_to_remove.previous = None

        self.head = newHead
        self.size -= 1
        return node_to_remove.value

    if position == self.size:
        node_to_remove = self.tail
        new_tail = self.tail.previous

        node_to_remove.previous = None
        new_tail.next = None

        self.tail = new_tail
        self.size -= 1
        return node_to_remove.value
    index = 1
    current = self.head

    while index != position:
        index += 1
        current = current.next

    prev = current.previous
    prev.next = current.next
    current.next.previous = prev
    self.size -= 1
    return current.valueCode language: Python (python)

In the code block above, the delete_node function performs three delete operations:

1. Deleting the head node: If the position specified is 1, the head node is deleted by setting both pointers to None, and the second node is assigned the head node.
2. Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to None to eliminate the tail node. The outgoing tail node’s pointers are also set to None respectively.
3. Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. For example, to delete the third node in a 5-value linked list, the second node will have its next pointer pointing to the fourth node, and the fourth node’s previous pointer will now point to the second node.The node preceding the node at the position will have its next pointer set to the node of the next pointer of the node to be deleted. The next pointer after the node to be deleted will have its previous pointer pointing to the node preceding the current node to be deleted.

All of the operations above decrease the size of the linked list. An IndexError will be returned if a wrong position is passed to the method.

If you delete the second node you created earlier, the new linked list will be:

dll.delete_node(2)
 
print(dll) # 10<->40<->50Code language: Python (python)

Circular linked lists

Circular linked lists are singly linked lists except that their last node points to the first node as opposed to None. As a result, the circular linked list does not have a tail node. Circular linked lists are commonly used to manage computing resources.

The circular linked list shares the same logic for insertion, traversal, and deletion as the singly linked list with the only difference being the assignment of the last node’s next pointer to the head node.

For example, the append method for the circular linked list is:

def prepend(self, value):
    cur = self.head
    new_node = Node(value)
    new_node.next = self.head

    if not self.head:
        new_node.next = new_node
    else:
        while cur.next != self.head:
            cur = cur.next
        cur.next = new_node
    self.head = new_nodeCode language: PHP (php)

In the code block above, the prepend method first checks if the head node is not present in the linked list. If there’s no head node, the new node’s next pointer is set to itself, creating a circle.

The circular linked list is implemented in the sandbox below to avoid repeating the implementation of the singular linked list.

Try it out in the CoderPad sandbox!

In this article, you have learned what linked lists are and how to implement singly and doubly linked lists. You can play with the sandboxes beneath this section to test the method you learned as well as implement new methods – the Coderpad Sandbox is an interactive sandbox for peer coding, live coding, and interviews.

Want more challenges? Create a sandbox and implement the reversal method for singly and doubly linked lists, create a tweet with your sandbox link, and tag CoderPad.