Data Structures Explained: Lists, Stacks, Queues, Hash Tables and Trees

Key terms: abstract data types, implementations and Big O

• Abstract data type (ADT): a description of behaviour, such as "a stack lets you push and pop from the top", without saying how it is built.
• Implementation: the concrete structure behind an ADT. A stack can be built on a dynamic array or a linked list.
• Big O notation: how the cost of an operation grows as the number of items, n, grows. O(1) is constant, O(log n) grows slowly, O(n) grows in step with the data.
• Amortised cost: the average cost over many operations, even if one occasional operation is slow.

Big O is covered more fully in our algorithms guide; here it is the yardstick for comparing structures.

How the main structures work

Arrays and linked lists

An array stores items in one contiguous block, so the position of item i can be calculated directly and indexing is O(1). Inserting at the front means shifting every other item. A Python list is a dynamic array that grows automatically. A linked list stores each item in a node that points to the next node, so inserting at the head is O(1), but reaching item i means walking i links.

Stacks and queues

A stack is last in, first out (LIFO), like a pile of plates; browser history and undo use one. A queue is first in, first out (FIFO), like a ticket counter line; print jobs and task schedulers use one.

Hash tables

A hash table runs each key through a hash function to choose a slot, so lookups usually go straight to the right place. When many keys land in the same slot (collisions), operations slow down, which is why the worst case is O(n). Python's dict and set are hash tables.

Trees, heaps and graphs

A tree is a hierarchy of nodes with one root. In a binary search tree (BST), every value in a node's left subtree is smaller and every value in its right subtree is larger, so a search discards half the remaining tree at each step if the tree is balanced. A binary heap is a tree, usually stored in an array, where each parent is no larger than its children (a min-heap), so the smallest item is always at the root. A graph is a set of vertices connected by edges, used for road maps, networks and social connections.

Big O comparison of common operations

A plain BST becomes a linked list in disguise if you insert already-sorted data, giving O(n) operations. Self-balancing trees such as AVL and red-black trees keep the height at O(log n) for every operation. For graphs stored as adjacency lists, adding an edge is O(1) and checking whether two vertices are connected takes time proportional to the number of neighbours.

Data structures in Python: list, deque, dict, set and heapq

from collections import deque
import heapq

stack = []                          # list as a stack (LIFO)
stack.append("page1")
stack.append("page2")
print(stack.pop())                  # page2

queue = deque(["Asha", "Ravi"])     # deque as a queue (FIFO)
queue.append("Meera")
print(queue.popleft())              # Asha

stock = {"rice": 40, "dal": 25}     # dict as a hash table
stock["atta"] = 30
print(stock.get("sugar", 0))        # 0

seen = set()                        # set for membership and de-duplication
for city in ["Pune", "Delhi", "Pune"]:
    seen.add(city)
print(len(seen), "Pune" in seen)    # 2 True

tasks = []                          # heapq as a min-heap priority queue
heapq.heappush(tasks, (2, "reply to email"))
heapq.heappush(tasks, (1, "fix login bug"))
heapq.heappush(tasks, (3, "update docs"))
print(heapq.heappop(tasks))         # (1, 'fix login bug')

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(graph["A"])                   # neighbours of A: ['B', 'C']

Avoid list.pop(0) for a queue: it shifts every remaining item, so it is O(n). deque.popleft() is O(1). Python has no built-in linked list or BST type, so here is a minimal BST to show the idea:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root


def contains(root, value):
    while root is not None:
        if value == root.value:
            return True
        root = root.left if value < root.value else root.right
    return False


root = None
for n in [50, 30, 70, 20, 40, 60]:
    root = insert(root, n)
print(contains(root, 40), contains(root, 45))   # True False

The Node class uses the ideas from object-oriented Python; if the syntax is new, start with the Python basics guide.

How to choose a data structure, step by step

1. List the operations your program performs most often: lookup by key, lookup by position, adding at one end, removing the smallest item, and so on.
2. If you look things up by a key or test membership, use a dict or set.
3. If you need items in order and access them by position, use a list.
4. If you add and remove at both ends, or need a FIFO queue, use a deque.
5. If you repeatedly need the smallest or highest-priority item, use heapq.
6. If you need data kept sorted while inserting, consider a balanced tree, or the standard bisect module on a sorted list for modest sizes.
7. If items are connected to each other, model a graph, usually as a dict of neighbour lists.
8. Measure with real data before optimising further; a simpler structure is often fast enough.

Practical exercise: a support ticket desk

Build a small Python module that manages support tickets using four structures together:

• A deque holding new tickets in arrival order.
• A dict mapping ticket ID to ticket details for instant lookup.
• A heapq list of (priority, ticket_id) tuples so the most urgent ticket is handled first.
• A set of customer emails that already have an open ticket, to block duplicates.

Done looks like this: you can add, look up, escalate and close tickets; a comment above each function states its Big O cost; and a timeit comparison of x in big_list against x in big_set for 100,000 numbers shows the set lookup is far quicker. If a step misbehaves, use the techniques in how to debug code. The PHP Foundation course teaches the same programming fundamentals in PHP, where associative arrays play the role of dicts.

Common mistakes

• Searching a long list with in inside a loop when a set or dict would turn each check into an average O(1) lookup.
• Using list.pop(0) or list.insert(0, x) as a queue, which is O(n) per operation.
• Assuming a binary search tree is always O(log n), forgetting that sorted input makes an unbalanced tree degrade to O(n).
• Trying to use a list as a dict key or set member, which raises TypeError: unhashable type.
• Expecting heapq to keep the whole list sorted, when it only ensures the smallest item is at index 0.

Frequently asked questions