Evaluate Linked Lists

Evaluating Linked Lists

Linked lists organise elements in nodes connected by pointers, allowing dynamic memory usage and flexible insertion/deletion. They come in three main flavours - singly, doubly and circular - each suited to different scenarios.

Applications & Trade-Offs

Singly linked lists suit simple stacks, browser history, and adjacency lists in graphs. They are light to implement and good for frequent adds/removes near the head.

Doubly linked lists power undo/redo in editors and caches that require quick removal from the middle, at the cost of extra pointers per node.

Circular lists underpin round-robin schedulers (for example, rotating through tasks), where you loop seamlessly from end back to start.

Linked Lists vs Arrays: Memory & Performance

Aspect Linked Lists Arrays Practical Impact
Memory layout Nodes live anywhere in memory; each node stores data + link(s). Elements sit in one contiguous block. Arrays tend to be faster to scan because nearby items are physically close (better CPU cache use).
Extra memory per item Each node stores pointer(s): 1 for singly, 2 for doubly. No per-item pointer; just the element itself. Lists pay overhead per element; doubly linked lists pay more. Arrays are more compact per item.
Growing / shrinking Natural growth: allocate a node when needed; no resizing step. Fixed arrays can’t grow. Resizable arrays (e.g. Python list, Java ArrayList) sometimes resize and copy. Lists handle unknown sizes smoothly. Dynamic arrays are usually fast, but occasional resizes copy data.
Insert / delete (middle) O(1) once you’re at the right node (just relink pointers). O(n): elements after the position shift to make room or fill the gap. Lists shine when you already have a pointer/iterator to the spot; arrays cost more for mid-list edits.
Access by index O(n): must follow links one by one. O(1): compute address by index instantly. Choose arrays when you need frequent random access (e.g. a[5000]).
Iteration / scanning Typically slower due to pointer chasing and cache misses. Typically faster; contiguous data is cache-friendly. For heavy reads or numeric processing, arrays usually outperform lists.
Wasted space Overhead in every node; little “spare capacity.” Resizable arrays keep extra capacity to avoid constant resizing. Arrays may reserve unused slots; lists spend space on pointers. “Waste” appears in different forms.
Reference stability Node addresses stay stable when inserting/removing other nodes. Resizes can move the whole array in memory (but indexes remain valid). Lists are good when external code holds pointers/iterators to specific nodes.

Summary: Choosing Between Them

  • Pick a linked list when you expect many inserts/deletes (especially near known positions) and random access is not critical.
  • Pick an array / dynamic array when you need fast index lookup, tight per-item memory, and fast scanning/processing.
  • Remember: Python’s list and Java’s ArrayList are dynamic arrays (fast index, occasional resize), not linked lists.

 Key Takeaways

  • Linked lists provide flexible, dynamic structures suited to insertion/deletion-heavy workloads.
  • Singly lists are memory-light; doubly lists support bidirectional traversal; circular lists enable seamless cycling.
  • Better than arrays for frequent mid-list updates, but inferior for random access and cache locality.