Linked lists

Overview

Introduces singly and doubly linked lists and contrasts them with arrays.

A linked list stores each element in its own node together with a reference to the next node. Inserting at a known position is constant time because only a couple of references change, but reaching that position first takes linear time.

Choose a linked list when you insert and remove frequently at ends or known positions and rarely index by position; choose an array when you index often and resize rarely.