Linked lists are still one of the most important data structures to understand because they show up everywhere: stacks, queues, adjacency lists in graphs, and many classic interview problems. This update expands the original post with clearer definitions, trade-offs, time complexity, and modern JavaScript examples.

What is a linked list?

A linked list is a linear collection of nodes, where each node stores data and a reference (pointer) to another node. Unlike arrays, nodes are not stored contiguously in memory. Instead, each node links to the next one, which means you traverse the list one step at a time.

Core terms

  • Node: A container holding value and a next reference (and sometimes a prev).
  • Head: The first node in the list.
  • Tail: The last node in the list (often tracked for O(1) appends).

Types of linked lists

  1. Singly linked list: Each node points to the next node.
  2. Doubly linked list: Each node points to the next and previous nodes. This supports deque-like operations in constant time when head and tail are maintained.
  3. Circular linked list: The tail points back to the head, forming a loop.

When to use a linked list (and when not to)

Linked lists shine when you frequently insert or delete elements in the middle of a list and you already have a reference to the node. In that case, insertions and deletions can be done in constant time.

They are weaker when you need random access by index: you must traverse from the head to reach the ith node, which is linear time.

Time complexity summary

These assume you maintain head and tail references, and that you already have a reference to the node where the operation occurs.

OperationTime
Access by indexO(n)
Search by valueO(n)
Insert/remove at headO(1)
Insert/remove after a known nodeO(1)
Append at tail (with tail pointer)O(1)

A clean JavaScript implementation

Below is a practical singly linked list you can paste into a project or a coding exercise. It includes the most common operations you will need.

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

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

  append(value) {
    const node = new Node(value);

    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length += 1;
    return this;
  }

  prepend(value) {
    const node = new Node(value, this.head);
    this.head = node;

    if (!this.tail) {
      this.tail = node;
    }

    this.length += 1;
    return this;
  }

  removeFirst() {
    if (!this.head) return null;

    const removed = this.head;
    this.head = this.head.next;

    if (!this.head) {
      this.tail = null;
    }

    this.length -= 1;
    return removed.value;
  }

  insertAfter(node, value) {
    if (!node) return null;

    const newNode = new Node(value, node.next);
    node.next = newNode;

    if (this.tail === node) {
      this.tail = newNode;
    }

    this.length += 1;
    return newNode;
  }

  find(predicate) {
    let current = this.head;
    while (current) {
      if (predicate(current.value)) return current;
      current = current.next;
    }
    return null;
  }

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

Quick example: queue with O(1) enqueue/dequeue

A singly linked list with head and tail makes a clean queue implementation.

class Queue {
  constructor() {
    this.list = new LinkedList();
  }

  enqueue(value) {
    this.list.append(value);
  }

  dequeue() {
    return this.list.removeFirst();
  }

  peek() {
    return this.list.head ? this.list.head.value : null;
  }
}

References