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









