Linked Lists

Why linked lists matter

In an array, elements are addressed by indexes, while in a linked list each element stores a reference to the next node. That changes the way we think about the structure: instead of jumping to a numbered position, an algorithm follows a chain of references and often changes the structure by rewiring those references rather than copying values.

Linked lists are especially useful as a learning structure because they make it clear why the cost of an operation depends not only on the number of elements, but also on whether an algorithm already has a reference to the node it needs.

What this section covers

• Linked List Basics. We will examine the structure of a node, the role of the next reference, and the difference between sequential and indexed access.
• Singly Linked List. You will learn to work with a chain in which each node knows only about the next element.
• Doubly Linked List. We will add a backward reference and see which operations become more convenient at the cost of additional memory.
• Fast and Slow Pointers. We will introduce a technique in which two references move through the same chain at different speeds.
• Reverse Linked List. You will learn to change the direction of references without creating a second list containing the same elements.
• Cycle Detection. We will examine a situation where the chain returns to an already visited node instead of ending.
• Merge Linked Lists. We will use sequential traversal to combine two ordered chains.

Links matter more than indexes

Node first = new Node(10);
Node second = new Node(20);

first.next = second;

These two nodes already form a tiny linked list. From here on, we will work not with indexes, but with nodes and references between them — the idea that underlies the entire section.