A linked list rebuilt in JavaScript

A linked list is one of those structures that looks trivial in a diagram and becomes surprisingly fiddly in code. Each node holds a value and a reference to the next node. The list itself holds a reference to the first node, and sometimes the last. The idea is simple. The edge cases are where the learning lives.

The shape of the class

A useful implementation starts with the operations a caller actually needs. Size and emptiness are basic. Reading a value at an index, adding to the front or back, removing from either end, and inserting or erasing at a position are enough to exercise the pointer work. A reverse operation and a lookup from the end add a little more depth without turning the exercise into a library.

The first version can be built with a head reference only. That makes insertion at the front cheap and removal from the back more expensive because the list has to walk to the node before the tail. Keeping a tail reference improves the common case, but it adds another pointer that must stay correct after every operation. Neither choice is universally right. The data structure should reflect the operations the program uses most.

Edge cases are the curriculum

Removing the only node is different from removing a node in the middle. Inserting at the end is different from inserting into an empty list. Reversing a list with one node should not be a special case, but a naive loop can easily make it one. The best way to find those gaps is to write small tests before the implementation feels finished. A console demo can hide the cases that matter.

JavaScript adds its own details. A class field is not the same as a private field, and an object reference can be copied without copying the node. A method that returns a removed value should not also leave a dangling reference in the list. These are not academic concerns. They are the source of bugs that appear only after the list has been used for a while.

Notebook note: data structure exercises are really state management exercises. The pointer is the state, and every operation has to leave it coherent.

Complexity in plain language

Access by index is linear because the list must be walked. Insertion and removal at a known node are constant time, while finding that node is linear. A head insertion is constant. These facts are easy to recite and much easier to remember after implementing them. The implementation turns the complexity table into a physical experience.

The larger benefit is confidence. A linked list can look intimidating because of the repeated next references. Writing one makes the pattern ordinary. The next data structure will still have edge cases, but the process for finding them is no longer a mystery.