Linked Lists Explained (Singly, Doubly, Circular)

A linked list is a data structure where elements — called nodes — are scattered anywhere in memory and connected using pointers, rather than sitting in one contiguous block like an array. Each node stores a value and a reference ("pointer") to the next node in the sequence. This single design choice flips the array's tradeoffs almost completely: you lose instant indexed access, but you gain cheap insertion and deletion.

Singly, Doubly, and Circular Linked Lists

A singly linked list is the simplest form: each node points only to the next node, so you can traverse forward but not backward. A doubly linked list adds a second pointer to the previous node in each node, allowing traversal in both directions at the cost of extra memory per node. A circular linked list is either variant with the last node's "next" pointer looping back to the first node instead of pointing to nothing — useful for things like round-robin scheduling, where you want to cycle through items endlessly.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None  # pointer to the next node

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

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:       # walk to the last node -- O(n)
            current = current.next
        current.next = new_node

    def to_list(self):
        values, current = [], self.head
        while current:
            values.append(current.value)
            current = current.next
        return values

ll = SinglyLinkedList()
for v in [10, 20, 30]:
    ll.append(v)
print(ll.to_list())

Output:

[10, 20, 30]

For a complete working implementation with insert-at-front and delete operations, see the Python singly linked list program.

Linked Lists vs Arrays: The Complexity Tradeoff

This is the comparison that matters most. Index access on a linked list is O(n) — there's no way to "jump" to the 5th node, you must walk the pointers one at a time starting from the head. But if you already hold a reference to a specific node, inserting or deleting right there is O(1): you just rewrite a couple of pointers, with no shifting of other elements required (unlike an array, where inserting in the middle means shifting every subsequent element).

# Inserting after a known node -- O(1), just pointer rewiring
def insert_after(node, value):
    new_node = Node(value)
    new_node.next = node.next
    node.next = new_node

Output:

No console output — the point is that this function does a fixed, constant amount of work no matter how long the list is, unlike an array's O(n) shift.

When to Reach for a Linked List

Linked lists shine when you're frequently inserting or removing elements at the front or in the middle, and you don't need random access by index — think of implementing a queue or managing a sequence where items are constantly added and removed. For everything else — especially anything requiring frequent lookups by position — a dynamic array usually wins, both for raw speed (better memory locality, no pointer-chasing) and simplicity.

---