liveBook · Manning

Linked list

As explained in The Coder Cafe

A linked list is a sequence of nodes connected by references, allowing flexible growth and efficient insertion or removal at known positions.

A linked list stores a sequence as nodes. Each node contains data and a reference to the next node, so the elements do not need to occupy adjacent memory locations. This organization supports flexible growth, but adds pointer overhead and makes position-based access slower than array access. section 1.1

Use the following tradeoffs when choosing between a linked list and an array:

  • Access a linked-list element by starting at the first node and following references one at a time; direct index access is unavailable. section 1.1
  • Insert or delete in O(1) time when the relevant position is already known; finding that position first can take O(n). section 1.1
  • Accept extra memory for references and potentially poorer cache locality in exchange for dynamic growth and efficient known-position updates. section 1.5
  • Choose a doubly linked list when nodes need references to both their previous and next neighbors. section 1.1

Choosing a container

A collection that frequently reads elements by index favors an array. A collection that grows or shrinks and frequently inserts or removes at already-known positions may favor a linked list, provided its reference overhead and slower traversal are acceptable. section 1.0 section 1.5

How The Coder Cafe covers it

How deep it goes
Explains node structure, memory layout, access, growth, insertion, deletion, and tradeoffs, without extending beyond introductory comparison.
Examples
Uses array comparisons, node references, dynamic-array implementations, and known-position insertion or deletion as concrete teaching examples.
What you can do after
Evaluate whether linked-list flexibility justifies reference overhead and slower traversal when selecting a collection for software.
How it connects
Contrasts linked lists with arrays and dynamic arrays, and connects them to doubly linked lists, cache locality, and time complexity.

Also explained in

Compare how 10 books explain linked list →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.