Build Linked List in C - Part 1: A simple linked list

Table of contents#

• Overview
• Linked list is what?
  • typedef keywords is to alias struct to a typename, for convenient
  • struct with IntNode tag is still needed in the struct body due to self-referencing
  • Is typedef that convienient and always recommended?
• Now let's initialize a list...
• What's next?

Overview#

The linked list is one of the first data structures any computer science student learn about in their syllabus. A node of the linked list holds a value (e.g. an integer) and a pointer to the next node in the list. That is the main idea.

Linked list is a building block that can be used to implement stacks, queues, hash table, trees and even adjacency lists of graphs. These data structures are variations of nodes pointing at other nodes. Thus understanding the linked list is crucial for further understanding of other data structures.

C is a low-level language, that may refered by some to be a dinosaur, prehistoric language. It is powerful and allow programmers to deal directly with memory management. It forces pointer allocation, deallocation and lifetime management to be done by us programmer and any mistakes in doing so can be catastrophe. A mistake may produce segfault or even worse, silent memory corruption that can be used as security exploit in the worse case. With great power comes great responsibility, and possibility of bugs. The ability to write good C program can be beneficial to writing higher-level programming languages.

Why reinvent the wheel? There is probably tonnes of library on linked list somewhere on Github and even apply in multiple languages. However, learning to implementing linked list from scratch gives us much insight into the language features of C, the algorithm to implement data structures and complexity analysis of those algoritm.

For this first part, we will keep everything on the stack and minimal: just create a linked list.

Linked list is what?#

A list is a collections of nodes and each node holds a value and a pointer to the next node. The last node can point to NULL to indicates that it does not have any successing node, making it the ending/last node of the list.

We can define a node of linked list using typedef and struct as follows:

// Struct with tag and typedef to alias to IntNode_t type
typedef struct IntNode {
    int val;
    struct IntNode *next;
} IntNode_t;

typedef keywords is to alias struct to a typename, for convenient#

typedef is used to alias the struct with nametag with a declared type name, therefore saving clutters and improve readability. An example of using typedef can help to keep code clean is shown below:

Without typedef we need to repeat struct Point at a lot of places:

struct Point {
    double x;
    double y;
};

struct Point origin = {0.0, 0.0};

struct Point *make_points(size_t n) {
    return malloc(n * sizeof(struct Point));
}

void sort_points(struct Point *pts, size_t n,
                 int (*cmp)(const struct Point *, const struct Point *));

But if we aliased that struct to say Point_t, we can use Point_t as an alias and cut down the need to type struct everytime:

typedef struct Point {
    double x;
    double y;
} Point_t;

Point_t origin = {0.0, 0.0};

Point_t *make_points(size_t n) {
    return malloc(n * sizeof(Point_t));
}

void sort_points(Point_t *pts, size_t n,
                 int (*cmp)(const Point_t *, const Point_t *));

struct with IntNode tag is still needed in the struct body due to self-referencing#

The IntNode after struct inside the body of node structure is a tag. It is important because the struct is self-referencing (node stores a pointer to another node). The typedef name IntNode_t does not exist until the whole declaration of node finishes, so the following will fail:

typedef struct {
    int val;
    IntNode_t *next;   // error: unknown type name 'IntNode_t'
} IntNode_t;

At the point the compiler reads IntNode_t *next;, the typedef has not been introduced yet. THus the compiler does not have any identifier name IntNode_t and will protest it.

In contrast, tag like struct IntNode can be used for self-referencing as tags are usable as soon as they appear. Once the compiler reads struct IntNode {, the name struct IntNode is an incomplete type in scope, and a pointer to an incomplete type is legal — a pointer is one machine word regardless of what it points at. The type only needs to be complete when you dereference it or take its size, which happens later, after the closing brace.

Therefore, for within the node struct definition, we shall use the tagged struct IntNode identifier to define a pointer to next node, but outside this struct, we can totally refer to a node of linkedlist using the aliased type.

Note: typedef also can works with anonymous, no tag struct like follow. However as we are doing self-referencing to the same node, it is beneficial to include a tag. This is important for self-referencing structure.

Is typedef that convienient and always recommended?#

It is not universally considered superior. The Linux kernel style guide discourages typedef'd structs because IntNode_t x; hides the fact that x is a struct, while struct IntNode x; states it. Both conventions are common. Pick one and stay consistent. One note on naming: names ending in _t are reserved by POSIX. IntNode or IntNodeT avoids a collision. This post keeps IntNode_t for readability.

Now let's initialize a list...#

By convention, we can use a head pointer to the first node of list to represent a list; every other nodes are accessed via the predecessor's next pointer. The last node in the list will point to NULL instead of another node. Let's create 3 nodes on the stacks using IntNode_t as typedef alias is now known by compiler.

#include <stdio.h>

void print_list(IntNode_t *head_ptr) {
    IntNode_t *curr_ptr = head_ptr;
    printf("List Nodes:");
    while (curr_ptr != NULL) {
        printf(" %d", curr_ptr->val);
        curr_ptr = curr_ptr->next;
    }
    printf("\n");
}

int main(void) {
    IntNode_t node  = {5, NULL};
    IntNode_t node2 = {10, NULL};
    IntNode_t node3 = {15, NULL};

    node.next  = &node2;
    node2.next = &node3;

    print_list(&node);
    return 0;
}

These three nodes are stack-allocated locals in main. Linking them is just storing each one's address in the previous node's next field. print_list walks the chain until curr_ptr is NULL. print_list copies head_ptr into curr_ptr before walking. Not strictly necessary — head_ptr is already a local copy of the caller's pointer — but it keeps the parameter meaningful for the whole function.

Output

List Nodes: 5 10 15

What's next?#

We have implemented a naive version of a linked list's node and allocate some of them on the stack and linked them together to form a linked list. We will explore some operations on linked list in the next blog.