Linked lists

Python has a rather handy list method. It allows you to add and remove items at will. How it actually does this is rather elaborate and you can read all about it over here.

C doesn’t give you the same flexibility. When you create an array, it is of X size. That size cannot change as there is no guarantee that memory on either side of the existing array space is even free for you. For this reason there is a handy data structure called the linked list.

Linked List

A linked list is essentially a struct node with a list item, and then a pointer to the next node. If you need to add an item to a list, you simply create another node in memory. As each item is created, it doesn’t matter where in memory it’s created, as the previous item has a pointer to the new node. A picture really helps here:
linked1
As we shall see, adding, inserting, and removing items are all very easy to do with linked lists. It’s not all roses though. Linked lists use more memory than an array of similar items. Each node has a pointer to the next item which takes up memory. The bigger issue is random access.

Let’s say we initialise an array with 1000 items. If I wanted to get to item 500, the computer would simply look at the address of item 0, work out the start address plus 500 of item size, and read that location.
linked2

You can’t do this with a linked list. Each node is in a separate location. They could be lined up next to each other, but they can just as easily be all over the place. The only way to get to item 500 in a linked list, is to start at node 0, read the pointer to the next node, then keep doing that until you reach node 500.

How do you know when you reach the end of the linked list? You could probably use any kind of escape character, but NULL tends to get used.

Basic implementation

So how do we create a linked list? Here I’ll create a struct called node that will hold an integer. The struct will also hold a pointer to the next node.

#include <stdio.h>

// Struct node with pointer to struct node
typedef struct node {
    int number;
    struct node* next;
}node;

int main(void) {

    // Create four nodes
    node node1;
    node node2;
    node node3;
    node node4;
    
    // Place numbers inside the four nodes we made
    node1.number = 10;
    node2.number = 20;
    node3.number = 30;
    node4.number = 40;
    
    // Each node will point to the next node
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = NULL;
}

Here I have created four nodes. Each points to the next node, except for node 4. It has it’s next pointer assigned to NULL. If you fail to assign this NULL value, the pointer will have whatever value what in that memory location when you create it. That is going to point to some random value which is bad news. In order to traverse the list, we need a pointer to the root, or currently node1’s address. This is a pointer that should never change unless node1 is deleted or a node is inserted before it. We also need a cursor that will be updated with the current node’s address. I’ll create a function that prints out items in the list. The following is added to main()

    // Never lose the root position, otherwise you
    // lose access to your list!
    node* root = &node1;
    
    // Use cur as a cursor to move around
    node* cur;
    cur = root;

    // Print current list
    printList(cur); 

And the printList function is as so:

void printList(struct node* cur) {
    // Traverse through our linked list
    int i = 0;
    while (cur != NULL) {
        printf("Item %i is %i\n", i, cur->number);
        i++;
        
        // Move cursor to next node via pointer
        cur = cur->next;
    }
}

Running the program gives the following:

$ ./list 
Item 0 is 10
Item 1 is 20
Item 2 is 30
Item 3 is 40

Let’s change the print statement now to print out the memory locations of each of these items. Printing the value of node->next should give is the address of the next node. Let’s change the printList function like so:

void printList(struct node* cur) {
    // Traverse through our linked list
    while (cur != NULL) {
        printf("%i is is at position %p\n", cur->number, &cur->number);
        printf("Next node is at position %p\n\n", cur->next);
        
        // Move cursor to next node via pointer
        cur = cur->next;
    }
}

Printing this out gives us the following:

$ ./list 
10 is is at position 0xbff38e68
Next node is at position 0xbff38e60

20 is is at position 0xbff38e60
Next node is at position 0xbff38e58

30 is is at position 0xbff38e58
Next node is at position 0xbff38e50

40 is is at position 0xbff38e50
Next node is at position (nil)

Notice the memory address of each next value is the same as the address of the next value printed. Exactly what we would expect. Also notice that node4’s next value is NULL. I’ve used this very fact in the while loop to know when the list has ended and exit the loop.

Adding to the list

The previous program had me hard code four node values into the program. Let’s change this now so that the program will prompt to add values, and then print them out when needed:

#include <stdio.h>
#include <stdlib.h>

// Struct node with pointer to struct node
typedef struct node {
    int number;
    struct node* next;
}node;

void printList(node* cur) {

    // Traverse through our linked list
    while (cur != NULL) {
        printf("%i is is at position %p\n", cur->number, &cur->number);
        printf("Next node is at position %p\n\n", cur->next);
        
        // Move cursor to next node via pointer
        cur = cur->next;
    }
}

void addNode(node* cur) {

    // Traverse through our linked list
    // Need to get to end of list in order to append
    if (cur != NULL) {
        while (cur->next != NULL) {
            cur = cur->next;
        }
    }
    
    // Now at the the end of the list, ensure the current last node
    // points to a new node we create dynamically
    cur->next = (node*) malloc(sizeof(node));
    
    // Move to the new node
    cur = cur->next;
    
    // Get a value inside that node
    printf("Please enter node value: ");
    scanf("%i", &cur->number);  
}
        
int main(void) {

    // Create initial node
    node node1;
    
    // Get initial value from user
    printf("Please enter inital node value: ");
    scanf("%i", &node1.number);
    
    // Initial node's next should be end of list
    node1.next = NULL;
    
    // Root position of list
    node* root = &node1;
    
    // Use cur as a cursor to move around
    node* cur;
    
    // User controls what to do next
    int choice;
    do
    {
        printf("1 - Add new item to list\n");
        printf("2 - Print list\n");
        printf("3 - Exit\n# ");
        
        scanf("%i", &choice);
        
        switch (choice) {
            case 3:
                return 0;

            case 2:
                cur = root;
                printList(cur);
                break;
                
            case 1:
                cur = root;
                addNode(cur);
         }
                
    } while (choice != 3);
}

Let’s add a couple of values and then print them out:

: ./list
Please enter inital node value: 100
1 - Add new item to list
2 - Print list
3 - Exit
# 1
Please enter node value: 200
1 - Add new item to list
2 - Print list
3 - Exit
# 2
100 is is at position 0xbf97dc18
Next node is at position 0x875a008

200 is is at position 0x875a008
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Exit
# 1
Please enter node value: 300
1 - Add new item to list
2 - Print list
3 - Exit
# 1
Please enter node value: 400
1 - Add new item to list
2 - Print list
3 - Exit
# 2
100 is is at position 0xbf97dc18
Next node is at position 0x875a008

200 is is at position 0x875a008
Next node is at position 0x875a018

300 is is at position 0x875a018
Next node is at position 0x875a028

400 is is at position 0x875a028
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Exit
# 3

Inserting into the list

Inserting into a list is very simple too, but it comes with one risky part. Order of operations is quite important. If you get to the position where you want to insert, then create a new node, you need to be sure that you don’t lose the address to the original next node. If you do so, you could lose the rest of your list!

Once again, imagery helps to explain this. Here we have three nodes. We now want to add a new node in the position:
linked3
Here we malloc a new node, and then point the previous node to this new node:
linked4
Oops, how do we now reattach the rest of the list? It’s there in memory, but good luck finding it.
linked5
It’s essential to ensure you either link the new node to the old rest of list first, then change the old node:
linked6
linked7
Or simply save the pointer value that the original node was pointing to, and copy that back into our new node’s pointer value.

I’ve chose the latter in the following code. I’ll only post the changed parts. I’ll create a new function that will do the insertion and call it through main():

    do
    {
        printf("1 - Add new item to list\n");
        printf("2 - Print list\n");
        printf("3 - Insert node\n");
        printf("4 - Exit\n# ");
        
        scanf("%i", &choice);
        
        switch (choice) {
            case 4:
                return 0;
                
            case 3:
                cur = root;
                printf("After which value should I insert? ");
                int match;
                scanf("%i", &match);
                insertNode(cur, match);
                break;

            case 2:
                cur = root;
                printList(cur);
                break;
                
            case 1:
                cur = root;
                addNode(cur);
         }
                
    } while (choice != 4);


void insertNode(node* cur, int match) {

    // Traverse through linked list to find value
    while (cur->next != NULL) {
        
        // We've found the node we're looking for
        if (cur->number == match) {
        
            // save pointer to rest of list
            node* temp = cur->next;
            
            // Create a new node and get current node to point to it
            cur->next = (node*) malloc(sizeof(node));
        
            // Move to the new node
            cur = cur->next;
            
            // Get a value to insert
            printf("What value do you want to insert? ");
            int number;
            scanf("%i", &number);
            cur->number = number;
            
            // Finally ensure new node connects to the rest of the list
            cur->next = temp;
            
            return;
        }
        
        // Otherwise keep going through the list
        cur = cur->next;
    }
}

Let’s add some values and then insert one:

$ ./list 
Please enter inital node value: 10
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 1
Please enter node value: 20
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 1
Please enter node value: 30
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 3
After which value should I insert? 20
What value do you want to insert? 25
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 2
10 is is at position 0xbfd42938
Next node is at position 0x831e008

20 is is at position 0x831e008
Next node is at position 0x831e028

25 is is at position 0x831e028
Next node is at position 0x831e018

30 is is at position 0x831e018
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 4

Deleting a node

Deleting is similar to inserting. Instead of getting a new value, we simply look for the node in question and unlink it from the chain. As per the inserting function, we need to take care that we don’t lose the address of the next node in the chain. It’s a little more tricky as well, as when we remove a node, we need to get back to the previous node so we can set it’s pointer to the next node we need:
linked8
Here I’ve deleted the second node. The first node’s pointer now points to a memory location with garbage data. We’ve also lost the address to the rest of the list!

In my function here, I’ll ensure I always keep the pointer address of the previous node. When we find the node we want to remove, we still have the previous pointer value that we can copy where we need it:

void deleteNode(node* cur, int match) {

    // We need to keep note of previous node
    // otherwise we cannot reconnect it!
    node* previous = cur;

    // Traverse through linked list to find value
    while (cur->next != NULL) {
        
        // We've found the node we're looking for
        if (cur->number == match) {
        
            // Set pointer of last node around this node to new node
            node* temp = cur->next;
            cur = previous;
            cur->next = temp;
            
            return;
            
            // Where to release the RAM?
        }
        
        // Otherwise keep going through the list
        previous = cur;
        cur = cur->next;
    }
}
: ./list 
Please enter inital node value: 10
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 1
Please enter node value: 20
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 3
After which value should I insert? 10
What value do you want to insert? 15
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 2
10 is is at position 0xbfa0b0c8
Next node is at position 0x8bda018

15 is is at position 0x8bda018
Next node is at position 0x8bda008

20 is is at position 0x8bda008
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 4
Which value should I delete? 15
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 2
10 is is at position 0xbfa0b0c8
Next node is at position 0x8bda008

20 is is at position 0x8bda008
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
#5

Freeing your nodes

It’s good practice to clean up once you’re done. Just before we exit, I want to ensure that all nodes are removed from memory. As noted in the delete section, we need to ensure that we save the location of the next node. There are a couple of ways to do this. One way is to keep a note of the next node’s address, then delete the current node. then off to the next node and repeat. I’ve done that here:

void deleteList(node* cur) {
    // Traverse through linked list
    while (cur != NULL) {
        node* temp = cur;
        cur = cur->next;
        free (temp);
    }
}

Extras

I’ve not covered all the different ways of manipulating a linked list. What if we want to delete the first or last node for example?
This is a good read if you want to take it further: https://www.cs.bu.edu/teaching/c/linked-list/delete/

You can find my working code for the above right here: https://github.com/mellowdrifter/C-Sandbox/blob/master/linked.c

Author: Darren

Network Architect. Dual CCIE and JNCIE-SP.