Data structures
Last week we learned about pointers. Now we use them to organize data intelligently. Grouping related data with a struct, the linked list, the stack and the queue: we will see all of them in live diagrams. This is exactly where it becomes clear why pointers are so important.
What you will learn in this lesson
7.1 What is a structure?
A data structure means a way of storing and managing data in a convenient order. We already know one of them: the array. But an array does not suit every task.
For example, if you want to insert an element into the middle of an array, you have to shift all the rest. Or the size of an array is fixed in advance and cannot grow easily afterwards. For different tasks, a different structure works better.
In this lesson we will look at several: struct (grouping related data), the linked list (a list that grows easily), the stack and the queue (lists with a special order). Most of them are built on top of the pointers from last week.
7.2 struct: grouping data
A student has a name, an age and a grade. You could store them in three separate variables, but they are related to one another. A struct combines exactly these related fields into a single new type.
We access fields through the dot: student.yosh. Enter values below and watch how the struct fills up:
7.3 Array of structs
A struct is just like an ordinary type, so you can make an array of it. struct Student sinf[3]; means: the full data of three students in one array. Now we access each student by index and each field by the dot: sinf[1].baho.
The table below holds three student structs. Click a row and see how it is accessed:
| # | name | age | grade |
|---|
7.4 Linked list
Now pointers come to the rescue. A linked list is made of nodes. Each node stores two things: its own value and a pointer to the next node. In this way the nodes are connected like a chain, and the last one points to NULL (the list has ended).
In the diagram below, each box is one node: the value on the left, an arrow to the next on the right. The green head points to the first node:
7.5 Insert and delete
This is the power of the linked list: to insert or delete a node you do not have to shift the whole array, you only reconnect a few pointers. Inserting at the front is especially fast: the new node points to the old head, and the head points to the new node.
Enter a value below and work with the list. The new node flashes green:
7.6 Array vs linked list
Both store data in sequence, but each has its strengths and weaknesses. The choice depends on the task:
| Property | Array | Linked list |
|---|---|---|
| Access by index | fast (O(1)) | slow (walk from the head) |
| Insert at front | slow (must shift) | fast (O(1)) |
| Size | fixed in advance | grows dynamically |
| Memory | compact | extra per node for the pointer |
In short: if you often access by index, an array is good. If you often insert and delete at the front and the size is unknown, a linked list is good.
7.7 Stack (LIFO)
A stack is a special list that works from only one end. Adding an element is called push, removing one is called pop, and both happen at the top. The rule is LIFO, that is, the last one in is the first one out. Like plates stacked on top of one another.
Try it below. Note: pop always takes the very top one:
Make a prediction
We pushed 1, then 2, then 3 onto an empty stack. If we then pop once, what comes out?
7.8 Queue (FIFO)
A queue is like a stack, but with the opposite rule. An element is added at one end (enqueue) and taken from the other end (dequeue). The rule is FIFO, that is, the first one in is the first one out. Just like a real queue in a shop.
Try it below. Note: dequeue always takes the front one (the first in):
7.9 Practical: which structure to choose?
Choosing a structure depends on the nature of the task. Here are everyday examples:
- You need fast access by index (for example a table): array
- The size is unknown and you often insert and delete: linked list
- Undoing the last action (the back button): stack (LIFO)
- Serving in order of arrival (printer, messages): queue (FIFO)
- Storing several related fields together: struct
7.10 Going deeper advanced
Let us briefly get to know two more powerful structures. Studying them in depth is for later stages; for now we just get a general idea.
Hash table
A hash table is one of the fastest search structures. It turns a key (for example a name) directly into a place in memory using a special function. That is why searching for an element happens in almost one step (O(1)). Ideal for a dictionary or a phone book.
Tree
A tree is a branching, hierarchical structure. Each node can have several "child" nodes. It is used for folders in a file system, a family tree, or fast searching (a binary tree). This too is mostly built on top of nodes and pointers.
Glossary of terms
7.11 Knowledge quiz
16 questions. To complete the week, answer at least 11 of them correctly.
Congratulations! Week 7 is complete
Now you can organize data intelligently: you have learned about struct, the linked list, the stack and the queue. These structures sit at the heart of almost every serious program.
Next week: Recursion and files (self-calling functions, the call stack and working with files).
Go to the next module