List Variants

List-Based Linear Data Structures

Type	Description	Key Characteristic	Typical Use Case	Access Pattern	Memory Behavior	Notes
Linked List	Nodes linked in sequence	Dynamic size	General-purpose lists	Sequential	Non-contiguous	Single pointer per node
Doubly Linked List	Two-way linked nodes	Bidirectional traversal	Navigation systems	Sequential	Non-contiguous	Extra memory per node
Array List	List backed by array	Fast random access	Dynamic collections	Indexed	Contiguous	Costly insertions
Association List	Key–value pairs in list	Simple mapping	Small dictionaries	Sequential	Non-contiguous	Linear search
Self-organizing List	Reorders on access	Adaptive performance	Caching	Sequential	Non-contiguous	Move-to-front heuristic
Skip List	Layered linked list	Logarithmic search	Ordered sets/maps	Sequential + skip	Non-contiguous	Probabilistic structure
Unrolled Linked List	Nodes store blocks	Fewer pointers	Memory optimization	Block-based	Semi-contiguous	Cache-friendly
VList	Versioned list	Persistent structure	Functional programming	Sequential	Non-contiguous	Immutable versions
Conc-tree List	Tree-based list	Fast concatenation	Text processing	Indexed	Tree-based	Rope-like behavior
XOR Linked List	XOR of addresses	Memory efficient	Low-level systems	Sequential	Non-contiguous	Hard to debug
Zipper	Focused list traversal	Efficient edits	Functional editing	Cursor-based	Non-contiguous	Maintains context
Doubly Connected Edge List	Edge-centric list	Graph topology	Computational geometry	Pointer-based	Non-contiguous	Used in planar graphs
Difference List	List as function	Fast append	Logic programming	Sequential	Abstract	Used in Prolog
Free List	Tracks unused nodes	Memory reuse	Memory allocators	Sequential	Non-contiguous	Internal structure