Linked List Random Access

Linked lists cannot jump to index i. They must walk from the head, which is why arrays win for most indexed reads.

The key limitation of a linked list is the absence of random access. Getting item i requires starting at the head and following i pointers.

With an array, arr[999] is direct. With a linked list, get(999) must visit node after node until it reaches that position.

class LinkedList {
  constructor() {
    this.head = null;
  }
 
  get(index) {
    let current = this.head;
    let i = 0;
 
    while (current) {
      if (i === index) return current.value;
      current = current.next;
      i++;
    }
 
    return undefined;
  }
}
 
// Linked list: O(n), must walk from the head
console.log(list.get(999));
 
// Array: O(1), direct indexed read
console.log(arr[999]);

In production

Pointer chasing means following references that may be scattered across memory. It hurts CPU cache locality, so arrays beat linked lists for most reads in V8. A real linked-list use case is an LRU cache, where a doubly linked list can move a known node in O(1).

Enjoyed this? Get more software craft delivered to your inbox.