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:
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.
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:
Here we malloc a new node, and then point the previous node to this new node:
Oops, how do we now reattach the rest of the list? It’s there in memory, but good luck finding it.
It’s essential to ensure you either link the new node to the old rest of list first, then change the old node:
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:
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