Released · improving
Algorithm
Learn how arrays, linked lists, stacks, queues and hash tables work, what each operation costs, and how to pick the right one.
A data structure is a way of laying out data in memory together with the operations that are cheap on that layout. This topic covers the five structures nearly every program relies on: arrays and dynamic arrays, linked lists, stacks, queues and deques, and hash tables. Along the way it explains contiguous versus linked memory, hash functions, collisions and the load factor.
The structure you choose decides whether an operation is O(1) or O(n). Building a queue by removing from the front of a list, or testing membership against a list, makes a program slow down sharply as data grows. Knowing what Python's list, deque, dict and set, C++'s vector, deque and unordered_map, Java's ArrayList, ArrayDeque and HashMap, and TypeScript's Array, Map and Set really are helps you avoid those traps, and it is the first thing coding interviews check.
Start by tracing each structure by hand on a small example to see what moves in memory. Then implement a stack, a ring-buffer queue and a hash map with separate chaining, summarize the costs in a table and measure them with a timer. Finally, work through practice problems where the main skill is choosing the right structure for the job.
Arrays give O(1) access by index and good cache behaviour; linked lists give O(1) insertion and deletion next to a node you already hold.
A dynamic array grows by a constant factor and copies its items, so occasional expensive appends still average out to O(1).
A stack removes the newest item and a queue the oldest. Deques and ring buffers make operations at both ends O(1).
A hash table maps keys to buckets for O(1) average lookups, resolves collisions with techniques such as chaining, and grows when the load factor passes a limit.
A hash map with separate chaining: the key's hash modulo the bucket count picks a bucket, an existing key has its value replaced, and once the load factor passes 0.75 the buckets double and every pair is reinserted. The script also shows a list used as a stack and a deque used as a queue.
data_structures.py
from collections import deque
class HashMap:
"""Separate chaining: each bucket is a list of (key, value) pairs."""
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size > 0.75 * len(self.buckets): # load factor limit
old = self.buckets
self.buckets = [[] for _ in range(2 * len(old))]
for pairs in old:
for k, v in pairs:
self._bucket(k).append((k, v))
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
stack = [1, 2, 3]
stack.append(4)
print("stack pop:", stack.pop()) # 4 (LIFO)
queue = deque([1, 2, 3])
queue.append(4)
print("queue popleft:", queue.popleft()) # 1 (FIFO)
ages = HashMap()
for name, age in [("ada", 36), ("alan", 41), ("grace", 85)]:
ages.put(name, age)
ages.put("ada", 37)
print("ada:", ages.get("ada"), "size:", ages.size) # ada: 37 size: 3
python data_structures.pySix chapters that take you from installation to the core ideas of Basic data structures.
Ask questions, share experience and trade opinions about Basic data structures.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.