Linked List

In coding interviews, linked lists often show up when the goal is to support frequent insertions and deletions without paying the shifting cost that arrays require. Arrays store elements in contiguous memory, which makes indexing fast (arr[i] is $O(1)$O(1)). But inserting or deleting in the middle typically involves shifting many elements, which can be costly.

A linked list takes a different approach: it stores values in separate nodes connected by pointers (links). This design allows the list to grow and shrink naturally, and operations like inserting at the head can be done in $O(1)$O(1) time by rewiring a couple of links instead of moving elements.

The trade-off is that linked lists don’t support fast indexing, since reaching an element requires traversal from the head.

What is a linked list?

A linked list is a linear data structure where elements are stored in nodes. Each node contains:

• Data: The value (e.g., 10, "cat")
• Next: A link (pointer/reference) to the next node.

class Node:
    def __init__(self, data):
        self.data = data      # stores the value (e.g., 10, "cat")
        self.next = None      # points to the next node (None means end)

Instead of living next to each other in memory (like an array), nodes can be stored in different locations and are connected through these links.

The linked list begins at the head (the first node). To move through the list, you follow links from one node to the next. In a singly linked list, traversal is forward-only, and the list ends when a node’s next points to NULL.

Because a linked list is essentially a chain of connected nodes, it behaves differently from arrays, especially in how it grows and how you access items.

Key characteristics of a linked list

• Built from connected nodes: Every element is a node, and the structure depends on links rather than physical adjacency in memory.
• Dynamic growth: It can grow/shrink easily by adding or removing nodes, no resizing or copying required.
• Sequential access (no direct indexing): You can’t jump to list[i]; you must traverse from the head node step by step.
• Fast insert/delete when position is known: Once you’re at the correct node (or have a pointer to it), insertion/deletion is usually just pointer updates, no shifting.
• Extra memory overhead: Each node stores link(s) in addition to its data.
• Weaker cache performance: Nodes are scattered in memory, so scanning can be slower than arrays in practice.

Types of linked lists

The main types are singly linked lists , doubly linked lists, and circular linked lists.

Singly linked list

A singly linked list is made of nodes where each node points only to the next node. It moves in one direction (forward) starting from the head. The last node points to NULL, so it’s simple and more memory-efficient than other linked list types.

Doubly linked list

A doubly linked list has nodes with two links: next and prev. This allows traversal both forward and backward through the list. Deleting a node is easier when you already have it, but it uses more memory and needs more pointer updates.

Circular linked list

A circular linked list connects the last node back to the head instead of NULL. Because of this, there is no true “end” and traversal can keep cycling. It’s useful when you need continuous repetition, such as in scheduling.

Advantages and Disadvantages

Common operations

Traversal

As linked list nodes are scattered in memory, traversal must begin at the head and continue by following pointers from one node to the next. The typical logic is to use a temporary pointer (often called current), start it at the head, perform your action (like printing the node’s data), and then move it to current.next. You stop when current becomes NULL, which signals that you’ve reached the end of the list.

Search

Searching in a linked list is basically traversal with a specific target in mind. You move through the list using a current pointer and compare the data in each node with the value you’re looking for; if it matches, you return that node (or its position), and if not, you continue to the next node. In the worst case, you may need to check every node, so the time complexity is O(n).

1 / 5

Insertion

The beauty of a linked list is that you don’t have to move the data; you just “re-wire” the connections.

• At the head: The fastest insertion. Create a new node, point its next to the current head, and then declare the new node as the new head. $O(1)$O(1)
• At the tail: You must traverse the entire list to find the last node (where next is NULL), then point that node to your new entry.
• After a Specific Node: You take the next pointer of the “previous” node and give it to the new node, then point the “previous” node to your new one.

1 / 6

Deletion

To delete a node, you effectively “skip” it so that nothing points to it anymore.

• Delete head: Simply move the head pointer to the second node in the list. The original first node is then orphaned and cleaned up by memory management.
• Delete in the middle: This is the trickiest part of a singly linked list. To delete node B, you must find node A (the one before it) and change A’s pointer to skip B and point directly to C.

1 / 8

Time complexity (Big-O)

Singly linked list: example in Python

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


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

    def is_empty(self):
        return self.head is None

    # O(1)
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # O(n) unless you keep a tail pointer
    def insert_at_tail(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            return

        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

    # O(n)
    def search(self, target):
        cur = self.head
        while cur:
            if cur.data == target:
                return True
            cur = cur.next
        return False

    # O(n)
    def delete_first(self, target):
        if self.is_empty():
            return False

        # target is at head
        if self.head.data == target:
            self.head = self.head.next
            return True

        prev = self.head
        cur = self.head.next
        while cur:
            if cur.data == target:
                prev.next = cur.next
                return True
            prev = cur
            cur = cur.next

        return False

    # O(n)
    def to_list(self):
        result = []
        cur = self.head
        while cur:
            result.append(cur.data)
            cur = cur.next
        return result

    def __str__(self):
        return " -> ".join(map(str, self.to_list())) + " -> None"


if __name__ == "__main__":
    ll = LinkedList()

    print("Initially:")
    print("List:", ll)
    print("is_empty:", ll.is_empty())
    print("-" * 70)

    ll.insert_at_head(3)
    print("After insert_at_head(3):")
    print("List:", ll)
    print("-" * 70)

    ll.insert_at_head(2)
    print("After insert_at_head(2):")
    print("List:", ll)
    print("-" * 70)

    ll.insert_at_head(1)
    print("After insert_at_head(1):")
    print("List:", ll)  # 1 -> 2 -> 3 -> None
    print("-" * 70)

    ll.insert_at_tail(4)
    print("After insert_at_tail(4):")
    print("List:", ll)  # 1 -> 2 -> 3 -> 4 -> None
    print("-" * 70)

    print("Search 3:", ll.search(3))
    print("Search 99:", ll.search(99))
    print("-" * 70)

    deleted = ll.delete_first(2)
    print("delete_first(2) returned:", deleted)
    print("After delete_first(2):")
    print("List:", ll)  # 1 -> 3 -> 4 -> None
    print("-" * 70)

    deleted = ll.delete_first(99)
    print("delete_first(99) returned:", deleted)
    print("List:", ll)

When should you use a linked list?

• Use a linked list when you need frequent insertions/deletions, especially at the head or in the middle (once you’re already there).
• Use it when the size changes often and you want easy growth/shrink without resizing.
• Avoid it when you need fast indexing like arr[i] (linked lists require traversal, $O(n)$O(n)).
• Prefer arrays/Python lists when your work is mostly reading/scanning and you want better cache performance.

Real-world applications

• OS scheduling (round-robin): uses circular linked lists to cycle through tasks.
• Browser history / Undo–Redo: doubly linked list style navigation backward/forward.
• LRU cache: doubly linked list + hashmap for fast updates and eviction.
• Hash tables (chaining): collisions stored as a linked list in each bucket.
• Memory management: “free lists” track available memory blocks using linked lists.