Computer Science › Section I · Data abstractions › Topic I.1

Basic data structures

Memory is a single row of numbered cells, but problems come in other shapes: tables, waiting lines, undo histories and hierarchies. Data structures give programs those shapes, and five of them, arrays, lists, stacks, queues and trees, appear almost everywhere.

Organising data on purpose

Main memory, as the topic "Main memory" described, is one long row of numbered cells. Real problems rarely look like that. A spreadsheet has rows and columns, a playlist has an order, an undo button needs the most recent change first, and a company chart branches downwards. A data structure arranges a collection of data in the shape the problem needs. This topic introduces the basic ones. Later topics in this section show how each is built from plain memory cells, so that a programmer can use the shape and forget about the cells.

Arrays in two dimensions

The topic "Traditional concepts: variables, types, and control" introduced arrays, values of one type reached by index, and records, fields of different types reached by name. An array can also have two dimensions, rows and columns, with each entry identified by a pair of indices: row first, then column. A gradebook for 30 students and 6 quizzes is a 30 × 6 array. In our pseudocode, counting from 1, Grades[4, 2] is student 4's score on quiz 2. In Python a two-dimensional array is usually a list of rows, counted from 0, so the same score is grades[3][1].

Lists

A list is a collection whose entries are arranged in sequence. Its front is the head and its far end the tail. A guest list, a playlist and the characters of a sentence are all lists. The usual operations are adding an entry, removing one, searching for one, and processing every entry in turn, as the loops in "Iterative structures: sequential search and insertion sort" do. Python's built-in list supports all of these: append adds at the end, remove deletes a value, in tests membership, and a for loop visits each entry.

Stacks: last in, first out

Restrict a list so that entries can only be added or removed at one end, the top, and you have a stack; the other end is the bottom. Adding is a push and removing is a pop. The newest entry always leaves first, so a stack is last in, first out (LIFO). That suits work undone or resumed in reverse order: an undo history, a browser's back button, or retracing your steps out of a maze, called backtracking. In "Recursive structures: binary search", the caller that waited most recently always resumed first, so computers keep activations on a call stack: each call pushes one and each return pops it.

Worked example: checking brackets

Check whether the brackets in ([]{()}) are properly nested. Rule: push each opening bracket; at each closing bracket, pop one and check that they match. 1. ( and [ are pushed; bottom to top, the stack is ( [. 2. ] pops [, a match. 3. { and ( are pushed, giving ( { (. 4. ) pops (, a match. 5. } pops {, a match. 6. The last ) pops the first (, a match. 7. The input is finished and the stack is empty, so the brackets are balanced. For ([)], the ) pops [, a mismatch, so it is rejected. A pop from an empty stack, or an entry left at the end, is also an error.

Queues: first in, first out

In a queue, entries join only at the tail and leave only at the head, like people waiting at a ticket window. They leave in the order they arrived, so the rule is first in, first out (FIFO). Adding is often called enqueuing and removing dequeuing. Queues handle work in arrival order: documents waiting for a printer, requests waiting for a web server, and the roughly FIFO job queue in "The history of operating systems". A buffer, a holding area for data on its way from one place to another, is usually a queue, so data comes out in the order it went in.

Worked example: a printer queue

Ana, then Ben, then Caro send documents to a shared printer. Track the queue from head to tail. 1. After the three arrivals: Ana, Ben, Caro. 2. The printer takes the head, so Ana's prints, leaving Ben, Caro. 3. Dev's document joins the tail: Ben, Caro, Dev. 4. Ben's and then Caro's print, leaving Dev. 5. Eli's arrives: Dev, Eli. Check: the printing order Ana, Ben, Caro matches the arrival order, as FIFO requires. A stack would have printed Caro's first, and with new documents arriving, Ana's could wait at the bottom indefinitely.

Stacks and queues in Python

A Python list already works as a stack if you only use its end. Line 1: stack = []. Line 2: stack.append(4). Line 3: stack.append(9). Line 4: print(stack.pop()) prints 9, leaving [4]. For a queue, list.pop(0) works but shifts every remaining entry forward, which is slow on long lists, so the standard library offers a double-ended queue. Line 1: from collections import deque. Line 2: queue = deque(). Line 3: queue.append("A"). Line 4: queue.append("B"). Line 5: print(queue.popleft()) prints A, leaving B at the head.

Trees

A tree arranges entries in a hierarchy, like folders on a computer or the parse trees of "Language implementation: translation and compilers". Each position is a node. The top node is the root, and nodes with nothing below them are leaves, or terminal nodes. The nodes directly below a node are its children, it is their parent, and children of one parent are siblings. One rule makes a tree a tree: every node except the root has exactly one parent, so branches never rejoin. A node with everything below it is itself a tree, a subtree. In a binary tree, no node has more than two children, called left and right.

Worked example: a folder tree

Folder Home holds Docs, Music and Photos; Docs holds School and Taxes; Photos holds Trips. 1. The root is Home, the only node without a parent. 2. The leaves are School, Taxes, Music and Trips, which have no children. 3. Docs, Music and Photos are siblings. 4. Counting the root as level 1, the tree has 3 levels. Some books call this its depth or height; others count the 2 links on the longest path instead, so check the convention. 5. It is not a binary tree, because Home has three children. 6. Docs, School and Taxes form a subtree.

Common mistakes to avoid

First, mixing up LIFO and FIFO: a stack gives back its newest entry, a queue its oldest. Second, popping or dequeuing without checking whether the structure is empty. Third, using list.pop(0) as a queue on a long list instead of deque.popleft(). Fourth, mixing index conventions: Grades[4, 2], counted from 1, is grades[3][1] in Python. Fifth, calling any branching diagram a tree: if a node has two parents, such as a task depending on two earlier tasks, it is not one. Sixth, thinking a binary tree needs exactly two children per node; it allows at most two.

Key takeaways

A data structure arranges data in the shape a problem needs. A two-dimensional array finds entries by row and column. A list is a sequence with a head and a tail. A stack adds and removes at its top, so it is LIFO; it underlies undo, backtracking and the call stack. A queue adds at the tail and removes at the head, so it is FIFO; it underlies buffers and waiting lines. In Python, a list serves as a stack and collections.deque as a queue. A tree has one root, and every other node has exactly one parent; a binary tree allows at most two children per node.

Flashcards

Flashcard

Data structure

A way of arranging a collection of data in the shape a problem needs

Arrays, lists, stacks, queues, trees.

Test your understanding

Question 1 of 5

Starting with an empty stack, you push 3, push 8, pop, push 5, push 1, and pop. Which value would the next pop return?

Question 2 of 5

An empty queue receives P, Q and R in that order. One entry is removed, S is added, and one more entry is removed. Which entry is now at the head?

Question 3 of 5

In a tree, node K has no parent, K's children are L and M, and L has one child, N. Which nodes are the leaves?

Question 4 of 5

A word processor's undo command must reverse the most recent change first. Which structure fits the change history best?

Question 5 of 5

In our pseudocode, which counts from 1, Seats[2, 5] is row 2, column 5 of an array. Which Python expression names the same entry in a list of rows counted from 0?

← Previous topicNext topic →