B2.2 · Book pp. 342–357

Data structures

Your level SL HL

The way you organize data decides what your program can do quickly. Choosing a good structure often matters more than clever code.

What you need to know

B2.2.1 Compare static and dynamic data structures.
B2.2.2 Construct programs that apply arrays and lists.
B2.2.3 Explain the concept of a stack as Last In First Out.
B2.2.4 Explain the concept of a queue as First In First Out.

⚠️ Common mistake

“Compare” needs similarities as well as differences. And “stacks are used for undo” earns little. Explain how: actions are pushed, and undo pops the latest one.

Next: static and dynamic →

B2.2.1 Static and dynamic structures

	Static	Dynamic
Size	Fixed when created	Grows and shrinks at runtime
Memory	Contiguous, and reserved whether used or not	Allocated as needed, often not contiguous
Access	Direct, by index	Depends on the structure. A linked list is sequential
Insert in the middle	Slow, as items must shift	Fast in a linked structure, once the position is found
Programming	Simpler	Needs more care over size and memory
Similarity	Both store and organize many items under one identifier, and both can be traversed with loops

✏️ Book corrections

The book says elements in a dynamic structure cannot be directly accessed, yet later says ArrayLists allow random access. Python lists and Java ArrayLists are dynamic and indexed. It is linked lists that need sequential access.
It says static structures have no overflow or underflow. They do: its own fixed-size stack has both errors. A fixed size is what makes overflow possible.
It says dynamic structures waste no memory. Linked structures use extra memory for pointers, so efficient is fairer than no waste.

Next: arrays and lists →

B2.2.2 Arrays and lists

An array holds many elements under one identifier, reached by an index. Java arrays have a fixed size and one type. Python lists are dynamic, but can be used in the same way.

grades = [75, 64, 95, 50, 34]

print(grades[2])        # direct access
grades[2] = 96          # change one element

total = 0
for g in grades:        # traverse
    total = total + g
print("Average:", total / len(grades))

smallest = grades[0]    # not 0!
for g in grades:
    if g < smallest:
        smallest = g
print("Smallest:", smallest)

Parallel arrays are arrays of the same size where one index links related values.

names = ["Mali", "Niran", "Asha"]
ages = [16, 17, 16]

for i in range(len(names)):
    print(names[i], "is", ages[i])

Two-dimensional arrays

A 2D array is a table. The first index is the row and the second is the column, and processing it takes two nested loops.

numbers = [[1, 2, 3],
           [4, 5, 6],
           [7, 8, 9]]

print(numbers[1][2])

for r in range(3):
    for c in range(3):
        print(numbers[r][c], end=" ")
    print()

# Sum of the main diagonal
total = 0
for i in range(3):
    total = total + numbers[i][i]
print(total)

# A trap: these three rows are the SAME list
bad = [[0] * 3] * 3
bad[0][0] = 9
print(bad)

# Do this instead
good = [[0 for c in range(3)] for r in range(3)]
good[0][0] = 9
print(good)

✏️ Book correction

The book shows a new Java 2D array as empty, with “no initial values”. Java fills a new int array with zeros, as the book said earlier about 1D arrays.

Dynamic lists

`grades.append(75)`	Add to the end
`grades.insert(0, 64)`	Insert at an index
`grades.remove(75)`	Remove the first matching value
`grades.pop(0)`	Remove by index
`grades.pop()`	Remove the last item
`grades.clear()`	Empty the list
`len(grades)`	Number of items

Java’s ArrayList offers add, get, set, remove, size and clear. It stores objects, so write ArrayList<Integer> rather than int.

colours = ["red", "green", "blue"]
colours.append("gold")
colours.insert(1, "pink")
colours.remove("blue")
last = colours.pop()
print(colours, last, len(colours))

Next: stacks →

B2.2.3 Stacks

A stack only allows access to its top, like a pile of plates. It is an abstract data structure, built from an array (fixed size) or a linked list.

SIZE = 4
stack = [None] * SIZE
top = -1

def is_empty():
    return top == -1

def is_full():
    return top == SIZE - 1

def push(value):
    global top
    if is_full():
        print("Stack overflow")
    else:
        top = top + 1
        stack[top] = value

def pop():
    global top
    if is_empty():
        print("Stack underflow")
        return None
    value = stack[top]
    top = top - 1
    return value

push(5)
push(12)
print(pop())
print(pop())
print(pop())

✏️ Book note

The book’s pop only moves the pointer, and discards the value. A pop normally returns the value it removes, as above.

Uses of stacks

Undo: actions are pushed, and undo pops the last.
Browser back: visited pages are pushed, and back pops.
Interrupts: return addresses are pushed, then popped to resume.
Recursion: each call’s return address and parameters are stored.
Reverse Polish: operands are pushed, and an operator pops two.

Next: queues →

B2.2.4 Queues

A queue adds at the rear and removes from the front, using two pointers. Operations are enqueue, dequeue, isEmpty, isFull and front.

SIZE = 4
queue = [None] * SIZE
front = 0
count = 0

def enqueue(value):
    global count
    if count == SIZE:
        print("Queue overflow")
    else:
        rear = (front + count) % SIZE   # % wraps around
        queue[rear] = value
        count = count + 1

def dequeue():
    global front, count
    if count == 0:
        print("Queue underflow")
        return None
    value = queue[front]
    front = (front + 1) % SIZE
    count = count - 1
    return value

for job in ["a", "b", "c", "d"]:
    enqueue(job)
print(dequeue(), dequeue())
enqueue("e")
print(queue)

Uses of queues

Printing: jobs are served in the order they were sent.
Keyboard buffer: characters appear in the order they were typed.
Simulations: checkouts, traffic and car parks.

Try it: reverse a queue using a stack

Dequeue every item and push it. Then pop every item and enqueue it. The order is reversed.

Next: review →

Quick quiz

1. A static data structure…

2. If grades has 5 items, the last index is…

3. numbers[1][2] means…

4. To find a smallest value, start min at…

5. Parallel arrays are linked by…

6. A stack works on…

7. A queue works on…

8. Pushing to a full fixed-size stack causes…

9. Which suits a printer?

Exam-style questions

These are written for this site in the style of Paper 2. Answer on paper first, then open the mark points.

Compare static and dynamic data structures. [4]
Mark points
- Both store a collection of items under one identifier [1].
- Static has a fixed size, while dynamic can change at runtime [1].
- Static may waste memory, while dynamic uses it as needed [1].
- Static allows direct access, while linked dynamic structures are accessed sequentially [1].
Identify the most suitable type and structure to hold 30 student names, in order of arrival. [2]
Mark points
- Strings [1].
- A one-dimensional list or array [1].
A 2D list scores has 6 rows and 6 columns. Construct code to output the total of each row. [4]
Mark points
- A loop for each row [1].
- Set total to 0 inside it [1].
- A nested loop adding scores[r][c] [1].
- Output total after the inner loop [1].
Outline two uses of a stack in a computer system. [4]
Mark points
- Undo in an editor: actions are pushed [1], and undo pops the latest [1].
- Interrupts: return addresses and values are pushed [1], and popped to resume [1].
Outline the difference between a linear queue and a circular queue held in an array. [4]
Mark points
- In a linear queue, removed slots at the front are not reused [1].
- So it can appear full while there is space [1].
- A circular queue wraps the rear pointer back to the start [1].
- This reuses freed slots [1].
Evaluate 5 2 * 3 2 + − using a stack. [2]
Mark points
- After 5 2 *: the stack holds 10. After 3 2 +: it holds 10, 5 [1].
- 10 − 5 = 5 [1].