Linked List — Explained with Examples

A linked list is a linear data structure where nodes point to the next node, enabling O(1) insertions/deletions but O(n) access time.

Linked lists store elements in nodes, each containing data and a pointer to the next node. Variants include singly linked (one direction), doubly linked (prev and next pointers), and circular (last node points to first). Unlike arrays, linked lists do not require contiguous memory, making insertions and deletions cheap at known positions — O(1) vs O(n) for arrays. However, random access is O(n) because you must traverse from the head.

Think of a linked list like a treasure hunt where each clue points to the next location. To reach clue #100, you must visit clues 1 through 99. But adding a new clue between two existing clues is easy — you just update the pointers.

Linked lists are used in undo/redo functionality, music playlists, hash table collision chains, and as the underlying structure for stacks and queues.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next and current.next.data != data:
            current = current.next
        if current.next:
            current.next = current.next.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # 1 -> 2 -> 3 -> None

Linked lists are rarely the first choice for modern applications (arrays or vectors are usually faster due to cache locality), but they remain important for understanding pointer manipulation and as building blocks.

Stack, Queue, Array, Hash Table

Stack Implementation