Building a Linked List in JavaScript to Understand References

Introduction

A linked list is a chain of objects. Each object is called a node. A node stores a value and a reference to the next node, so the list is built by connecting objects rather than placing all values beside each other in one array.

A reference is a value that points to an object. It does not copy the whole object. For example, if one node stores a reference to another node, following that reference allows the program to reach the existing next node.

JavaScript arrays already grow dynamically and provide convenient methods for inserting, removing, and searching. Building a linked list is still a useful exercise because it makes references visible. Every operation has to identify the first node, the last node, and the nextNode reference that must change. It must also handle the empty-list and one-node cases correctly.

This article is based on the current main branch of the Linked-List repository. The repository contains a general LinkedList, a similar KeyedLinkedList, and a small main.js demonstration. The walkthrough below focuses on the general list and distinguishes what the README documents from behaviour reproduced from the source.

The list object and the node objects have different jobs

The project represents the overall collection with LinkedList and each element with a separate Node:

export class LinkedList {
  #head = null;
  #tail = null;

  get head() {
    return this.#head;
  }

  get tail() {
    return this.#tail;
  }

  createNode(value, nextNode) {
    return new Node(value, nextNode);
  }
}

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

The list object stores the private #head and #tail references. A node stores a value and a nextNode reference. The nodes do not know which list contains them, and they do not refer backward to a previous node. A list with only forward links is called a singly linked list.

In the illustrated state:

• #head refers to the node containing owl;
• each node's nextNode refers to the following node;
• #tail refers to the same final node reached by traversal; and
• the tail node's nextNode is null.

Assigning currentNode = currentNode.nextNode does not copy a node. It changes the object to which the local variable refers. Similarly, assigning previousNode.nextNode = newNode changes the link stored in an existing node. This is the main reference idea used throughout the implementation: the code changes connections between existing objects instead of shifting every later value as an array operation might do.

Conditions that keep the list correct

Several conditions should remain true after every operation. These conditions describe a valid list:

1. An empty list has both #head === null and #tail === null.
2. A non-empty list has non-null head and tail references.
3. Starting at the head and repeatedly following nextNode eventually reaches the tail.
4. The tail's nextNode is null.
5. Every node counted as part of the list is reachable from the head.

These are not extra features. They define what it means for the representation to be internally consistent. An operation can appear to produce the right printed value while still breaking one of these conditions.

Why an empty list needs special handling

Appending to a non-empty list can link the current tail to a new node and then move the tail reference:

this.#tail.nextNode = newNode;
this.#tail = newNode;

That cannot work when #tail is null. The repository's append handles the empty case by making both fields refer to the first node:

append(value) {
  const newNode = this.createNode(value, null);

  if (this.#tail === null) {
    this.#head = this.#tail = newNode;
  } else {
    this.#tail.nextNode = newNode;
    this.#tail = newNode;
  }
}

Because the class stores a tail reference, it does not need to walk from the head to append. The operation is constant-time with respect to the number of nodes.

prepend constructs a node whose nextNode is the old head. On an empty list, it again sets both head and tail. Otherwise, only the head reference changes:

prepend(value) {
  const newNode = this.createNode(value, this.#head);

  if (this.#head === null) {
    this.#head = this.#tail = newNode;
  } else {
    this.#head = newNode;
  }
}

The old first node is not moved or copied. The new node simply refers to it.

Traversal is the recurring operation

Most other methods start with the same pattern:

let currentNode = this.#head;

while (currentNode !== null) {
  // inspect the current node
  currentNode = currentNode.nextNode;
}

The project uses traversal to implement:

• size(), which counts every reachable node;
• at(index), which returns the node at a zero-based index;
• contains(value), which returns a Boolean;
• find(value), which returns the first matching index or null;
• toString(), which builds ( value ) -> ... -> null; and
• parts of insertAt, removeAt, and pop.

The loop invariant is that currentNode is either the next reachable node to process or null after the tail. Advancing exactly once per iteration ensures traversal progresses toward its stopping condition.

Lookup and index validation in the current code

The implementation's at method validates the index by calling size():

at(index) {
  if (index > this.size() - 1 || index < 0) return null;

  let currentNode = this.#head;
  let i = 0;

  while (index > i) {
    currentNode = currentNode.nextNode;
    i++;
  }

  return currentNode;
}

Negative and too-large indices return null. A valid lookup may traverse the list twice: once inside size() and again to reach the index. Two linear passes are still O(n), but the repeated work is an implementation detail worth noticing.

The related methods do not all apply the same validation policy:

The high-index checks are documented behaviour in the repository. The negative-index TypeError is demonstrated behaviour from running the current source. As a design judgement, a collection API is easier to use when related methods share one deliberate invalid-index policy—return a sentinel, throw a RangeError, or report failure consistently.

Inserting by changing one link

For a non-zero valid index, insertAt records two references during traversal:

• targetNode, the node currently at the requested index; and
• prevNode, the node immediately before it.

The final update is:

prevNode.nextNode = this.createNode(value, targetNode);

The new node points to the old target, and the previous node is redirected to the new node.

For insertAt("fox", 2), dog.nextNode previously referred to the cat node. Afterwards it refers to the new fox node, while fox.nextNode preserves access to cat. No later node has to be copied or shifted.

The current method deliberately does not insert at index === size for a non-empty list, so it is not a replacement for append. Index zero is a special case that works through prepend, including on an empty list.

Removing the final node with pop

In this repository, pop() removes the tail, not the head. That distinction is important because a singly linked node has no reference to its predecessor.

The method handles three cases:

1. If the list is empty, return without changing anything.
2. If the head is also the tail, set both fields to null.
3. Otherwise, traverse until currentNode.nextNode is the tail, set that predecessor's nextNode to null, and move #tail to the predecessor.

The core loop looks one link ahead:

while (currentNode.nextNode.nextNode !== null) {
  currentNode = currentNode.nextNode;
}

currentNode.nextNode = null;
this.#tail = currentNode;

Although the class stores the tail, removing it remains linear-time. The tail reference identifies the last node, but a singly linked list cannot move backward to find the previous node. Traversal from the head is required.

Removing at an index

removeAt(index) first computes the size, then separates head, tail, and middle removal:

• index zero advances #head to #head.nextNode;
• the last index delegates to pop(); and
• a middle removal redirects prevNode.nextNode to targetNode.nextNode.

The middle update bypasses the target:

prevNode.nextNode = targetNode.nextNode;

Once no reachable node refers to the removed node, JavaScript can reclaim it when nothing else refers to it. The code does not manually free memory as C code would.

A reproduced single-node edge case

The README says that removing the final node correctly updates both head and tail. That is true when the final node is removed through pop(). The current removeAt(0) branch, however, changes only the head:

if (index === 0) {
  this.#head = this.#head.nextNode;
  return;
}

Running this example against the current src/linked-list.js produces the annotated results:

const list = new LinkedList();
list.append("only");
list.removeAt(0);

console.log(list.head);        // null
console.log(list.tail.value);  // "only"

list.append("new");
console.log(list.toString());  // "null"

This is demonstrated behaviour, not an assumption: after removeAt(0), the list reports an empty traversal but retains a stale tail. A later append links from that unreachable tail, leaving the head as null.

The broken invariant is precise: an empty list should have both head and tail set to null. A robust head-removal branch must also clear the tail when advancing the head empties the list, or it can delegate the one-node case to logic that already clears both fields. That is a design recommendation; the repository has not been modified as part of this article.

Complexity of the implemented methods

Let n be the number of nodes reachable from the head. These bounds describe the current LinkedList implementation.

The list's storage is O(n): each value is wrapped in one node carrying one nextNode reference, while the list itself stores two references. This does not include memory owned by the values themselves.

A stored size counter could make size() constant-time and remove the validation pass from indexed methods, but every insertion and removal would then have another invariant to maintain. That tradeoff is a design decision rather than an automatic improvement.

The keyed companion list

The repository also contains KeyedLinkedList and KeyedNode. Its structure and most operations mirror the general list, but a node stores key, value, and nextNode. contains and find compare keys, and toString prints both key and value.

That keyed version later supports thinking about separate chaining in a hash map: a bucket can hold multiple key-value entries connected by next references. The hash-map article should still inspect that repository's actual integration instead of assuming it imports this class unchanged.

What this exercise teaches when arrays are easier

The Odin Project's linked-list lesson explicitly notes that JavaScript arrays do not have the fixed-size limitation that motivates linked lists in some lower-level settings. For ordinary application code, an array is often clearer and benefits from built-in iteration, indexing, and optimized engine support.

The value of this exercise is the mental model:

• object variables hold references;
• changing a reference changes reachability;
• insertion and removal depend on reconnecting the correct neighboring nodes;
• fast access to one boundary does not imply fast access to its predecessor; and
• empty and one-node states test whether the representation invariants are complete.

Those ideas transfer directly to trees, graphs, caches, queues, and ownership reasoning. Open Data Structures develops the same connection between representation choices and operation costs across multiple structures.

The repository's main.js provides manual usage examples rather than an automated test suite. I reran the single-node stale-tail and negative-index cases described here against the current source with Node.js v22.23.1; these reproductions are not performance tests.

Key takeaways

• LinkedList owns the head and tail references; each Node owns a value and one forward link.
• An empty list needs both head and tail set to null.
• In a non-empty list, the stored tail must be reachable from the head and its nextNode must be null.
• The stored tail makes append O(1), but pop remains O(n) because the list has no backward links.
• Traversal powers size, indexed lookup, searching, string conversion, and most indexed updates.
• Insertion redirects the previous node to a new node while preserving a link to the old target.
• Removal bypasses a target by linking its predecessor to its successor.
• The current methods use inconsistent negative-index handling, and removeAt(0) leaves a stale tail when removing the only node.
• JavaScript arrays are usually more convenient, but linked lists expose reference and invariant reasoning that carries into more complex structures.

Sources

• Author repository: Linked-List
• Repository source: linked-list.js
• Repository source: keyed-linked-list.js
• The Odin Project: Linked Lists
• Open Data Structures