Core Concepts

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.

Abstract data type vs implementation

It helps to separate what a structure promises from how it keeps that promise.

• An abstract data type (ADT) describes operations and their meaning. A stack promises push, pop and peek, with the last item in being the first out.
• An implementation is a concrete memory layout. The same stack can sit on top of a dynamic array or a linked list.

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?"

Contiguous vs linked memory

Every structure here is built from one of two ideas.

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.

The five structures

• Array / dynamic array: a contiguous block. A dynamic array (Python 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.
• Linked list: nodes that hold a value and a reference to the next node (singly linked) or to both neighbours (doubly linked).
• Stack: last in, first out (LIFO). Think of a pile of plates or the call stack of a running program.
• Queue / deque: a queue is first in, first out (FIFO), like a line at a ticket counter. A deque (double-ended queue) allows adding and removing at both ends.
• Hash table: maps keys to values. A hash function turns a key into a bucket index, so lookups take O(1) on average.

The standard library already has them

You rarely write these from scratch in production code, but you need to know which built-in type matches which idea.

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 hashable

Choosing between them

Ask a few questions in order:

1. Do I need access by position? Use a dynamic array.
2. Do I only add and remove at one end? Use a stack (a dynamic array is enough).
3. Do I add at one end and remove at the other? Use a queue or deque, never a plain array with removal at index 0.
4. Do I look things up by key or test membership? Use a hash map or hash set.
5. Do I splice items in and out of the middle while holding references to nodes? Consider a linked list, but measure first; arrays often win anyway.

Vocabulary

Summary

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.