Linked List Implementation in Python

Introduction#

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations — each node holds a value and a reference (pointer) to the next node.

Linked lists are foundational to understanding dynamic data structures and are commonly used in interview questions and system internals (e.g., LRU caches, adjacency lists in graphs).

Core Concepts#

A linked list consists of:

Node: Holds a value and a reference to the next node
Head: The first node in the list
Tail: The last node (its next pointer is None)

Types of Linked Lists#

Singly Linked List: Each node points to the next node only
Doubly Linked List: Each node points to both the next and previous nodes
Circular Linked List: The tail node points back to the head

This post covers a singly linked list with a full implementation.

Implementation#

Node Class#

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None

LinkedList Class#

class LinkedList:
    def __init__(self) -> None:
        self.head: Node | None = None
        self.size: int = 0

    def append(self, value: int) -> None:
        """Insert a node at the end of the list."""
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node
        self.size += 1

    def prepend(self, value: int) -> None:
        """Insert a node at the beginning of the list."""
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def insert_at(self, index: int, value: int) -> None:
        """Insert a node at the given index (0-based)."""
        if index < 0 or index > self.size:
            raise IndexError(f"Index {index} out of range for list of size {self.size}")
        if index == 0:
            self.prepend(value)
            return
        new_node = Node(value)
        current = self.head
        for _ in range(index - 1):
            current = current.next
        new_node.next = current.next
        current.next = new_node
        self.size += 1

    def delete(self, value: int) -> bool:
        """Remove the first node with the given value. Returns True if deleted."""
        if self.head is None:
            return False
        if self.head.value == value:
            self.head = self.head.next
            self.size -= 1
            return True
        current = self.head
        while current.next is not None:
            if current.next.value == value:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False

    def delete_at(self, index: int) -> int:
        """Remove the node at the given index and return its value."""
        if index < 0 or index >= self.size:
            raise IndexError(f"Index {index} out of range for list of size {self.size}")
        if index == 0:
            value = self.head.value
            self.head = self.head.next
            self.size -= 1
            return value
        current = self.head
        for _ in range(index - 1):
            current = current.next
        value = current.next.value
        current.next = current.next.next
        self.size -= 1
        return value

    def search(self, value: int) -> int:
        """Return the index of the first node with the given value, or -1."""
        current = self.head
        index = 0
        while current is not None:
            if current.value == value:
                return index
            current = current.next
            index += 1
        return -1

    def reverse(self) -> None:
        """Reverse the linked list in place."""
        previous = None
        current = self.head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        self.head = previous

    def to_list(self) -> list[int]:
        """Return all node values as a Python list."""
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result

    def __len__(self) -> int:
        return self.size

    def __repr__(self) -> str:
        nodes = self.to_list()
        return " -> ".join(str(v) for v in nodes) + " -> None"

Usage Examples#

ll = LinkedList()

# Append elements
ll.append(10)
ll.append(20)
ll.append(30)
print(ll)          # 10 -> 20 -> 30 -> None

# Prepend
ll.prepend(5)
print(ll)          # 5 -> 10 -> 20 -> 30 -> None

# Insert at index
ll.insert_at(2, 15)
print(ll)          # 5 -> 10 -> 15 -> 20 -> 30 -> None

# Delete by value
ll.delete(15)
print(ll)          # 5 -> 10 -> 20 -> 30 -> None

# Delete at index
removed = ll.delete_at(0)
print(removed)     # 5
print(ll)          # 10 -> 20 -> 30 -> None

# Search
print(ll.search(20))   # 1
print(ll.search(99))   # -1

# Reverse
ll.reverse()
print(ll)          # 30 -> 20 -> 10 -> None

# Length
print(len(ll))     # 3

Time and Space Complexity#

Operation	Time Complexity	Notes
`append`	O(n)	Traverses to the tail
`prepend`	O(1)	Updates head only
`insert_at`	O(n)	Traverses to index
`delete`	O(n)	Scans for value
`delete_at`	O(n)	Traverses to index
`search`	O(n)	Linear scan
`reverse`	O(n)	Single pass, O(1) extra space

Space complexity is O(n) for storing n nodes.

Best Practices#

Prefer a doubly linked list when frequent backward traversal or O(1) tail deletion is needed
Track size explicitly to avoid O(n) length queries
Keep a tail pointer if append performance matters (reduces O(n) to O(1))
Use linked lists over arrays when frequent insertions/deletions at the head are required

Common Interview Patterns#

Linked lists appear frequently in technical interviews. Common problems include:

Detecting a cycle (Floyd’s tortoise and hare algorithm)
Finding the middle node (slow/fast pointer)
Merging two sorted lists
Reversing a sublist between positions
Checking if a linked list is a palindrome

These all rely on a solid understanding of pointer manipulation, which the implementation above covers.

Conclusion#

A singly linked list is a versatile data structure with O(1) prepend and pointer-based insertion/deletion. It trades random access (O(n) vs O(1) for arrays) for flexible dynamic sizing. Understanding the implementation details — especially pointer reassignment during deletion and reversal — is essential for working with more complex structures like graphs, trees, and LRU caches.