B2.2 Data Structures

The Big Picture

A data structure is a way of organising data in memory so it can be used efficiently. You need four, and each has a picture you can keep in your head.

B2.2.1: Static vs Dynamic

You are running a school concert. There are exactly 200 seats. You will never sell seat 201, so a fixed list of 200 is perfect. That is static. You also sell snacks, but nobody knows how many. That list has to grow and shrink. That is dynamic.

Compile time is before the program runs, when the code is translated into machine code. Runtime is while the program is running in memory.

A tuple has a fixed size and its elements cannot be changed:

days = ("Mon", "Tue", "Wed", "Thu", "Fri")
print(days[0])
days[0] = "Monday"

Mon
TypeError: 'tuple' object does not support item assignment

B2.2.2: Lists (1D)

A list stores many values under one variable name. Each value is an element, and each element has an index: its position, starting at 0. In Python, negative indexes count from the end.

Five elements means the last index is 4, not 5. The last index is always len(list) - 1. Asking for index 5 gives an IndexError.

Cheat sheet

Add

names = []                 # empty list
names.append("Angelica")   # add to the end
names.append("Ansh")
names.append("Kai")
names.append("Fabio")
names.append("Michelle")
names.insert(1, "Hana")    # add at index 1, the rest shift right
print(names)
print(len(names))

['Angelica', 'Hana', 'Ansh', 'Kai', 'Fabio', 'Michelle']
6

Read and change

names = ["Angelica", "Hana", "Ansh", "Kai", "Fabio", "Michelle"]
print(names[0])      # first
print(names[-1])     # last
names[2] = "Anshul"  # change an element
print(names)
print("Kai" in names)

Angelica
Michelle
['Angelica', 'Hana', 'Anshul', 'Kai', 'Fabio', 'Michelle']
True

Remove

names = ["Angelica", "Hana", "Ansh", "Kai", "Fabio", "Michelle"]
del names[2]             # by index
print(names)
names.remove("Kai")      # by value (first match)
print(names)
last = names.pop()       # removes AND returns the last item
print(last, names)

['Angelica', 'Hana', 'Kai', 'Fabio', 'Michelle']
['Angelica', 'Hana', 'Fabio', 'Michelle']
Michelle ['Angelica', 'Hana', 'Fabio']

Traverse

Traversing means visiting every element in order. There are three ways in Python. Use the index version when you need the position (or want to change elements).

names = ["Ansh", "Fabio", "Hana"]

# 1. value by value (simplest)
for name in names:
    print(name)

# 2. using the index
for i in range(len(names)):
    print(i, names[i])

# 3. enumerate gives index and value together
for i, name in enumerate(names):
    print(i, name)

Ansh
Fabio
Hana
0 Ansh
1 Fabio
2 Hana
0 Ansh
1 Fabio
2 Hana

B2.2.2: 2D Lists

A 2D list is a list of lists. Picture a table: each inner list is one row. You reach an element with two indexes: [row][column]. Remember it as R before C, like a remote control car.

Daily temperatures for four weeks. Rows are weeks, columns are days.

The highlighted cell is temperature[2][3]: row 2, then column 3.

temperature = [
    [21, 23, 24, 22, 23, 24, 29],
    [22, 20, 19, 18, 18, 17, 20],
    [24, 28, 29, 31, 32, 31, 33],
    [23, 25, 21, 26, 22, 20, 19]
]
print(temperature[2][3])     # row 2, column 3
print(len(temperature))      # number of rows
print(len(temperature[0]))   # number of columns in row 0
temperature[3][2] = 34       # change one element

31
4
7

Traversing a 2D list: the double loop

To visit every element you need a loop inside a loop. The outer loop picks a row. The inner loop goes through every value in that row. Only when the inner loop finishes does the outer loop move to the next row. Python lists are dynamic, so each row can even have a different length.

temperature = [
    [21, 23, 24, 22, 23, 24, 29],
    [22, 20, 19, 18, 18, 17, 20],
    [24, 28, 29, 31, 32, 31, 33],
    [23, 25, 21, 26, 22, 20, 19]
]
temperature[1].append(24)    # rows can grow: dynamic
temperature[2].append(25)

total = 0
count = 0
for row in temperature:          # outer loop: each row
    for value in row:            # inner loop: each value in that row
        total = total + value
        count = count + 1

print("Average:", round(total / count, 1))

Average: 23.8

Need the positions too? Use indexes: for r in range(len(grid)): then for c in range(len(grid[r])): and read grid[r][c].

# RIGHT: a new row list is made each time
seats = [["" for col in range(3)] for row in range(2)]
seats[0][1] = "Ivan"
print(seats)

# WRONG: every row is the SAME list
bad = [[""] * 3] * 2
bad[0][1] = "Ivan"
print(bad)

[['', 'Ivan', ''], ['', '', '']]
[['', 'Ivan', ''], ['', 'Ivan', '']]

ROWS = 3
COLS = 4
plan = [["empty" for c in range(COLS)] for r in range(ROWS)]

plan[0][0] = "Ana"
plan[1][2] = "Ivan"
plan[2][3] = "Leo"

for r in range(ROWS):
    print("Row", r, ":", plan[r])

Row 0 : ['Ana', 'empty', 'empty', 'empty']
Row 1 : ['empty', 'empty', 'Ivan', 'empty']
Row 2 : ['empty', 'empty', 'empty', 'Leo']

B2.2.3: Stacks (LIFO)

Think of a pile of plates, or a tube of Pringles. You can only add to the top and take from the top. The plate you put on last is the first one you take off. That is LIFO: Last In, First Out (also called FILO, first in, last out).

Every operation touches only the top, so it takes the same time however big the stack is: O(1). Reaching the bottom item is O(n), because everything above it must be popped first. (Big O comes properly in B2.4.)

A Python list already works as a stack: the end of the list is the top.

stack = []

stack.append("A")      # push
stack.append("B")      # push
stack.append("C")      # push
print(stack)

print(stack[-1])       # peek: look at the top
print(stack.pop())     # pop: remove the top
print(stack.pop())
print(stack)
print(len(stack) == 0) # isEmpty

['A', 'B', 'C']
C
C
B
['A']
False

Wrapping it in a class gives the exact method names the exam uses. Here it powers an undo button:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            return None            # stack underflow: nothing to pop
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0


history = Stack()
history.push("type Hello")
history.push("make bold")
history.push("delete word")
print("Undo:", history.pop())
print("Undo:", history.pop())
print("Next undo would be:", history.peek())

Undo: delete word
Undo: make bold
Next undo would be: type Hello

Where stacks are used

def balanced(text):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in text:
        if ch in "([{":
            stack.append(ch)                 # opening: push
        elif ch in ")]}":
            if len(stack) == 0 or stack.pop() != pairs[ch]:
                return False                 # closing with no match
    return len(stack) == 0                   # empty stack = all closed

print(balanced("print((a + b) * [c])"))
print(balanced("if (x > 1 {"))

True
False

word = "NINJA"
stack = []
for ch in word:
    stack.append(ch)        # push every letter

reversed_word = ""
while len(stack) > 0:
    reversed_word = reversed_word + stack.pop()   # pop comes out backwards
print(reversed_word)

AJNIN

B2.2.4: Queues (FIFO)

Think of the line at a shop till. You join at the back. People are served from the front, in the order they arrived. Nobody pushes in. That is FIFO: First In, First Out.

Reaching the item at the back is O(n), because everything in front of it must be dequeued first.

Python's deque (double ended queue, said "deck") is built for this. A plain list works too with pop(0), but that is slow, O(n), because every other item has to shift one place left.

from collections import deque

queue = deque()

queue.append("Job 1")    # enqueue: join the back
queue.append("Job 2")
queue.append("Job 3")
print(list(queue))

print(queue[0])          # front: look without removing
print(queue.popleft())   # dequeue: leave from the front
print(queue.popleft())
print(list(queue))
print(len(queue) == 0)   # isEmpty

['Job 1', 'Job 2', 'Job 3']
Job 1
Job 1
Job 2
['Job 3']
False

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.popleft()

    def front(self):
        if self.is_empty():
            return None
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0


playlist = Queue()
for song in ["Song A", "Song B", "Song C"]:
    playlist.enqueue(song)

while not playlist.is_empty():
    print("Now playing:", playlist.dequeue())

Now playing: Song A
Now playing: Song B
Now playing: Song C

Where queues are used

Try It: Live Stack and Queue

Click the buttons and watch where items go in and where they come out. Orange is the next item to leave.

Stack vs Queue

Choosing the Right Structure

Ask three questions. Do I know how many items there will be? (static or dynamic) Is the data a line or a grid? (1D or 2D) Does the order of removal matter? (newest first = stack, oldest first = queue)

The textbook's thinking skills task, answered:

Practice Questions

gym = [
    [[(8, "Pilates")], [(18, "Boxfit")], [(13, "Attack")], [(9, "Pilates"), (19, "Boxfit")], [(14, "Attack")], [(8, "Pilates")], [(8, "Pilates"), (10, "Boxfit")]],
    [[(10, "Boxfit")], [(9, "Pilates"), (17, "Attack")], [(19, "Boxfit")], [(9, "Pilates")], [(9, "Baby Yoga")], [(8, "Pilates")], [(8, "Pilates")]],
    [[(8, "Pilates")], [(11, "Boxfit"), (17, "Yoga")], [(18, "Pilates")], [(12, "Boxfit")], [(18, "Pilates"), (19, "Attack")], [(8, "Pilates"), (10, "Boxfit")], [(8, "Pilates")]],
    [[(18, "Pilates")], [(18, "Boxfit")], [(19, "Pilates")], [(19, "Boxfit")], [(19, "Pilates")], [(8, "Pilates")], [(8, "Pilates")]],
]

pilates = 0
for week in gym:                 # each row (week)
    for day in week:             # each cell (day)
        for hour, name in day:   # each class on that day
            if name == "Pilates":
                pilates = pilates + 1
print("Pilates classes:", pilates)

Pilates classes: 18

evening = 0
for week in gym:
    for day in week:
        for hour, name in day:
            if hour == 18 or hour == 19:
                evening = evening + 1
print("Evening classes:", evening)

Evening classes: 11

days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
boxfit = []
for w in range(len(gym)):
    for d in range(len(gym[w])):
        for hour, name in gym[w][d]:
            if name == "Boxfit":
                boxfit.append("Week " + str(w + 1) + ", " + days[d] + ", " + str(hour) + ":00")

for c in boxfit:
    print(c)

Week 1, Tuesday, 18:00
Week 1, Thursday, 19:00
Week 1, Sunday, 10:00
Week 2, Monday, 10:00
Week 2, Wednesday, 19:00
Week 3, Tuesday, 11:00
Week 3, Thursday, 12:00
Week 3, Saturday, 10:00
Week 4, Tuesday, 18:00
Week 4, Thursday, 19:00