Objects that point at the next object

A linked list is small objects, each holding a value and a reference to the next one, ending at null. There is no index and no length.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

An array is better for almost everything you will write, so the reason to know this is the interview and the idea underneath it: you buy cheap insertion anywhere by giving up the ability to jump to a position.

How to think about it

Every walk has the same skeleton: start at the head, do the work, move to node.next, stop when the node is null. Write the skeleton first.

Worked example

const node = (value, next = null) => ({ value, next });

A node is an ordinary object; no class is needed.

const head = node('a', node('b', node('c')));

Built inside out: c first.

const out = [];

Somewhere to collect.

let cur = head;

The walking variable. let, not const: it moves.

while (cur !== null) {

The skeleton line.

  out.push(cur.value);

The work for this node.

  cur = cur.next;

Step. Leaving this out is an infinite loop.

console.log(out.join(','));

a,b,c

Your turn

Move to the next node so the walk makes progress.

let cur = head;
while (cur !== null) {
  console.log(cur.value);
  cur = ;
}

The trap

There is no .length and no index. To reach the 500th value you take 500 steps, and a walk that forgets to advance hangs the tab rather than throwing.

Practise linked lists on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.