Arrays, linked lists, stacks, queues and skip lists.
An array is a contiguous block of memory holding a fixed-size sequence of equally-sized elements, indexed by position. Python's is a dynamic array (ArrayLi
A doubly-linked list adds a pointer to each node, enabling O(1) insertion and removal anywhere — given a node reference. in Python is implemented as a…
A queue is a FIFO (first-in, first-out) container with (add to back) and (remove from front). Use in Python — O(1) at both ends. A as a queue is O(n) per…
A singly-linked list is a chain of nodes, each holding a value and a pointer to the next node. Insert/delete at the head is O(1); access by index is O(n)…
A skip list is a probabilistic ordered structure: a base linked list with multiple "express lane" forwarding pointers above it. Each node is randomly…
A stack is a LIFO (last-in, first-out) container with two operations: (add to top) and (remove from top). Backed by an array or linked list; Python uses a…
Linear structures store elements in a sequence. There are two physical layouts underneath all of them. An array keeps elements in one contiguous block, so element i is found by arithmetic in O(1) time and iteration is cache-friendly, but inserting in the middle shifts everything after it. A linked list stores each element in its own node with a pointer to the next (and, for doubly linked lists, the previous) node, so splicing at a known position is O(1) but finding position i requires walking i nodes.
Stacks and queues are abstract interfaces defined by which end you access. A stack adds and removes at the same end (last in, first out); a queue adds at the back and removes from the front (first in, first out). Either can be built on a dynamic array or a linked list. A skip list adds multiple levels of forward pointers to a sorted linked list, giving expected O(log n) search while keeping cheap insertion.
| Structure | Access by index | Search | Insert / delete | Typical use |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n), amortised O(1) append | Default sequence, buffers |
| Singly Linked List | O(n) | O(n) | O(1) at head or after a node | Simple queues, free lists |
| Doubly Linked List | O(n) | O(n) | O(1) given a node | LRU caches, deques |
| Stack | top only | — | O(1) push / pop | Call stacks, undo, DFS |
| Queue | front only | — | O(1) enqueue / dequeue | BFS, job scheduling |
| Skip List | O(log n) expected | O(log n) expected | O(log n) expected | Ordered maps, Redis sorted sets |
Start with an array (a Python list) unless you have a specific reason not to; contiguous memory usually wins in practice even when a linked list has a better theoretical bound. Use collections.deque for queues in Python, since popping from the front of a list is O(n). Reach for a doubly linked list when you hold references to nodes and must remove them in O(1), as in an LRU cache combined with a hash table. Use a skip list or a balanced tree from Trees when you need ordered iteration plus fast insert.