Computer Science › Section I · Data abstractions › Topic I.2
Related concepts: abstraction and pointers
Stacks, queues and trees do not exist inside a memory chip; software creates them. Three ideas explain how: abstraction, the difference between structures that stay fixed and structures that grow, and pointers, addresses stored as data.
Structures that exist only in software
A computer's main memory holds no tables, stacks or trees, only a long sequence of numbered cells. Every structure in "Basic data structures" must therefore be simulated: software stores the entries in cells and keeps the bookkeeping that makes them behave like a stack or a tree. The people and programs that use the structure see only the convenient shape and its operations, such as push and pop, while the details of where each entry sits are hidden. In that sense data structures are abstract tools, an example of the abstraction theme from "The big themes of computer science and its impact on society".
Who is the user?
The user of an abstract tool is not always a person. It depends on where you stand. For someone keeping a club's scores, the user is a human, and a spreadsheet presents the data as a grid. For a web server, the user is a client program, and the server decides what shape the client sees, perhaps a list of search results. Inside one program, the user may be another module that calls functions such as add_member without knowing how the members are stored. In every case the provider of the data takes responsibility for presenting it in a convenient form, and the user gains the right to ignore what lies beneath.
Static and dynamic structures
A static structure keeps the same size and shape while it is in use. A chessboard of 8 × 8 squares, or a table of 24 hourly readings for each of 7 days, never needs a new entry. A dynamic structure grows and shrinks: a list of users currently online, an inbox, or a waiting list. Static structures are easier to manage, because the software only has to find entries and change their values. A dynamic structure must also make room for new entries and tidy up after deletions. If it is poorly designed, adding one entry might force the whole structure to be rearranged, or copied to a larger area of memory.
Pointers: addresses stored as data
A memory address is just a number, so it can itself be stored in a memory cell. A pointer is a storage location that holds an address. Following a pointer means reading the address it holds and then going to that address; this is also called dereferencing. Pointers let one item record where another is kept. If an item must be moved around memory, a program can keep one fixed pointer to it and update only that pointer after each move, so the item can always be found. You have met a pointer already: the program counter from "Program execution and the machine cycle" holds the address of the next instruction, and x86 processors even call it the instruction pointer.
Worked example: following a chain of pointers
A recipe app stores records alphabetically, two cells each: a name, then a pointer to the next recipe of the same cuisine. Bibimbap is at 0x30, Carbonara at 0x32, Gnocchi at 0x34, Kimchi stew at 0x36, Lasagne at 0x38 and Risotto at 0x3A. The pointer cells hold: 0x31: 0x36, 0x33: 0x34, 0x35: 0x38, 0x37: 0x30, 0x39: 0x3A, 0x3B: 0x32. List the Italian dishes, starting from Lasagne. 1. Lasagne's pointer at 0x39 holds 0x3A: Risotto. 2. 0x3B holds 0x32: Carbonara. 3. 0x33 holds 0x34: Gnocchi. 4. 0x35 holds 0x38, back to Lasagne, so stop. Four Italian dishes, found without looking at either Korean one.
Pointers in programming languages
C makes pointers an ordinary data type. After int x = 4; the declaration int *p = &x; makes p hold the address of x, since & means "address of". Then *p means "the cell p points to", so *p = 9; changes x to 9. C also allows pointer arithmetic: if p points into an array, p + 1 points to the next entry, whatever its size in bytes. That power is risky, because nothing stops a pointer running past the end of the array. Java therefore offers only references, which cannot be changed by arithmetic. In Python every variable is a reference to an object, as "Procedural units: functions and parameters" explained, and Python has no pointer arithmetic at all.
Worked example: pointer arithmetic in C
Trace this C fragment. Line 1: int a[3] = {10, 20, 30}; Line 2: int *p = a; Line 3: p = p + 2; Line 4: *p = 99; 1. Line 1 stores three integers in consecutive locations. 2. In C, an array name used this way gives the address of its first entry, so p points to a[0]. 3. Adding 2 moves p two entries along, to a[2], not two bytes. 4. Writing through p changes a[2], so the array becomes 10, 20, 99. 5. Danger check: p + 3 would point just past the end of the array, and writing through it might overwrite whatever lies there or crash. C does not catch this; the behaviour is undefined.
The null pointer
A pointer sometimes needs to say "there is nothing here", for example at the end of a chain. A special value, the null pointer, means exactly that. It is written NULL in C, null in Java and None in Python. If no item is ever stored at address 0, then 0 can never be a real target, so many systems use 0 as the null pointer. Following a null pointer is a classic bug: a C program may crash, Java raises a NullPointerException, and in Python, trying to use an attribute of None raises an AttributeError. Code that follows pointers should test for null before every step.
Garbage collection and memory leaks
Dynamic structures keep claiming memory and giving it back. Automatically reclaiming space that nothing uses any more is called garbage collection. Java, Python and C# do it: once no reference leads to an object, the system may reuse its space. In C the programmer requests space with malloc and must release it with free. Forgetting to release space that is no longer needed causes a memory leak, in which free memory slowly dwindles until a long-running program slows or fails. The opposite error is freeing space too early, leaving a dangling pointer that still holds the old address, so later use may read or overwrite someone else's data.
Common mistakes to avoid
First, confusing a pointer with what it points to: the pointer holds an address, and following it gives the data. Second, thinking abstract structures are built into memory hardware; they are simulated by software. Third, following a pointer without checking for null. Fourth, assuming p + 1 in C adds one byte; it moves one whole entry. Fifth, believing automatic garbage collection makes leaks impossible: if a program keeps a reference to data it will never use again, such as an ever-growing cache, that data cannot be reclaimed. Sixth, treating a dynamic structure as if it were static and leaving no room to grow.
Key takeaways
Memory is a sequence of cells, so arrays, stacks, queues and trees are abstract tools simulated by software, and their users, whether people, clients or modules, can ignore the storage details. Static structures keep their size; dynamic ones grow and shrink and are harder to manage. A pointer stores an address, and following it reaches the data; the program counter is one. C exposes pointers and pointer arithmetic, Java restricts them to references, and Python variables are all references. A null pointer marks "nowhere". Garbage collection reclaims unused space; failing to free it causes leaks, and freeing it too early leaves dangling pointers.
Flashcards
Flashcard
A structure used through its shape and operations while storage details stay hidden
Test your understanding
Question 1 of 5
Which of these is best described as a dynamic structure?
Question 2 of 5
Cell 0x50 holds 0x6C, and cell 0x6C holds 0x21. If cell 0x50 is used as a pointer, what value do you reach by following it?
Question 3 of 5
In C, after int x = 4; and int *p = &x; the statement *p = *p + 3; runs. What does x hold now?
Question 4 of 5
A server program keeps requesting memory for each new message but never releases the memory of old messages it has finished with. What is this problem called?
Question 5 of 5
Why is a queue described as an abstract tool?
