Chrysolites Tech Academy

Programming Foundations: Python, Algorithms, Kotlin and Excel · Course book

Chapter 2: Choosing a Data Structure and Counting Steps

Pairs with Lesson 2: Data Structures and Algorithms, Seen Clearly

A program that gives the right answer can still be useless if it takes an hour to do so. Two things decide how fast a program runs: how its data is arranged in memory, called the data structure, and the series of steps it follows, called the algorithm. This chapter compares the most common structures, shows how to count the work an algorithm does, and explains why one good idea can turn a million steps into twenty.

Linear structures

Arrays and linked lists

The simplest way to store many values is an array: a row of equal-sized slots sitting side by side in memory. Because the slots are next to each other and all the same size, the computer can jump straight to any position. Asking for item 500 costs the same as asking for item 0. The weakness appears when you insert a value near the front. Every later item must shuffle along one place to make room, so inserting at the start of a million-item array means a million moves.

A linked list makes the opposite trade. Each value lives in its own node, and every node stores a pointer to the next one. The nodes can be scattered anywhere in memory. Inserting is cheap, because you only redirect two pointers, but finding item 500 means starting at the first node and following 500 pointers one at a time.

Array: neighbours in memory 72946 [0][1][2][3][4] Linked list: nodes joined by pointers 7294 headtail
Figure 2.1 — An array keeps its values in one unbroken block, so any position can be reached directly. A linked list keeps each value in a separate node and reaches it by following pointers from the head.

Variations exist for particular needs. A doubly linked list gives every node a second pointer back to the previous node, so you can walk in both directions. A circular list joins the tail back to the head, which suits anything that takes turns in a loop, such as players in a game.

Stacks, queues and priority

Some structures are defined less by how they are stored and more by the rule for taking things out.

A stack follows "last in, first out". Picture a pile of plates: you add to the top and remove from the top. Adding is called push and removing is called pop. The undo button in an editor is a stack, since the most recent change is the first one reversed. So is the record a program keeps of which function called which.

A queue follows "first in, first out", like people waiting at a counter. New arrivals join the back and the person at the front is served next. Print jobs, messages waiting to be sent and tasks waiting for a processor are all queues. A deque, short for double-ended queue, allows adding and removing at both ends.

A priority queue breaks the arrival order on purpose. Each item carries a priority, and the most urgent one leaves first no matter when it arrived. It is usually built on a heap, a tree arranged so that the most urgent item is always at the top and can be found instantly.

Hash tables: finding without searching

Suppose you want to store a phone number for each name and fetch it instantly. Searching a list name by name is slow. A hash table avoids the search altogether. It runs the key through a hash function, a calculation that converts the key into a slot number, and then goes directly to that slot.

Here is a toy hash function for a table with 8 slots: replace each letter by its position in the alphabet, add the positions, and take the remainder after dividing by 8.

  • "cat" gives 3 + 1 + 20 = 24, and 24 divided by 8 leaves remainder 0, so it goes in slot 0.
  • "dog" gives 4 + 15 + 7 = 26, and 26 divided by 8 leaves remainder 2, so it goes in slot 2.
  • "act" gives 1 + 3 + 20 = 24, which again lands on slot 0.

The third key shows the catch. Two different keys can land on the same slot, which is called a collision. Real hash tables handle this, for example by keeping a short list in each slot, and they use far better hash functions that spread keys evenly. With a good function and enough slots, looking up a key takes roughly the same small time whether the table holds ten entries or ten million. A set is a hash table that stores keys only, which makes it ideal for removing duplicates or checking membership.

Trees and graphs

A tree arranges data in levels. One node sits at the top as the root, and each node may have children below it. Folders on a computer form a tree, and so does a family of web page elements.

A binary search tree adds one rule: every node has at most two children, smaller values go to the left and larger values go to the right. To find a value you start at the root and at each node decide to go left or right, throwing away half of the remaining tree each time. That only works well while the tree stays evenly shaped. If values are inserted in sorted order, a plain tree degenerates into a long chain that behaves like a linked list. Self-balancing designs such as AVL trees and red-black trees rearrange themselves after each insertion to prevent that.

A trie stores words letter by letter along its branches, so all words sharing a prefix share a path, which is how autocomplete can suggest endings quickly. A graph is the most general structure of all: nodes joined by connections in any pattern, with no root and no levels. Road maps and friend networks are graphs, and finding the shortest route between two points on one is the job of Dijkstra's algorithm.

Counting steps with Big O

To compare algorithms fairly we count how the number of steps grows as the input grows, and we describe that growth with Big O notation. The letter n stands for the number of items.

Take searching. Linear search checks items one after another, so in the worst case it looks at all n of them. This is written O(n). Binary search works only on sorted data, but it is far quicker: look at the middle item, decide which half the target must be in, and discard the other half.

Search for 26 in the sorted list 3, 8, 12, 17, 21, 26, 30, 35, 41, whose positions run from 0 to 8.

  1. The middle of positions 0 to 8 is position 4, which holds 21. Since 26 is larger, keep positions 5 to 8.
  2. The middle of positions 5 to 8 is position 6, which holds 30. Since 26 is smaller, keep position 5 only.
  3. Position 5 holds 26. Found.

Binary search needed 3 comparisons. Linear search would have needed 6, because 26 is the sixth item. The gap widens dramatically with size, because each comparison halves what is left. The worst case is about log₂ n comparisons, written O(log n).

01632081632number of items (n)steps in the worst case linear search: nbinary search: about log₂ n
Figure 2.2 — Worst-case steps for the two searches. Doubling the number of items doubles the work for linear search but adds only one step for binary search.

For a thousand items, binary search needs at most 10 comparisons, because 2 multiplied by itself 10 times is 1,024. For a million items it needs at most 20, since 2 to the power 20 is 1,048,576. Linear search could need all million.

Sorting shows the same pattern. Simple methods such as bubble sort, selection sort and insertion sort compare items in nested loops and take around n² steps. Merge sort and quicksort split the list, sort the pieces and combine them, taking around n × log₂ n steps. For 1,000 items that is roughly 1,000,000 steps against roughly 10,000.

StructureReach an item by positionFind an item by valueInsertGood for
ArrayO(1)O(n), or O(log n) if sortedO(n) at the front, O(1) at the endFixed collections read often
Linked listO(n)O(n)O(1) once you are at the spotFrequent inserts and removals
Stack or queueEnds onlyNot intendedO(1)Undo history, waiting lines
Hash tableNot orderedO(1) on averageO(1) on averageLookups by key, removing duplicates
Balanced search treeO(log n)O(log n)O(log n)Data that must stay sorted
HeapTop item only, O(1)O(n)O(log n)Always taking the most urgent item

O(1) means the cost does not grow with the amount of data. Table 2.1 makes the central lesson plain: no structure wins every column, so choosing one means deciding which operation your program performs most.

Strategies for designing algorithms

Beyond individual algorithms there are a few general strategies that turn up again and again.

  • Recursion solves a problem by having a function call itself on a smaller version of the same problem, until it reaches a case small enough to answer directly.
  • Divide and conquer splits the input into parts, solves each part and combines the answers. Binary search and merge sort both work this way.
  • Greedy methods take the choice that looks best right now and never reconsider. They are fast, and for some problems, such as giving change with ordinary coin values, they are also correct.
  • Backtracking tries a choice, follows it as far as it will go and steps back to try another when it hits a dead end. Puzzle solvers use it.
  • Dynamic programming stores the answers to small sub-problems so that each is worked out only once, which rescues recursive solutions that would otherwise repeat the same work thousands of times.

Recognising which strategy a problem calls for is the real skill. The syntax of any particular language is easy to look up; the habit of asking "how does the work grow as the data grows?" is what separates a program that scales from one that stalls.

Check your understanding

  • Why is reading item 900 quick in an array but slow in a linked list?
  • You push 1, then 2, then 3 onto a stack and pop once. Which value comes out? Which would come out of a queue? (Answer: 3 from the stack, 1 from the queue.)
  • Using the toy hash function from this chapter, which slot does "bad" land in? (Answer: 2 + 1 + 4 = 7, and 7 divided by 8 leaves remainder 7, so slot 7.)
  • A sorted list holds 4,000 items. What is the most comparisons binary search could need? (Answer: 12, because 2 to the power 11 is 2,048, which is too few, and 2 to the power 12 is 4,096.)
  • Why can binary search not be used on an unsorted list?

Install Chrysolites Tech Academy

Android / Chrome / Edge: open the browser menu and choose Install app or Add to Home screen.

iPhone / iPad (Safari): tap the Share button, then Add to Home Screen.