Linked Lists

November 18, 2025

#linked-list #data-structures #algorithms #interviewing

Introduction

A linked list is a linear data structure made of nodes where each node stores a value and a reference (a “link”) to the next node. Unlike arrays, linked lists do not store elements contiguously in memory. This gives them different performance characteristics and trade-offs.

If you are new to time and space complexity, start with our guide to Big-O Notation. You may also want to review Arrays to understand how linked lists compare.

Linked lists excel at fast insertions and deletions at known positions (especially at the head) without shifting elements, but random access by index is slow.

Why use a linked list?

Choose a linked list when:

You need frequent insertions or deletions near the head or at known nodes: O(1) when you already have a reference to the node.
Memory reallocation costs of resizing arrays are undesirable.
You are building other structures (e.g., stacks, queues, adjacency lists) where linked lists are a good fit.

Avoid a linked list when:

You need fast random access by index. Arrays provide O(1) index access; linked lists require O(n) traversal.
Cache locality matters a lot; arrays are typically more cache-friendly due to contiguous memory.

Flavors of linked lists

Singly linked list: Each node has value and next.
Doubly linked list (DLL): Each node has value, prev, and next for bidirectional traversal.
Circular linked list: The tail’s next points back to the head (and for DLL, head’s prev points to tail), forming a loop.

This tutorial focuses on the singly linked list, then discusses variations.

Core operations and complexity

Access kth element by index: O(n) — must traverse from head.
Search by value: O(n) — scan nodes until found.
Insert at head: O(1) — create a node and point it to the old head.
Insert after a given node: O(1) — if you have the node reference.
Delete head: O(1) — move head to head.next.
Delete after a given node: O(1) — if you have the previous node reference.
Insert at tail: O(1) if you maintain a tail pointer; otherwise O(n) to find the tail.

Singly linked list implementation

Below are minimal singly linked list implementations providing: insert at head, search, delete (by value), and iteration/printing.

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null; // optional: helps O(1) tail insert
    this.size = 0;
  }

  insertHead(value) {
    const node = new ListNode(value, this.head);
    this.head = node;
    if (!this.tail) this.tail = node;
    this.size++;
  }

  insertTail(value) {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }

  search(target) {
    let curr = this.head;
    while (curr) {
      if (curr.value === target) return curr; // return node
      curr = curr.next;
    }
    return null;
  }

  delete(value) {
    if (!this.head) return false;
    if (this.head.value === value) {
      this.head = this.head.next;
      if (!this.head) this.tail = null; // list became empty
      this.size--;
      return true;
    }
    let prev = this.head;
    let curr = this.head.next;
    while (curr) {
      if (curr.value === value) {
        prev.next = curr.next;
        if (curr === this.tail) this.tail = prev;
        this.size--;
        return true;
      }
      prev = curr;
      curr = curr.next;
    }
    return false;
  }

  toArray() {
    const out = [];
    let curr = this.head;
    while (curr) {
      out.push(curr.value);
      curr = curr.next;
    }
    return out;
  }
}

// Example usage
const list = new LinkedList();
list.insertHead(3);
list.insertHead(2);
list.insertTail(4);
console.log(list.toArray()); // [2, 3, 4]
console.log(!!list.search(3)); // true
list.delete(2);
console.log(list.toArray()); // [3, 4]

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # optional tail pointer
        self.size = 0

    def insert_head(self, value):
        node = ListNode(value, self.head)
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def insert_tail(self, value):
        node = ListNode(value)
        if self.head is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def search(self, target):
        curr = self.head
        while curr is not None:
            if curr.value == target:
                return curr
            curr = curr.next
        return None

    def delete(self, value):
        if self.head is None:
            return False
        if self.head.value == value:
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            self.size -= 1
            return True
        prev, curr = self.head, self.head.next
        while curr is not None:
            if curr.value == value:
                prev.next = curr.next
                if curr is self.tail:
                    self.tail = prev
                self.size -= 1
                return True
            prev, curr = curr, curr.next
        return False

    def to_list(self):
        out = []
        curr = self.head
        while curr is not None:
            out.append(curr.value)
            curr = curr.next
        return out

# Example usage
lst = LinkedList()
lst.insert_head(3)
lst.insert_head(2)
lst.insert_tail(4)
print(lst.to_list())      # [2, 3, 4]
print(lst.search(3) is not None)  # True
lst.delete(2)
print(lst.to_list())      # [3, 4]

class ListNode {
    int value;
    ListNode next;
    ListNode(int value) { this.value = value; }
    ListNode(int value, ListNode next) { this.value = value; this.next = next; }
}

public class LinkedList {
    private ListNode head;
    private ListNode tail;
    private int size = 0;

    public void insertHead(int value) {
        head = new ListNode(value, head);
        if (tail == null) tail = head;
        size++;
    }

    public void insertTail(int value) {
        ListNode node = new ListNode(value);
        if (head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
    }

    public ListNode search(int target) {
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.value == target) return cur;
        }
        return null;
    }

    public boolean delete(int value) {
        if (head == null) return false;
        if (head.value == value) {
            head = head.next;
            if (head == null) tail = null;
            size--;
            return true;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.value == value) {
                prev.next = cur.next;
                if (cur == tail) tail = prev;
                size--;
                return true;
            }
            prev = cur;
            cur = cur.next;
        }
        return false;
    }

    public int[] toArray() {
        int[] out = new int[size];
        int i = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) out[i++] = cur.value;
        return out;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertHead(3);
        list.insertHead(2);
        list.insertTail(4);
        System.out.println(java.util.Arrays.toString(list.toArray())); // [2, 3, 4]
        System.out.println(list.search(3) != null); // true
        list.delete(2);
        System.out.println(java.util.Arrays.toString(list.toArray())); // [3, 4]
    }
}

Using a linked list for a queue

Queues are often implemented using linked lists to achieve O(1) enqueue and dequeue with a head and tail pointer.

class Queue {
  constructor() { this.list = new LinkedList(); }
  enqueue(x) { this.list.insertTail(x); }
  dequeue() {
    if (!this.list.head) return null;
    const val = this.list.head.value;
    this.list.delete(val); // optimized version would pop head directly
    return val;
  }
}

class Queue:
    def __init__(self):
        self.list = LinkedList()
    def enqueue(self, x):
        self.list.insert_tail(x)
    def dequeue(self):
        if self.list.head is None:
            return None
        val = self.list.head.value
        self.list.delete(val)  # a specialized pop_head method would be O(1)
        return val

class QueueLL {
    private final LinkedList list = new LinkedList();
    public void enqueue(int x) { list.insertTail(x); }
    public Integer dequeue() {
        // For production, add a dedicated popHead method on LinkedList.
        int[] before = list.toArray();
        if (before.length == 0) return null;
        int val = before[0];
        list.delete(val);
        return val;
    }
}

Variations and extensions

Doubly linked list: Add prev to each node. Pros: O(1) delete with node reference and easier bidirectional traversal. Cons: more memory, more pointer updates.
Circular linked list: Useful for round-robin scheduling; the last node links to the first.
Sentinel (dummy) nodes: Simplify edge cases by using a dummy head and/or tail.

Pitfalls and edge cases

Forgetting to update tail when deleting the last node.
Memory management: In manual-memory languages, ensure nodes are freed to avoid leaks.
Infinite loops in circular lists: Ensure termination conditions are correct.
Off-by-one errors when inserting/deleting near the head or tail.

When to prefer arrays over linked lists

You need frequent random reads by index.
Data fits comfortably in memory and resizing costs are acceptable.
You benefit from CPU cache locality and vectorized operations.

For sorted arrays where you frequently search, consider Binary Search.

Practice prompts

Implement a popHead() method that removes and returns the head in O(1) time.
Implement a doubly linked list with addFirst, addLast, remove(Node), and find.
Detect a cycle in a linked list using Floyd’s Tortoise and Hare algorithm. Return the node where the cycle begins.
Merge two sorted singly linked lists into one sorted list in O(n + m) time.
Reverse a singly linked list iteratively, then recursively. Analyze time/space complexity.

Complexity summary

Time:
- Search: O(n)
- Insert at head/tail (with tail pointer): O(1)
- Delete at head: O(1); delete by value with traversal: O(n)
Space:
- O(n) for node storage; each node stores data plus pointer(s)