Dynamic data structures
When you do not know in advance how much data is going to arrive, the array gets in the way. The linked list grows and shrinks by following pointers, and with that mechanism you build queues, stacks and trees.
01When the array is not enough
An array is fast and simple, but its size is fixed, decided before the program runs. If more data arrives than expected, it overflows; if less arrives, memory is wasted. A dynamic structure grows and shrinks during execution, allocating one node per item of data.
| Operation | Array | Linked list |
|---|---|---|
| Access element i | O(1): direct calculation | O(n): you have to traverse |
| Insert at the beginning | O(n): shift everything | O(1): change two pointers |
| Insert at the end | O(1) if there is room | O(n), or O(1) with a pointer to the tail |
| Delete from the middle | O(n): shift everything | O(1) if you already have the previous node |
| Memory per item | Only the data | The data plus a pointer |
| Cache locality | Excellent: contiguous | Poor: scattered nodes |
There is no winner: there is judgment. If you know the size and access by index, use an array. If there are many insertions and deletions at arbitrary positions, use a list. And in practice, for a few elements the array often wins anyway, because contiguous memory flies in the processor’s cache.
02The linked list
Each node holds the data and the address of the next one. The last one points to NULL, and an external variable —the head— holds the address of the first:
typedef struct node {
int data;
struct node *next;
} Node;
Node *head = NULL;
The structure refers to itself: that is why the name struct node is needed inside its
own definition. Inserting at the beginning takes three lines:
Node *n = malloc(sizeof(Node));
n->data = x;
n->next = head;
head = n;
If you do head = n before n->next = head, the node points to
itself and the whole list is lost. In linked structures, the order of pointer assignments
is the most frequent error and the hardest to spot by reading.
Insert and delete nodes, and watch how the pointers rearrange and how many steps each operation costs.
03Variants and derived structures
| Structure | What it is like | What it is for |
|---|---|---|
| Doubly linked list | Each node points to the next and the previous | Traversing in both directions, deleting without searching for the previous node |
| Circular list | The last one points to the first | Round-robin schedulers, buffers |
| Stack (LIFO) | The last item in is taken out | Function calls, undo, evaluating expressions |
| Queue (FIFO) | The first item in is taken out | Communication buffers, event queues |
| Circular queue | Fixed array with indices that wrap around | UART buffers in microcontrollers |
| Binary search tree | Each node has two children, in order | Search in O(log n) if balanced |
Each function call pushes its frame —local variables and return address— and pops it on return. That is why a recursion without a base case ends in a stack overflow: the data structure that overflows is, literally, a stack.
04Binary trees
In a binary search tree, everything smaller than a node is in its left subtree and everything larger is in the right one. Searching means walking down comparing, and if the tree is balanced each comparison discards half of the remaining data: 20 comparisons are enough for a million elements.
- In-order traversal —left, node, right— returns the data sorted from smallest to largest.
- Preorder —node, left, right— is used to copy the structure.
- Postorder —left, right, node— to free it, because it destroys the children before the parent.
The problem is imbalance: if the data arrives already sorted, the tree degenerates into a list and search goes back to O(n). This is the origin of self-balancing trees, such as AVL and red-black trees.
05Where they are used in a device
- UART circular buffer. The receive interrupt writes to the queue and the main program reads: it is the most widely used structure in embedded systems.
- Event queue. A graphical interface, a real-time operating system and firmware with a state machine all use the same producer-consumer scheme.
- A scheduler’s task list. Ordered by priority or by deadline.
- Sample history. A sliding window for averaging or filtering signals is implemented with a circular queue.
- Device table. An operating system kernel maintains linked lists of open processes, files and drivers.
06In the lab
Implement in C insertion at the head, at the tail and in order, deletion by value, search, counting and freeing the whole list. Check with valgrind that no memory is leaked.
Write a fixed-size circular queue with read and write indices, and use it to receive data from a serial port without losing bytes while the program does something else.
Insert a hundred thousand elements at the beginning of an array and of a list, and measure the time of each one. Repeat accessing by index. Contrast the numbers with the table in the first section.
07Common mistakes
- Losing the head of the list by reassigning pointers in the wrong order.
- Freeing a node before saving its
next, and being left with no way to reach the rest. - Not handling the empty list or the deletion of the first node, which are the two edge cases.
- Forgetting to set the
nextof the last node to NULL. - Using a list where an array was the better choice, only because it sounds more sophisticated.
- Traversing with the same pointer that is used to free, without an auxiliary variable.
08Self-assessment
How much does it cost to insert at the beginning of a linked list?
O(1): allocate the node and change two pointers, no matter how many elements there are.
Why is accessing element 500 of a list slow?
Because you have to follow 500 pointers: the address cannot be calculated, you have to traverse.
Which structure suits a UART’s receive buffer?
A circular queue on a fixed array: it needs no malloc, its size is known and an interrupt can use it safely.
Which traversal of a binary search tree returns the data in order?
The in-order traversal: left, node, right.
What happens if already sorted data is inserted into a simple binary tree?
It degenerates into a list: each node has only one child and the search goes from O(log n) to O(n).
Why does infinite recursion end in a “stack overflow”?
Because each call pushes a frame with its local variables, and the program’s stack has a limited size.
09Further reading
- Thomas H. Cormen et al. Introduction to Algorithms. 4th ed., MIT Press, 2022. The reference on data structures and their cost analysis.
- Mark Allen Weiss. Estructuras de datos en C. Addison-Wesley, 1995 (in Spanish). Complete implementations in C, at exactly the level of the course.
- Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language. 2nd ed. (Spanish edition, “El lenguaje de programación C”), Pearson, 1991. Chapter 6 builds a symbol table with linked structures, as a capstone example.
- Robert Sedgewick. Algorithms in C. 3rd ed., Addison-Wesley, 1998. Very graphic, with good explanations of trees and their balancing.