Exploring Linked List Data Structure in TypeScript

Arrays have a dirty secret: inserting at the beginning is O(n). Every element has to shift over. With a linked list, it's O(1).

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node. There's no contiguous memory, no shifting, no resizing. You trade random access for efficient insertion and deletion.

Singly Linked List

Each node points to the next. The last node points to null.

class ListNode<T> {
  data: T;
  next: ListNode<T> | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList<T> {
  head: ListNode<T> | null;
  private length: number;

  constructor() {
    this.head = null;
    this.length = 0;
  }

  prepend(data: T): void {
    const node = new ListNode(data);
    node.next = this.head;
    this.head = node;
    this.length++;
  }

  append(data: T): void {
    const node = new ListNode(data);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }

  find(data: T): ListNode<T> | null {
    let current = this.head;
    while (current) {
      if (current.data === data) return current;
      current = current.next;
    }
    return null;
  }

  size(): number {
    return this.length;
  }
}

Performance Comparison with Arrays

*Amortized for dynamic arrays. **O(1) if you maintain a tail pointer.

Variants

Doubly linked list: Each node has a prev and next pointer. Traversal works in both directions. Deletion of a known node becomes O(1) because you don't need to find the previous node first.

Circular linked list: The last node points back to the first. Useful for round-robin scheduling or cyclic buffers.

When to Use Linked Lists

• Frequent insertions/deletions at arbitrary positions. If you're constantly adding and removing elements from the front or middle, linked lists outperform arrays.
• Unknown size at compile time. Linked lists grow one node at a time. No resizing, no wasted capacity.
• Implementing stacks and queues. Both map naturally to linked list operations.
• Memory fragmentation scenarios. Linked lists allocate nodes independently, which can be an advantage when contiguous blocks are unavailable.

When NOT to Use Linked Lists

• Random access matters. You can't jump to index 500 in O(1). You have to walk there node by node.
• Cache performance matters. Arrays live in contiguous memory, which plays well with CPU caches. Linked list nodes are scattered across memory, causing frequent cache misses. In practice, this makes arrays faster for sequential access even when the algorithmic complexity says otherwise.

The linked list isn't dead, but modern hardware favors arrays in most scenarios. Use linked lists when the insertion/deletion pattern genuinely demands it, not as a default.