Computer Science › Section I · Data abstractions › Topic I.3
Implementing data structures
Every array, list, stack, queue and tree must end up in plain numbered memory cells. A few simple techniques, an address formula, pointers and wrap-around, are enough to store them all, and translators use them every time you index an array.
Storing a one-dimensional array
For an array Temps of 24 entries, a translator reserves a block of consecutive cells and remembers x, the address of the first entry. Counting positions from 1, as our pseudocode does, entry i lies i − 1 entries past the start, so Temps[5] is at x + 4 when each entry fills one cell. If each entry fills s cells, entry i is at \(x + s(i - 1)\). Python, C and Java count positions from 0, so their formula is \(x + s \cdot i\). This one calculation turns the programmer's numbered row of values into a real address.
Two-dimensional arrays: row-major order
Memory has one dimension, so a table must be laid out in a line. In row-major order, all of row 1 is stored, then row 2, and so on. To reach row i, column j, skip i − 1 whole rows of c entries, then j − 1 more entries. With s cells per entry the address is
and the bracketed part is called the address polynomial. Column-major order stores column after column, so with r rows the bracket becomes \(r(j - 1) + (i - 1)\). C uses row-major order and FORTRAN column-major.
Worked example: finding an entry's address
A table of 6 rows and 9 columns starts at address 200, with 4 cells per entry. Find row 3, column 7. 1. Row-major: skip 2 rows of 9 entries, 18 entries, then 6 more: 24 entries. 2. At 4 cells each, the offset is 96, so the address is 296. 3. Column-major: skip 6 columns of 6 entries, 36, then 2 more: 38 entries, so the address is 200 + 152 = 352. 4. Check: 54 entries × 4 cells = 216 cells, so the last entry starts at 200 + 212 = 412, inside the block. A short program listing every address in order agrees.
Storing records
A record whose fields have fixed sizes can be stored as one block, each field at a known offset from the start. Suppose a Book record has Title in 30 cells, Year in 2 and Pages in 2. If the record starts at x, Book.Year is at x + 30 and Book.Pages at x + 32, so Book.Year = 2024 becomes a store to x + 30. Alternatively, each field can be stored separately, with the record holding a pointer to each. That suits fields that change size: a longer title needs a new home and one updated pointer, not a rebuilt record.
Contiguous lists and linked lists
A contiguous list stores its entries one after another in a single block. That suits a static list, but a dynamic one suffers: a deletion leaves a gap that later entries must shuffle forward to fill, an insertion shuffles them back, and growth may force the whole list to move. A linked list scatters its entries instead, each stored with a pointer to the next. A head pointer holds the address of the first entry, and the last entry's pointer is null, often 0. To traverse the list, follow the head pointer, then each next pointer, until you reach null.
Worked example: editing a linked list
Each entry is a letter followed by the next entry's address. The head pointer holds 0x40. Cell 0x40 holds C and 0x41 holds 0x46; 0x46 holds F and 0x47 holds 0x42; 0x42 holds K and 0x43 holds 0x00, null. The list reads C, F, K. 1. Delete F: copy F's pointer, 0x42, into 0x41, so C leads straight to K. 2. Insert H after C, using free cells 0x48 and 0x49: put H in 0x48. 3. Copy C's pointer, 0x42, into 0x49, so H leads to K. 4. Only then set 0x41 to 0x48. The list reads C, H, K. Doing step 4 before step 3 would lose K's address.
Stacks and queues in a reserved block
A stack lives in a block reserved for its largest expected size. Entries start at one end, the base, and a stack pointer records the top. In this course it holds the address of the next free cell: a push stores the entry there and adds 1; a pop subtracts 1 and reads that cell. The stack is empty when the pointer equals the base. Some designs point at the top entry instead, so check. A queue needs two pointers: a head pointer to the oldest entry and a tail pointer to the first vacancy after the newest. Insert at the tail, remove at the head, and move that pointer on by one.
Worked example: a circular queue
Entries join at the tail and leave at the head, so a queue creeps through memory. A circular queue wraps instead: after the last cell of its block comes the first. Take cells 0xA0 to 0xA4, with head = tail = 0xA0, meaning empty. 1. Insert A, B, C, D into 0xA0 to 0xA3; the tail moves to 0xA4. 2. Remove A and B; the head moves to 0xA2. 3. Insert E at 0xA4; the tail wraps to 0xA0. 4. Insert F at 0xA0; the tail moves to 0xA1. The queue is C, D, E, F. Since head = tail must mean empty, one cell stays unused, so the queue is now full; keeping a count is the alternative.
Storing binary trees
A binary tree is normally stored as linked nodes. Each node is a small block holding the data, a left child pointer and a right child pointer. A missing child is a null pointer, so a leaf has two nulls. A root pointer holds the address of the root node. The nodes can sit anywhere in memory, because the pointers alone record the shape. Adding a node means finding free cells for it and setting one pointer in its parent; nothing else moves.
Trees without pointers
A binary tree can also fill one block with no pointers. Put the root in position 1; the children of the node in position n go in positions 2n and 2n + 1, so the tree is stored level by level. The parent of position n is at n div 2, division rounded down, so position 11's parent is 5. Unused positions hold a special "empty" pattern. This suits a full, balanced tree with nearly complete levels, but wastes space on a tall, thin one: a chain of 4 nodes, each the right child of the last, uses positions 1, 3, 7 and 15, leaving 11 of 15 empty.
Common mistakes to avoid
First, forgetting the entry size: with 4 cells per entry, multiply the offset in entries by 4. Second, using a 1-based formula with 0-based indices. Third, multiplying i − 1 by the number of rows in row-major order; use the number of columns. Fourth, redirecting the previous entry's pointer before copying it into the new entry, which loses the rest of the list. Fifth, letting head = tail mean both empty and full in a circular queue. Sixth, storing a tall, thin tree in the pointer-free layout.
Key takeaways
Arrays occupy consecutive cells, and an address formula, such as the row-major address polynomial, finds each entry. Records keep fields at fixed offsets. Linked lists chain scattered entries from a head pointer to a null, so edits change pointers instead of moving data. A stack uses a block and a stack pointer; a queue uses head and tail pointers and wraps round as a circular queue. Binary trees are linked nodes, or a block with children at 2n and 2n + 1.
Flashcards
Flashcard
Entry i, counted from 1, is at x + s(i − 1)
Test your understanding
Question 1 of 5
A table with 4 rows and 10 columns is stored in row-major order from address 500, one cell per entry, positions counted from 1. What is the address of row 3, column 2?
Question 2 of 5
In a linked list, entry P is followed by entry Q. A new entry N must go between them. Which order of steps is correct?
Question 3 of 5
A circular queue uses cells 0x10 to 0x14 and keeps one cell unused. Its head is 0x13 and its tail is 0x14. After one entry is inserted, where is the tail?
Question 4 of 5
A binary tree is stored without pointers, with the root in position 1. Where are the children of the node in position 6?
Question 5 of 5
Why is a linked list better than a contiguous list for a list with frequent insertions and deletions?
