Core Data Structures in C

Two ways into the same idea

Before You Start

The Core Idea: argc/argv as Your First "Data Structure" Received

Before building your own structures, the argc/argv project teaches you how your program receives data from outside it in the first place:

int main(int argc, char *argv[])
{
    int i;

    /* argc: number of arguments including the program's own name */
    /* argv: an array of strings, argv[0] is the program's name */
    for (i = 0; i < argc; i++)
        printf("argv[%d] = %s\n", i, argv[i]);
    return (0);
}
/* run: ./program hello world
   argv[0] = ./program
   argv[1] = hello
   argv[2] = world
   argc = 3 */

Linked Lists: Singly and Doubly

Figure 1, each node holds a value and a single pointer to the next node only; to go backward you must traverse the whole list from the start.

Figure 2, each node holds two pointers: to the next node and the previous one together, allowing traversal in both directions at a small extra memory cost.

Worked Example: Building a Node and Adding It to a Singly Linked List's Front

typedef struct node_s
{
    int data;
    struct node_s *next;
} node_t;

node_t *push_front(node_t *head, int value)
{
    node_t *new_node = malloc(sizeof(node_t));

    if (new_node == NULL)
        return (head);          /* allocation failed: return the list unchanged */
    new_node->data = value;
    new_node->next = head;       /* the new node points to what was the list's start */
    return (new_node);           /* it's now the new head of the list */
}

Figure 3, Notice this is exactly the same "pointer as address" logic from Part Six, all you're doing is linking addresses together instead of copying whole pieces of data.

Hash Tables and Binary Trees

Figure 4, a binary search tree: to find any value, compare with the root and go left if smaller or right if larger, and repeat, without needing to check every node.

Insertion into a BST follows exactly the same logic as search: start at the root and compare, go left or right based on the comparison, and repeat until you reach an empty (NULL) spot, where you place the new node, no need to reorder the whole tree. Deletion is a bit trickier: deleting a leaf (no children) is simple, and deleting a node with one child just means "skipping over it" by linking its parent directly to its child, but deleting a node with two children requires finding its "successor", the smallest value in its right subtree, and putting it in the deleted node's place so the tree's ordering stays correct.

Deep Dive: Linked Lists: Nodes, Pointers and Rewiring

Linked lists are the first time you build a structure from scattered pieces tied together by pointers. The idea matters more than the code here: where the nodes sit, how pointers are rewired on insertion and deletion, and when a list beats an array and when it loses.

1. The node and the head

A node is a structure carrying a value and a pointer to the next node (a struct containing a pointer to its own type). A list has no index; all you hold is a pointer to the first node called the head, and the list ends at a node whose next pointer is NULL. An empty list has a head that is NULL itself. Each node is usually reserved with its own malloc, so they are scattered in the heap in no order, and only the pointers connect them.

Figure 5, A singly linked list of three nodes: each node knows only the next one.

2. Insertion and deletion are rewiring, not moving

The list’s advantage is that no data moves on insertion: you reserve a new node then change two pointers. Order matters greatly: make the new node point to what follows first, then make the previous node point to the new one. Reverse it and you lose the rest of the list, because the only pointer to it was overwritten. On deletion you reconnect the previous node to what follows the deleted one then free the deleted one, otherwise memory leaks or a freed node gets used. The edge cases where many fail: inserting at the head (the head itself changes, so you need a pointer to a pointer or to return the new head), deleting the head, the empty list, and a position beyond the length.

Figure 6, Inserting a node between A and B: connect the new node to what follows before changing A’s pointer.

3. The doubly linked list

The doubly linked list adds to each node a pointer to the previous one as well. Its value is walking in both directions and deleting a node while holding only a pointer to it, without searching for its predecessor from the head. Its cost is an extra pointer in every node (more memory) and two extra operations in each insertion and deletion, and a mistake in one direction silently corrupts the list. So keep a fixed invariant: if a points to b via next, then b points to a via prev.

Figure 7, A doubly linked list: each link has two faces that must stay consistent.

4. A list or an array?

The summary of the comparison: choose the list when insertion and deletion are frequent and random access is rare. But in many real cases the array wins despite Big O theory because contiguous memory helps the processor cache, so do not judge by theory alone, measure.

Deep Dive: Hash Tables, Collisions and the Load Factor

A hash table promises something that sounds impossible: reaching any item by any key in nearly constant time. We detail how it does that and when the promise collapses.

1. The idea: turn the key into an index

An array gives instant access but by a numeric index. A hash function turns any key, even text, into a number then takes the remainder of dividing it by the array size to get an index. A bucket is then known for every key, and you look in it directly instead of walking over all items.

2. What makes a good hash function?

3. Collisions are inevitable

The number of possible keys is far larger than the number of buckets, so two different keys will necessarily produce the same index, and this is a collision. The birthday paradox explains it: in a room of only 23 people the chance that two share a birthday exceeds half, so collisions happen very early, long before buckets fill. So what matters is not preventing collisions but handling them. There are two main approaches:

Figure 8, Chaining: apple and grape reached bucket 2 so they line up in one list.

4. The load factor and why it matters

The load factor is the number of items divided by the number of buckets. As it rises, chains grow longer and search time degrades from near constant to near linear. That is why serious tables rebuild themselves into a larger array (rehashing) when a given factor is exceeded. In the worst case, if all keys land in one bucket, the table becomes one linked list and the search time is O(n).

Many systems use them: dictionaries in languages, caches, symbol tables in compilers, database indexing, and counting word frequencies.

Deep Dive: Binary Trees: Terminology, Traversal and Balance

A binary tree is hierarchical as the list is linear. Here we learn the language for describing trees, then the ways of walking over them, and then why balance makes a big difference to performance.

1. Essential terminology

Figure 9, A tree of size 8 and height 3: the leaf farthest from the root is 10 at depth 3.

2. A plain binary tree or a binary search tree?

In a plain binary tree each node has at most two children, with no condition on the values. A binary search tree (BST) imposes an order: everything in a node’s left branch is smaller than it and everything in the right is larger. With this condition search resembles binary search: at each node you compare and discard half of the possibilities, reaching your target in time proportional to the height, not the size.

3. Traversal methods

Walking a tree means visiting each node once, and the order differs by when you visit the node relative to its children. In depth there are three ways expressed by a simple recursive definition, and in breadth one way that goes layer by layer using a queue.

4. Kinds of binary trees

In a perfect tree of height h the number of nodes is 2^(h+1) − 1, so a tree of about a million nodes has a height of only about 20. That is its power: the height is logarithmic in the size. But if you insert sorted values into a plain BST, every node gets one child and the tree turns into a linked list of height n, and the benefit collapses. Balance is what guarantees performance, and the reason self-balancing trees (AVL, red-black) exist.

Figure 10, Shape governs performance: the same nodes, a different search time.

Try it yourself

Quick Review Flashcards

Check Your Understanding