liveBook · Manning

Linked list

As explained in Algorithms Every Programmer Should Know

A linked list is a sequence of elements connected by links or references to other elements.

A linked list stores values in nodes, each pointing to the next. To find an element, start at the head and follow the links; unlike an array, the list does not provide direct access by position. Insertions and deletions can be efficient because they change links rather than shift array elements. section 1.4.2

A doubly linked list adds a link to the previous node:

  • Its previous and next links allow traversal in both directions, at the cost of extra memory. section 1.4.2

Why use links?

To reach position six in a linked list, follow nodes from the head. Inserting at position three in an array requires shifting elements; in a linked list, the relevant links can be changed. section 1.4.2

Figure 1.4 Illustration of a linked list with four nodes. Each node has data and a pointer pointing to the next node. The start of the linked list is marked as head. The end of the linked list is identified if the next pointer is null.

Use the node-and-arrow diagram to see how the head begins the chain and a null next link marks its end. section 1.4.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains nodes, sequential traversal, pointer updates, and the doubly linked variation, with Python implementations.
Examples
Uses a chain of nodes, traversal to position six, and insertion at array position three as contrasts.
What you can do after
Build a basic linked list in Python with nodes, append, and display operations.
How it connects
Connects linked lists with arrays, hash maps, doubly linked lists, and algorithm performance.

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 Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.