Skip to content
Tutorials Center
My learning

Topics

Lesson 142 of 149 ยท Data Structures and Algorithms

Stacks, Queues, Heaps and Linked Lists

Build classic data structures in Python. Use lists as stacks, deque as a queue, heapq for priority queues, and build a linked list and a binary search tree.

A data structure is a way of organizing data so that certain operations are fast. Python's built-in lists, dictionaries and sets cover most needs, but computer science has a small set of classic structures that show up everywhere: in job interviews, in algorithms, and inside the tools you use every day. Undo buttons are stacks. Print jobs wait in queues. Task schedulers pick the most urgent job from a heap.

In this lesson you'll learn what each structure is for, how to get it from Python's standard library, and how to build a linked list and a small tree yourself, so you understand what's happening underneath. The guiding question throughout is: which operations does my program do most often, and which structure makes them cheap?

Measuring "cheap": a quick word on Big-O

To compare structures, programmers describe how the cost of an operation grows as the data grows. This is Big-O notation:

  • O(1), constant time: the cost doesn't depend on the size. Reading items[5] or a dictionary lookup.
  • O(log n), logarithmic: doubling the data adds only one more step. Pushing onto a heap.
  • O(n), linear: the cost grows in step with the size. Searching an unsorted list with in.

You'll go deeper in the next lesson, Searching and Sorting Algorithms. For now, "O(1) good, O(n) slow for big data" is enough.

Stacks: last in, first out

A stack works like a pile of plates. You add to the top (push) and take from the top (pop), so the last item added is the first one out: LIFO. Stacks are behind undo history, the browser's back button, and the call stack that Python uses to track running functions (the one you saw in recursion).

A Python list is already a perfect stack. append() pushes and pop() removes the last item, and both are O(1):

Python An undo stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A classic stack problem is checking whether brackets are balanced. Each opening bracket is pushed; each closing bracket must match the one on top:

Python Balanced brackets with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Queues: first in, first out

A queue is a line at a ticket counter: new items join at the back (enqueue) and leave from the front (dequeue), so the first one in is the first one out: FIFO. Queues hold tasks waiting to be processed, messages waiting to be sent, and the frontier of a breadth-first search.

A list is a poor queue, because list.pop(0) shifts every remaining item one place left, which is O(n). Use collections.deque instead, which is O(1) at both ends. You met it in the collections lesson:

Python A print queue with deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here's a queue doing real work. Breadth-first search (BFS) explores a network level by level, which finds the path with the fewest steps. The network is stored as a dictionary that maps each station to its neighbors, a common way to represent a graph:

Python Fewest stops with BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The visited set makes sure no station is queued twice, and its O(1) membership test keeps the search fast.

Note: the standard library also has queue.Queue, a thread-safe queue for passing work between threads (see concurrency). It adds locking you don't need in single-threaded code, so deque is the right default.

Heaps and priority queues

Sometimes the next item to process isn't the oldest but the most important: the most urgent support ticket, the closest unexplored node on a map, the earliest scheduled event. That's a priority queue, and the standard way to build one is a heap.

Python's heapq module turns an ordinary list into a min-heap: the smallest item is always at index 0. Pushing and popping are O(log n), and peeking at the smallest is O(1):

Python heapq basics

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed heap looks only partly sorted, and that's the point: a heap keeps just enough order to find the smallest item fast, which is much cheaper than keeping everything sorted.

To store tasks with priorities, push tuples. Tuples compare by their first item, so the lowest priority number comes out first. Adding a counter as the second item breaks ties in arrival order and stops Python from ever comparing the task data itself:

Python A task scheduler with priorities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both P1 tasks come out before everything else, in the order they were added. Python 3.14 also added max-heap functions such as heapq.heappush_max() and heapq.heappop_max(); in older versions the usual trick is to push negated numbers, -priority, so the largest comes out first.

Linked lists

A linked list stores each value in a small node object that also holds a reference to the next node. The list itself only remembers the first node, the head. To find an item, you follow the links one by one.

Python doesn't ship a linked list class, and in everyday code a list or deque is almost always faster. But linked lists are a classic interview topic, and building one is a great exercise in classes and references:

Python A singly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The special methods make it feel like a built-in: __iter__ (written as a generator) lets you loop over it and use in, __len__ supports len(), and __repr__ gives it a readable printout.

The trade-off: inserting at the head is O(1) and never moves other items, but reaching the 500th item means following 500 links, while items[500] on a Python list is instant. A doubly linked list also stores a link to the previous node, so it can remove from either end in O(1). That's roughly how deque works internally (it links blocks of items rather than single values).

Trees, briefly

A tree is like a linked list where each node can point to several children. Folders on your disk, HTML elements on a page, and the moves in a game are all trees. A binary search tree (BST) is a special case where each node has at most two children, with smaller values on the left and larger values on the right. That rule lets a search skip half of the remaining tree at every step:

Python A tiny binary search tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

An in-order traversal (left subtree, node, right subtree) visits a BST's values in sorted order. Searching a balanced BST is O(log n). If you insert already-sorted values, though, every node goes to the right and the tree degenerates into a linked list with O(n) searches. Real-world trees, such as the ones inside databases, rebalance themselves to avoid that.

In Python you'll rarely need your own BST: a dictionary or set gives O(1) lookups, and the bisect module keeps a list sorted. Write trees when the data is naturally hierarchical, like a folder structure or a parsed document such as XML.

Hash maps: how a dictionary works inside

A dict is Python's built-in hash map (also called a hash table). It keeps an array of buckets. To store a key, Python computes hash(key), takes it modulo the number of buckets, and puts the pair in that bucket. To find the key later, it repeats the same calculation and goes straight to the right bucket, which is why lookups take O(1) time on average.

Two different keys can land in the same bucket. That is a collision. One classic fix is chaining: each bucket holds a small list of pairs, and a lookup scans only that short list. When the table gets too full, you grow it (double the buckets) and re-insert everything, so the chains stay short. (CPython's real dict uses open addressing instead of chains, but the idea is the same.)

Python A hash map with chaining

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Advantages Disadvantages
Hash map Fast insert, lookup and delete on average; keys can be any hashable value Uses more memory than a list; no order by key; the worst case is O(n) when many keys collide; keys must be hashable and immutable

You get all of this ready-made from dict, and your own classes can be keys if they define consistent __hash__ and __eq__ methods.

Choosing a structure

You mostly need to... Use Fast operations
Add and remove at the end (undo, backtracking) list as a stack append, pop: O(1)
Add at one end, remove at the other (tasks, BFS) collections.deque append, popleft: O(1)
Always take the smallest or most urgent item heapq on a list push, pop: O(log n); peek: O(1)
Look up by key, or check membership dict / set lookup, insert, delete: O(1) on average
Read by position list items[i]: O(1)
Insert in the middle without moving data linked list O(1) once you hold the node
Represent a hierarchy a tree of node objects depends on the shape

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which structure gives you the item that was added most recently?

    A stack is last in, first out, so pop() returns the newest item.
  2. 2. Why is collections.deque better than a list for a FIFO queue?

    Removing from the front of a list moves all other items, which gets slower as the list grows.
  3. 3. After heapq.heapify(data), what is guaranteed about data?

    heapq maintains a min-heap, which keeps only enough order to put the smallest item first.
  4. 4. Why push (priority, counter, task) tuples instead of (priority, task)?

    When priorities are equal, tuples compare the next item. A unique counter decides the order and avoids errors if tasks can't be compared.
  5. 5. What is the cost of reading the 1,000th item of a singly linked list?

    Linked lists have no index; you walk node by node from the head.

Summary

  • Big-O describes how an operation's cost grows with the data: O(1) constant, O(log n) logarithmic, O(n) linear.
  • A stack (LIFO) is just a list with append() and pop(); it powers undo, backtracking and bracket matching.
  • A queue (FIFO) should be a collections.deque with append() and popleft(); breadth-first search is built on one.
  • heapq turns a list into a min-heap: heappush, heappop, nsmallest and nlargest. Push (priority, counter, item) tuples for a priority queue.
  • A linked list chains nodes by reference: cheap inserts at the head, slow access by position.
  • A binary search tree keeps smaller values left and larger values right; an in-order traversal yields sorted values.
  • Pick the structure whose fast operations match what your program does most.

Next: Searching and Sorting Algorithms, where you'll put these ideas to work and measure how algorithms scale.