Data structures & algorithms3 min

Linked Lists

A Linked List is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a Node) contains two things:

The actual Data.
A Pointer (or reference) to the next node in the sequence.

Memory Layout

Unlike arrays, where memory is a solid block, linked list nodes are scattered randomly throughout the computer's RAM. They are chained together purely via memory addresses.

Types of Linked Lists

Singly Linked List: Each node only points forward to the next node. You can only traverse the list in one direction.
Doubly Linked List: Each node has a next pointer AND a prev (previous) pointer. You can traverse forward and backward.
Circular Linked List: The tail node's next pointer points back to the head node, creating an infinite loop.

Time Complexity (Singly Linked List)

Operation	Time Complexity	Explanation
Access `list[i]`	$O(N)$	You cannot jump directly to an index. You must start at the `head` and traverse $i$ times.
Search	$O(N)$	Must check every node one by one.
Insert at Head	$O(1)$	Just create a new node and point its `next` to the current `head`.
Delete at Head	$O(1)$	Just update `head = head.next`.
Insert/Delete in Middle	$O(N)$	The actual insertion is $O(1)$ (rewiring pointers), but finding the middle node takes $O(N)$ time.

Linked List vs Array

Arrays are vastly superior for reading data because of $O(1)$ access time and excellent CPU cache locality (since memory is contiguous).
Linked Lists are superior for frequent insertions/deletions at the beginning (or anywhere, if you already hold a pointer to that node) because no shifting of elements is required.

Implementation Example (Singly Linked List)

typescript

class ListNode {
  val: number;
  next: ListNode | null;
  
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
  }
}

class LinkedList {
  head: ListNode | null = null;

  // O(1) Insertion at the front
  public prepend(val: number): void {
    const newNode = new ListNode(val);
    newNode.next = this.head;
    this.head = newNode;
  }

  // O(N) Traversal to print
  public printList(): void {
    let curr = this.head;
    let output = "";
    while (curr !== null) {
      output += `${curr.val} -> `;
      curr = curr.next;
    }
    console.log(output + "null");
  }
}

// Usage
const list = new LinkedList();
list.prepend(30);
list.prepend(20);
list.prepend(10);
list.printList(); // 10 -> 20 -> 30 -> null

Common Linked List Algorithms

Fast & Slow Pointers (Floyd's Tortoise and Hare)

Used to find the middle of a linked list or detect a cycle (loop). You move a "slow" pointer 1 step at a time, and a "fast" pointer 2 steps at a time. If there is a cycle, the fast pointer will eventually overlap the slow pointer. If there is no cycle, the fast pointer will reach null, and the slow pointer will be exactly in the middle.

typescript

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;          // Move 1 step
    fast = fast.next.next;      // Move 2 steps
    
    if (slow === fast) {
      return true; // The hare caught the tortoise! Cycle detected.
    }
  }
  return false;
}