Publié · en amélioration
Guide Structures de données de base · 1/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
A data structure is a way of laying out data in memory together with the operations that are cheap on that layout. Picking one is always a trade: a layout that makes lookups by position instant may make insertion in the middle slow, and a layout that makes insertion cheap may make lookups slow. This guide covers the five structures you meet in almost every program: arrays and dynamic arrays, linked lists, stacks, queues and deques, and hash tables.
It helps to separate what a structure promises from how it keeps that promise.
push, pop and peek, with the last item in being the first out.Interview questions and library docs mix the two all the time, so get used to asking: "Which operations do I need, and how often?" before asking "Which class do I use?"
Every structure here is built from one of two ideas.
| Idea | How it stores items | Strength | Weakness |
|---|---|---|---|
| Contiguous | One block of memory, items side by side | O(1) access by index, cache friendly | Inserting in the middle shifts everything after it |
| Linked | Separate nodes joined by pointers | O(1) insert or delete next to a node you hold | O(n) to reach the k-th item, poor cache locality |
Modern CPUs read memory in cache lines, so walking a contiguous array is often many times faster than walking a linked list with the same big-O cost.
list, C++ std::vector, Java ArrayList, a JavaScript array) keeps spare capacity and grows by allocating a bigger block and copying, so appending is O(1) amortized.You rarely write these from scratch in production code, but you need to know which built-in type matches which idea.
| Idea | Python | C++ | Java | TypeScript |
|---|---|---|---|---|
| Dynamic array | list | std::vector | ArrayList | Array |
| Stack | list (append / pop) | std::vector or std::stack | ArrayDeque | Array (push / pop) |
| Queue / deque | collections.deque | std::deque, std::queue | ArrayDeque | write a ring buffer |
| Hash map | dict | std::unordered_map | HashMap | Map |
| Hash set | set | std::unordered_set | HashSet | Set |
A list used as a stack works only at its end:
stack = []
stack.append("a") # push
stack.append("b")
print(stack[-1]) # peek -> b
print(stack.pop()) # pop -> b
print(stack) # ['a']For a queue, use deque instead of list.pop(0), which shifts every remaining element:
from collections import deque
queue = deque()
queue.append("job-1") # enqueue at the right
queue.append("job-2")
print(queue.popleft()) # dequeue from the left -> job-1
queue.appendleft("urgent") # a deque also accepts items at the front
print(list(queue)) # ['urgent', 'job-2']Dictionaries and sets are hash tables. Keys must be hashable, which in practice means immutable:
stock = {"apple": 3, "pear": 0}
stock["kiwi"] = 7 # insert
stock["apple"] += 1 # update
print(stock.get("plum", 0)) # missing key with a default -> 0
seen = {"apple", "kiwi"}
print("pear" in seen) # membership test in O(1) average -> False
# stock[["a", "b"]] = 1 would raise TypeError: lists are not hashableAsk a few questions in order:
| Term | Meaning |
|---|---|
| Capacity | Slots allocated in a dynamic array, including unused ones |
| Amortized cost | Average cost per operation over a long sequence |
| Hash function | Maps a key to an integer |
| Bucket | One slot of a hash table's array |
| Collision | Two keys that land in the same bucket |
| Load factor | Number of stored items divided by number of buckets |
Data structures are trade-offs between access patterns. Contiguous arrays give fast indexing and good cache behaviour, linked nodes give cheap local splicing, stacks and queues restrict access to the ends, and hash tables give average O(1) lookup by key. Start from the operations you need, then pick the built-in type that makes those operations cheap.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.