ProgramGuru

Linked Lists: Nodes, Links and Traversal

Follow a chain of school stations

An activity route points from the library station to the laboratory station. Each station stores its own information and a link to the next station; the first link tells us where traversal begins.

A linked list consists of nodes. Each node contains a value and a link to another node. The head identifies the first node, and a chosen end marker such as null identifies the end.

  1. Traverse

    Follow next links until the end marker.

  2. Change links

    Insert a node while preserving the rest of the route.

  3. Compare costs

    Explain why finding a position still requires traversal.

Follow links rather than array positions

  1. Head

    Begin at the first node.

    Library

  2. Next link

    Read the next node reference.

    Lab

  3. End marker

    No next node remains.

    null
Read these stages alongside the complete example. They explain the relationship; they do not execute code.

A link holds a reference to another node

These JavaScript nodes are ordinary objects. value stores the station name and next refers to another node. The list is represented by references, not by pretending the objects occupy consecutive physical locations.

Traversal keeps a current node, processes its value, then advances to node.next. Unlike array indexing, reaching the third node requires following the earlier links.

Before starting, review objects and shared references. These examples use JavaScript; other languages can use different syntax and rules.

Visit each station in the chain

The first node links to the second. The loop prints Library, advances to Lab, then advances to null and stops.

Changing only a value differs from changing a link: links determine which nodes are reachable from the head.

JavaScript · local teaching example

const lab = { value: 'Lab', next: null };
const library = { value: 'Library', next: lab };
let node = library;
while (node !== null) {
  console.log(node.value);
  node = node.next;
}

Expected output

Library
Lab

Preserve the old link when inserting

The new art node points to the original next node before library.next is updated. This preserves the route to Lab.

If you replaced the old link without saving it, the tail could become unreachable from the head. Insertion is simple after you have the needed node reference.

JavaScript · local teaching example

const lab = { value: 'Lab', next: null };
const library = { value: 'Library', next: lab };
const art = { value: 'Art', next: library.next };
library.next = art;
let node = library;
while (node !== null) {
  console.log(node.value);
  node = node.next;
}

Expected output

Library
Art
Lab

Apply the rule to a small change

Represent an empty route using a null head, and count visited nodes.

Worked answer

The initial condition is false, so no node is processed and the count remains zero. A null head is different from a node whose station value happens to be empty text.

JavaScript · local teaching example

const head = null;
let node = head;
let visited = 0;
while (node !== null) {
  visited += 1;
  node = node.next;
}
console.log(visited);

Expected output

0

Recognize mistakes and limits

Insertion can be constant work once the relevant predecessor is known, but finding that location may require walking the list. “Linked-list insertion is always faster” ignores the search and other overhead.

A mistaken link can create a cycle, making a null-terminated traversal repeat forever. Lists also require extra link storage and can have poorer locality than contiguous structures. A doubly linked list adds backward links and more updates; use that complexity only if needed.

For the language or tool rules used here, see JavaScript indexed collections.

Check the core idea

JavaScript · code for this question

const lab = { value: 'Lab', next: null };
const library = { value: 'Library', next: lab };
let node = library;
while (node !== null) {
  console.log(node.value);
  node = node.next;
}
What makes traversal advance to the next station?
Choose one answer. You can try again.

Answer and explanation

node = node.next

Yes. It follows the stored link.

Apply the idea to a new situation

Why save the original next link when inserting Art?
Choose one answer. You can try again.

Answer and explanation

To keep the remaining route reachable after inserting the new node.

Yes. Art must still link to Lab.

Trace reachability through each link

A linked list is a chain of nodes. Maintain head and next links, stop at the end marker, and consider traversal, memory and cycle risks when comparing it with arrays.

Connect this idea with indexed collections and operation-based selection.

Reaching the recap and completing the quizzes are separate milestones.

    Next lesson: Choosing the Right Data Structure →