Compare structures by looking at how they allocate memory and whether their capacity can change. These choices affect speed, memory usage and flexibility. Neither approach is always better; choose according to the problem.

Size and capacity

Once created, a static data structure has a fixed capacity. The elements can change, but the number of allocated positions cannot.

A dynamic data structure can change its size while a program runs. It manages storage so that elements can be added or removed without the programmer setting a permanent size at creation.

Size counts the elements currently stored; capacity counts how many elements the allocated storage can hold. Some capacity may therefore be unused.

Here, static refers to the structure's capacity, not Java's static keyword. A Java array is fixed-size even when its length is calculated while the program is running.

Memory allocation and resizing

A fixed-size array allocates storage for a set number of indexed positions. These form an indexed block, so an element's position can be calculated directly from its index. If the program needs a larger array, it must allocate a different one and copy the existing elements. The original array has not grown.

Java's ArrayList and Python's list are dynamic structures that use resizable backing arrays. Their storage usually has spare capacity. An added element takes a spare position if one is available. Otherwise, the structure allocates a larger backing array and copies the existing entries. Python lists store references to objects, rather than all the objects themselves, in the list's storage.

Removing an element reduces a dynamic list's size, but its capacity does not necessarily fall immediately. The list may keep reserved storage for later additions.

Comparing the trade-offs

Dynamic doesn't mean slower for every operation. Both arrays and array-backed lists support fast indexed access. Operations such as resizing and shifting elements account for the extra costs.

Choosing for a situation

A device that always records exactly 12 monthly totals can use a fixed-size array for simple, predictable allocation. The number of positions is already known, so dynamic resizing offers little benefit.

In a club registration system, the number of members is unknown. A dynamic list avoids the need to choose an arbitrary maximum. Occasional resizing and spare capacity are reasonable costs for allowing registrations and withdrawals.

Key terms: static data structures, dynamic data structures, memory allocation, resizing, speed, memory usage, flexibility.

Construct programs by choosing a suitable structure, accessing positions with valid indices, and using loops to process its elements. Java uses fixed-size arrays and dynamic ArrayList objects; Python uses dynamic lists for both one-dimensional and two-dimensional collections.

One-dimensional and two-dimensional structures

An array is an indexed collection with a fixed number of positions. A one-dimensional array uses one index; a two-dimensional array uses a row index followed by a column index.

A list is an ordered collection whose elements can be accessed by position. Java's ArrayList and Python's list allow its size to change.

Indexing starts at 0 in both languages. A collection containing 3 elements has valid indices 0, 1 and 2; index 3 is outside its bounds.

Worked example: indexing and traversal

The Java and Python versions perform the same steps: change the middle daily count to 8, total the daily counts, traverse the rows and columns of the two-dimensional structure, and print the results. Traversal means visiting the elements in a structure, usually to inspect or process each one.

Java — arrays

1  public class RepairTotals {
2      public static void main(String[] args) {
3          int[] daily = {4, 7, 5};
4          int[][] repairs = {{2, 3, 4}, {5, 6, 7}};
5          daily[1] = 8;
6          int dailyTotal = 0;
7          for (int count : daily) {
8              dailyTotal += count;
9          }
10         int gridTotal = 0;
11         for (int row = 0; row < repairs.length; row++) {
12             for (int column = 0; column < repairs[row].length; column++) {
13                 gridTotal += repairs[row][column];
14             }
15         }
16         System.out.println(dailyTotal);
17         System.out.println(gridTotal);
18         System.out.println(repairs[1][2]);
19     }
20 }

Python — lists

1  daily = [4, 7, 5]
2  repairs = [[2, 3, 4], [5, 6, 7]]
3  daily[1] = 8
4  daily_total = 0
5  for count in daily:
6      daily_total += count
7  grid_total = 0
8  for row in range(len(repairs)):
9      for column in range(len(repairs[row])):
10         grid_total += repairs[row][column]
11 print(daily_total)
12 print(grid_total)
13 print(repairs[1][2])

The outer loop selects a row; the inner loop visits every column in that row. Using the current row's length keeps the column index within that row's bounds.

The trace below uses the Java variable names; Python's daily_total and grid_total hold the same values. A dash means that the variable has not yet been initialized or is not active at that stage.

Adding, removing and traversing a dynamic list

Java — ArrayList

1  import java.util.ArrayList;
2  public class RepairList {
3      public static void main(String[] args) {
4          ArrayList<Integer> counts = new ArrayList<>();
5          counts.add(4);
6          counts.add(7);
7          counts.add(5);
8          counts.remove(1);
9          int total = 0;
10         for (int count : counts) {
11             total += count;
12         }
13         System.out.println(counts.size());
14         System.out.println(total);
15     }
16 }

Python — list

1  counts = [4, 7]
2  counts.append(5)
3  counts.pop(1)
4  total = 0
5  for count in counts:
6      total += count
7  print(len(counts))
8  print(total)

Removing index 1 removes the value 7. The value 5 then moves from index 2 to index 1, so the remaining elements still occupy consecutive indices.

Language-specific operations

A Java ArrayList holding integer values uses Integer as its element type. In Java, an integer argument to remove() selects an index; in Python, remove() searches for a matching value, whereas pop() selects an index. Do not confuse removing by position with removing by value.

Key terms: one-dimensional (1D) arrays, two-dimensional (2D) arrays, ArrayLists, Lists, add, remove, traverse.

Explain a stack by identifying the end where operations take place and showing why the last item added is removed first. Link this behaviour to a problem, then to the storage used to implement the stack.

One accessible end

A stack is a last-in, first-out (LIFO) data structure: the last item added is the next one removed. Items are added and removed at the same end, called the top.

LIFO tells us the order of access, not how the stack is implemented. The storage may have a fixed capacity or be able to grow.

Fundamental operations

Both pop and peek require a non-empty stack. The program should check for this or handle the empty-stack case: an empty stack has no valid top item to return. It must also reject or handle a push to a full fixed-capacity stack.

Worked sequence: an undo history

The trace below lists the stack contents from bottom to top. Each stored action must contain enough information for the program to reverse its effects. The stack controls the order; it doesn't perform the reversal itself.

A stack fits this problem because each undo must reverse the most recent remaining action. If the oldest action had to be processed first, a stack would not be appropriate.

Performance and memory usage

For an array-backed stack, the program keeps track of the top position. A normal push writes to the next available position. A pop reads the top item and moves the top position back. Neither operation has to shift all the other elements, while peek and isEmpty also take only a fixed amount of work.

A push that exceeds the backing array's capacity takes more work. A dynamic implementation must allocate larger storage and copy the existing entries into it. That individual push is slower, although most pushes do not resize the storage.

Fixed-capacity implementations reserve storage in advance, including positions that remain unused. A dynamic implementation can grow with the history, though it may keep spare capacity. Popping reduces the number of stored items without necessarily shrinking the allocated capacity immediately. Once the reference to a popped object is removed, its memory can become reclaimable if nothing else refers to it.

Keeping every action indefinitely can use substantial memory. A limit on the undo history saves storage, but users cannot undo actions beyond that limit.

Key terms: stack, last in, first out (LIFO), push, pop, peek, isEmpty, performance, memory usage.

To explain a queue, distinguish the end where items enter from the end where they leave. Show why the earliest item still waiting is removed first. Choosing a queue involves both its service order and how it is implemented.

Two different ends

A queue is a first-in, first-out (FIFO) data structure: the earliest item still waiting is removed next. New items join at the rear; items leave from the front.

FIFO keeps items in arrival order. A stack gives the most recently added item the next turn; a queue does not.

Fundamental operations

Here, front names both the inspection operation and the end where items are removed. The queue must be non-empty before calling front or dequeue. For a fixed-capacity queue, the implementation must also handle an enqueue attempt when no space remains.

Worked sequence: processing print jobs

The trace lists the contents from front to rear.

Use a queue when arrival order should determine service order. There is a limitation: an urgent new job must still wait behind earlier jobs. Ordinary FIFO behaviour does not select jobs by urgency.

Performance depends on implementation

In a simple array-backed implementation, removing the front element may involve shifting every remaining element towards the beginning. The longer the queue, the more work a dequeue takes. Removing index 0 from a Python list or Java ArrayList incurs this shifting cost.

Tracking the front and rear positions avoids moving all the waiting items after each dequeue. The positions can wrap around the allocated storage, allowing vacated positions to be reused. When space is available, enqueue and dequeue then take only a fixed amount of work. Tracking the front position and current size also lets front and isEmpty use only a fixed amount of work.

A dynamic implementation may need to enlarge its backing storage. Allocation and copying make that particular enqueue slower. FIFO alone doesn't guarantee the same performance across implementations.

Memory usage

Enqueue increases the number of stored items; dequeue decreases it. Calling front or isEmpty leaves the queue's contents unchanged.

A fixed-capacity queue reserves predictable storage, but it can become full. A dynamic queue accommodates a changing workload at the cost of spare capacity and possible resizing. Dequeuing does not necessarily reduce the allocated capacity immediately. References to removed items should no longer be retained unnecessarily.

If jobs arrive faster than the printer processes them, the waiting queue grows. More storage can hold a larger backlog. It won't make the printer process jobs faster.

Key terms: queue, first in, first out (FIFO), enqueue, dequeue, front, isEmpty, performance, memory usage.