Linked List Implementation With Examples and Animation

A linked list is one of the most basic data structures in computer science. In this article, we will go through the following topics:

• Advantages and disadvantages of linked list over arrays.
• What is a linked list?
• Insertion in a linked list (insert node).
• Deletion from a linked list (delete node).

What is a linked list?

It is a list of nodes where each node contains data and a pointer to the next node in the list. It is a linear data structure, meaning it can be traversed by following only one pointer at a time. The first node is called the head, and the last node is called the tail. The tail node points to null.

class Node:
    def __init__(self, data: int, next_node: 'Node' = None):
        self.data = data
        self.next = next_node

Insertion in a linked list (insert node)

There are three ways to insert a node in a linked list:

1. Insert at the beginning of the list.
2. Insert at the end of the list.
3. Insert at a given position.

Insert at the beginning of the list

Let's start with the simplest one. We will insert a node at the beginning of the list. The algorithm consists of the following steps:

• Create a new node.
• Set the next pointer of the new node to point to the head.
• Set the head to point to the new node.
• Return the new head.

def insert_at_beginning(head: Node, data: int) -> Node:
    new_node = Node(data)
    new_node.next = head

    return new_node

Let's create a list of 4 nodes with that method:

head = None
for i in range(4):
    head = insert_at_beginning(head, i + 1)

The time complexity of this algorithm is O(1) because we are only changing the head pointer

Insert at the end of the list

That algorithm is a bit more complicated, but still an easy one. We will insert a node at the end of the list.

• Create a new node.
• Set the next pointer of the new node to point to null.
• Iterate through the list until we find the last node.
• Set the next pointer of the tail node to point to the new node.
• Return the head.

def insert_at_end(head: Node, data: int) -> Node:
    new_node = Node(data)

    if head is None:
        return new_node

    current = head
    while current.next is not None:
        current = current.next

    current.next = new_node

    return head

head = None
for i in range(5):
    head = insert_at_end(head, i + 1)

The time complexity of this algorithm is O(n) because we are iterating through the list until we find the tail.

Insert at a given position.

We will insert a node at a given position. The algorithm consists of the following steps:

• Create a new node.
• Iterate through the list until we find the node at the given position.
• Set the next pointer of the new node to point to the node at the given position.
• Set the next pointer of the previous node to point to the new node.
• Return the head.

def insert_at_position(head: Node, data: int, position: int) -> Node:
    new_node = Node(data)

    if position == 0:
        new_node.next = head
        return new_node

    current = head
    current_position = 0
    while current is not None and current_position < position - 1:
        current = current.next
        current_position += 1

    if current is None:
        return head

    new_node.next = current.next
    current.next = new_node

    return head

The time complexity of this algorithm is O(n) because we are iterating through the list until we find the node at the required position

Insert a node at position 0:

Insert a node at a position greater than the length of the list:

Insert a node at a position between 0 and the length of the list:

Deletion from a linked list

There are three ways to delete a node from a linked list:

1. Delete the first node.
2. Delete the last node.
3. Delete a node at a given position.

Delete the first node

The algorithm consists of the following steps:

• Set the head to point to the second node.
• Return the new head.

def delete_first(head: Node) -> Node:
    if head is None:
        return None

    return head.next

The time complexity of this algorithm is O(1) because we are only changing the head pointer.

Delete the last node

The algorithm consists of the following steps:

• Iterate through the list until we find the second last node.
• Set the next pointer of the second last node to point to null.
• Return the head.

def delete_last(head: Node) -> Node:
    if head is None:
        return None

    if head.next is None:
        return None

    current = head
    while current.next.next is not None:
        current = current.next

    current.next = None

    return head

The time complexity of this algorithm is O(n) because we are iterating through the list until we find the second last node.

Delete a node at a given position

The algorithm consists of the following steps:

• Iterate through the list until we find the node at the given position.
• Set the next pointer of the previous node to point to the node after the node at the given position.
• Return the head.

def delete_at_position(head: Node, position: int) -> Node:
    if position == 0:
        return head.next

    current = head
    current_position = 0
    while current is not None and current_position < position - 1:
        current = current.next
        current_position += 1

    if current is None or current.next is None:
        return head

    current.next = current.next.next

    return head

The time complexity of this algorithm is O(n) because we are iterating through the list until we find the node at the required position.

Conclusion

In this article, we have seen how to implement a linked list in Python. That data structure is very efficient when you need to add or remove elements from the head of the list. It is also very easy to implement.