Data StructuresBeginner12 min readUpdated March 2025

Linked Lists

A linked list is a linear data structure where elements (nodes) are stored in non-contiguous memory and connected via pointers. Unlike arrays, linked lists excel at O(1) insertion and deletion at known positions but sacrifice O(1) random access.

Linked List Structure

A linked list consists of nodes, where each node contains: 1. Data — The value stored in the node 2. Next pointer — A reference to the next node in the list

The list is accessed through a head pointer that points to the first node. The last node's next pointer is null (None), marking the end.

Types of linked lists: - Singly Linked List — Each node has one pointer (next) - Doubly Linked List — Each node has two pointers (next and prev) - Circular Linked List — The last node points back to the head

Singly vs Doubly Linked Lists

Choosing between singly and doubly linked lists involves tradeoffs:

Singly Linked List — Less memory (one pointer per node). Can only traverse forward. Deletion requires knowing the previous node.
Doubly Linked List — More memory (two pointers per node). Can traverse both directions. O(1) deletion given a node reference. Used in LRU Cache, browser history.
Circular Linked List — Last node points to head. Useful for round-robin scheduling, circular buffers.
Python's collections.deque is implemented as a doubly linked list, providing O(1) append and popleft.

Implementing a Doubly Linked List

A complete doubly linked list implementation with all core operations:

python

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def append(self, data):
        """Add to end - O(1)"""
        node = Node(data)
        if self.tail is None:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        self._size += 1

    def prepend(self, data):
        """Add to front - O(1)"""
        node = Node(data)
        if self.head is None:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        self._size += 1

    def delete(self, node):
        """Delete a given node - O(1) given the node"""
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next   # Deleting head
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev   # Deleting tail
        self._size -= 1

    def find(self, data):
        """Search for a value - O(n)"""
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None

    def __repr__(self):
        result = []
        current = self.head
        while current:
            result.append(str(current.data))
            current = current.next
        return " <-> ".join(result)

# Test
dll = DoublyLinkedList()
for val in [1, 2, 3, 4, 5]:
    dll.append(val)
print(dll)          # 1 <-> 2 <-> 3 <-> 4 <-> 5

node = dll.find(3)
dll.delete(node)
print(dll)          # 1 <-> 2 <-> 4 <-> 5

Classic Linked List Problems

Key algorithmic patterns for linked lists:

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# ---- Reverse a Linked List - O(n) time, O(1) space ----
def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev   # New head

# ---- Detect Cycle (Floyd's Algorithm) ----
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# ---- Find Middle Node ----
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # slow is at middle

# ---- Merge Two Sorted Lists ----
def merge_sorted(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 or l2
    return dummy.next

Key Takeaways

Linked lists store nodes in non-contiguous memory connected by pointers — no random access.
Insertion and deletion at a known position are O(1); searching is O(n).
Doubly linked lists allow O(1) deletion given a node reference — used in LRU Cache implementations.
Floyd's cycle detection (slow/fast pointers) detects cycles in O(n) time with O(1) space.
Use linked lists when frequent insertion/deletion is needed; use arrays for frequent random access.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com