When you need a collection or container with more flexibility than an Array provides, but also need to be memory efficient, then Linked Lists . Linked Lists are part of the STL in C++ as std::list<T>, where T stands for the type you want the collection to be of.
Because we don’t have this luxury in C I will show you today how we can implement our own List type written purely in C. We will rely on some concepts from my article on how to implement Classes in C, so read it first if you are interested.
If you need an overview of different containers and their advantages and disadvantages you can find them in my article here.
In this Article...
How a Linked List works
A Linked List is a list that does not have fixed or reserved space in memory. It is a loose collection of elements which are pointing to each other. An element contains of the data (i.e. a number) and a pointer to the next element in the list. If there is no other element, this pointer points to NULL.
Also keep in mind that the elements can be stores anywhere in the Heap memory and are seldom adjacent.
This is an empty list which only consists of a header which points to NULL. No elements are present and thus no data is stored.
The simplest form of a list with data. It contains exactly one element and this element points to NULL which identifies it as the last element of the list.
Last but not least we see a list with multiple element, each one pointing to the next until the last element which again points to NULL.
A Note on Double Linked Lists
You can expand the concept of a linked lists with so called Double Linked Lists. You will need some more memory per element but then have the flexibility to go back to the previous element. A Double Linked List saves the pointer to the next element but also another pointer to the previous element.
Goals of the Linked List Implementation in C
We will implement a Linked List Class in C that is capable of the following features:
- Initializing a Linked List (and clean up!)
- Adding Elements to the Linked List
- Accessing Elements
- Removing Elements from the Linked List
We will only implement a Linked List for the Integer (int) type. The C language is missing the <template> stuff that C++ provides so you have to make an implementation for every type that you need. (You maybe could use void-Pointers but that is a rabbit whole of it’s own…)
Linked List Initialization in C
We will need three files for our implementation:
- linked_list.h – here we define the Interface for our Linked List
- linked_list.c – the actual Linked List implementation
- main.c – here we write a little program to test our Linked List
The list_t struct contains two members. The first one, called first_element, will point to the first element of the list. It is initialized with NULL as there are no elements on creation. The second one keeps track of the current size of the array (and is therefore initialized with 0).
There is another struct called list_element_t. It is only visible in this implementation file (a.k.a. private) as nobody outside of our class must now about it. It contains the element data (in our case an int) and the pointer to the next element.
Our interface declares the struct for our linked list objects as well as the initialization, construction and destruction functions. Note that the struct is only declared here but not defined. This keeps the members private. The downside to this is that you have to allocate memory with the list_new() function in order to use it (and remember to use list_dtr() in order to free the allocated memory).
#pragma once
typedef struct list_t list_t;
list_t* list_new();
void list_ctr(list_t* obj);
void list_dtr(list_t* obj);The implementation of memory allocation and class initialization is exactly as I described it in my article about classes in C. The list_new() and list_ctr() may look like you expected them, but the destructor does not.
In the destructor we have to iterate through each list element and free it. This may inflate the destructor a bit but is mandatory to keep the memory clean.
#include "linked_list.h"
#include <stdlib.h>
typedef struct list_element_t {
int element;
struct list_element_t* next;
} list_element_t;
typedef struct list_t {
list_element_t* first_element;
int size;
} list_t;
list_t* list_new()
{
return (list_t*) malloc(sizeof(list_t));
}
void list_ctr(list_t* obj)
{
obj->first_element = NULL;
obj->size = 0;
}
void list_dtr(list_t* obj)
{
if(obj==NULL || obj->first_element==NULL) {
return;
}
list_element_t* iterator = obj->first_element;
list_element_t* old_element = NULL;
while(iterator->next != NULL) {
old_element = iterator;
iterator = iterator->next;
free(old_element);
}
}Our test program is not very fancy so far as it only creates, allocates and destroys our linked list:
#include "linked_list.h"
#include <stdio.h>
int main(int arg, char** argv)
{
list_t* my_list = list_new();
list_ctr(my_list);
list_dtr(my_list);
return 0;
}Adding an Element to a Linked List in C
We use the Linked List class from the C++ STL as a model. Therefore, the function for adding an element will also be called push_back. A similar function is called push_front and does exactly what you might guess, it adds the element in front instead of the back of the list. We also want to keep track of the current size of our List. Therefore, the Interface is defined as follows:
...
int list_size(list_t* obj);
void list_push_back(list_t* obj, const int element);
void list_push_front(list_t* obj, const int element);
...The size function is simply a Getter of the private variables of our object:
...
int list_size(list_t* obj)
{
return obj->size;
}
...Before we implement our adding functions we write a little helper that creates a new list_element_t* for use because we will need the same behaviour for both adding functions. We allocate memory for the new list element, set the element value to the given new value and initialize the pointer to the next element with NULL.
...
static list_element_t* get_new_list_element(const int element)
{
list_element_t* new_element = malloc(sizeof(list_element_t));
new_element->element = element;
new_element->next = NULL;
return new_element;
}
...The push_back() function adds an element to the end of our linked list. We start by calling our helper function to get a new list element.
We then check if the list is empty – if so we simply put the new element as our first element. Otherwise we have to iterate to the current end of the list end replace the NULL pointer to the next element with a pointer to our new element. Because we initialized the next-Pointer of the new element with NULL it is already the new last element of the list.
We also have to increase the size of the list by incrementing the size variable.
...
void list_push_back(list_t* obj, const int element)
{
list_element_t* new_element = get_new_list_element(element);
if(obj->first_element ==NULL) {
obj->first_element = new_element;
} else {
list_element_t* iterator = obj->first_element;
while(iterator->next != NULL) {
iterator = iterator->next;
}
iterator->next = new_element;
}
obj->size++;
}
...The push_front() function adds the new element at the beginning of the list. We again use the helper function from above. If there is already a first element of the list we point to this element with our new element.
In any case we will make the new element the first element of the list, and we also increase the size.
...
void list_push_front(list_t* obj, const int element)
{
list_element_t* new_element = get_new_list_element(element);
if(obj->first_element != NULL) {
new_element->next = obj->first_element;
}
obj->first_element = new_element;
obj->size++;
}
...Now we can use these functions to add new elements to our list in our little test program in main:
#include "linked_list.h"
#include <stdio.h>
int main(int arg, char** argv)
{
list_t* my_list = list_new();
list_ctr(my_list);
printf("Linked List Size: %d\n", list_size(my_list));
list_push_back(my_list, 42);
printf("Linked List Size: %d\n", list_size(my_list));
list_push_front(my_list, 55);
printf("Linked List Size: %d\n", list_size(my_list));
list_push_back(my_list, 11);
list_push_back(my_list, 12);
list_push_back(my_list, 13);
printf("Linked List Size: %d\n", list_size(my_list));
list_dtr(my_list);
return 0;
}This program will produce the following output:
Linked List Size: 0
Linked List Size: 1
Linked List Size: 2
Linked List Size: 5Accessing Linked List Elements in C
We will implement two different ways to access elements of the linked list. First we use fixed access with front() and back() and then we implement more dynamic access of a given index with the at() function.
Accessing Linked List Elements with front() and back()
We add the both declarations of front(…) and back(…) in our header. They both return an int because our list contains values of type int.
...
int list_front(list_t* obj);
int list_back(list_t* obj);
...Let’s start with the front(…) because it is as simple as it gets. In order to prevent undefined behaviour we return 0 if the list is empty. Otherwise we return the element value of the first list element.
...
int list_front(list_t* obj)
{
if(obj->first_element == NULL) {
return 0;
}
return obj->first_element->element;
}
...In the back() function we also check for an empty list and return 0 as a fallback value. Then we iterate through the whole list until there are no elements left and simply return the last element we found. This is of course a very simplistic approach and it is definitly not the most performant.
...
int list_back(list_t* obj)
{
if(obj->first_element==NULL) {
return 0;
}
list_element_t* iterator = obj->first_element;
while(iterator->next != NULL) {
iterator = iterator->next;
}
return iterator->element;
}
...We again test the new functions in our test program. We use the push_back(…) function from above to insert some elements and then print the first and the last element to the console.
#include "linked_list.h"
#include <stdio.h>
int main(int arg, char** argv)
{
list_t* my_list = list_new();
list_ctr(my_list);
list_push_back(my_list, 42);
list_push_back(my_list, 11);
list_push_back(my_list, 12);
list_push_back(my_list, 13);
printf("Linked List Size: %d\n", list_size(my_list));
printf("First Element: %d\n", list_front(my_list));
printf("Last Element: %d\n", list_back(my_list));
list_dtr(my_list);
return 0;
}This leads to the following output:
Linked List Size: 4
Linked List Front Eement: 42
Linked List Back Element: 13Accessing Linked List Elements with at()
Next we implement the possibility to access an element by its index with the at(…) function.
We pass the index of the element that we want to access. The return type is int because we have a vector of type int and the function returns a single element. Our protection against an invalid index is again return a 0 value.
...
int list_at(list_t* obj, const int index);
...Similar to the back(…) function we loop through the list, but this time we also end the loop if our index parameter is reached before the end of the list. By doing this we return the value at the given index.
...
int list_at(list_t* obj, const int index)
{
list_element_t* iterator = obj->first_element;
int i=0;
while(i<index && iterator!=NULL) {
iterator = iterator->next;
i++;
}
int element = (iterator!=NULL) ? iterator->element : 0;
return element;
}
...We modify our last test program a little bit and test the output of a valid as well as the output of an invalid index passed to the at(..) function:
...
list_t* my_list = list_new();
list_ctr(my_list);
list_push_back(my_list, 42);
list_push_back(my_list, 11);
list_push_back(my_list, 12);
list_push_back(my_list, 13);
printf("Linked List Size: %d\n", list_size(my_list));
printf("Second Element: %d\n", list_at(my_list, 1));
printf("First Element: %d\n", list_front(my_list));
printf("Last Element: %d\n", list_back(my_list));
printf("Invalid Element (index 7): %d\n", list_at(my_list, 7));
list_dtr(my_list);
...The output of this test program is as follows:
First Element: 42
Second Element: 11
Last Element: 13
Inavlid Element (index 7): 0Removing Linked List Elements in C
Last but not least we will cover removing elements from the linked list. If you remove an element from a linked list, its size will also shrink and the memory is free to be used otherwise.
There are two possibilities to do this. First we can pop_back() which means that the last element will be removed, or we can erase(..) elements from the array. With the latter function we can delete either one element or a range of elements between two given iterators.
Removing Elements with pop_back()
Our header declaration for the pop_back(…) function is just plain simple:
...
void list_pop_back(list_t* obj);
...After the NULL-Element guard we setup a loop which will iterate through the linked list. On each iteration we save the current element as it could be the last one. When we reach the end of the list we know that this is the last element. Then it is just simply freeing the memory for this element and decrementing the size counter.
Again, this is a plain simple approach, feel free to find a more performant solution.
...
void list_pop_back(list_t* obj)
{
if(obj->first_element==NULL) {
return;
}
list_element_t* iterator = obj->first_element;
list_element_t* previous = iterator;
while(iterator->next != NULL) {
previous = iterator;
iterator = iterator->next;
}
previous->next = NULL;
free(iterator);
obj->size--;
}
...Once more we use our example and modify it to show how the new implemented remove functions work:
#include "linked_list.h"
#include <stdio.h>
int main(int arg, char** argv)
{
list_t* my_list = list_new();
list_ctr(my_list);
list_push_back(my_list, 11);
list_push_back(my_list, 12);
list_push_back(my_list, 13);
printf("Linked List Size: %d\n", list_size(my_list));
printf("Last Element: %d\n", list_back(my_list));
list_pop_back(my_list);
printf("Linked List Size: %d\n", list_size(my_list));
printf("Last Element: %d\n", list_back(my_list));
list_dtr(my_list);
return 0;
}Finally we have this output:
Linked List Size: 3
Last Element: 13
Linked List Size: 2
Last Element: 12Removing Elements with erase()
The function erase(…) gives us the possibility to remove n adjacent elements at any position within the linked list:
...
void list_erase(list_t* obj, int first_index, int last_index);
...The advantage of the erase function over pop_back(…) is that we can choose which elements we want to remove from the list. The guard clause checks for an empty list, whether the indexes are valid in relation to each other and if the requested indexes are in object range.
We look for the first index where the element should be deleted and also remember the element after this one (if there is any). Then we delete the element and decrement the size of the list.
Now there are several options: If the list is empty now we return because there is nothing more to do. If there are elements left and we deleted the first one we now have to set a new beginning of the list.
In any other case we search the element which now has a “missing link” to the next and set this link with our remembered element.
If we want to delete more that one element we make a recursive call to list_erase(…).
...
void list_erase(list_t* obj, int first_index, int last_index)
{
if(obj->first_element==NULL || last_index < first_index || first_index > obj->size || last_index >= obj->size) {
return;
}
list_element_t* elementToDelete = obj->first_element;
list_element_t* replaceElement = obj->first_element->next;
for(int i=0;i<first_index;i++) {
elementToDelete = elementToDelete->next;
replaceElement = replaceElement->next;
}
free(elementToDelete);
obj->size--;
if(obj->size == 0) {
return;
}
if(0==first_index) {
obj->first_element = replaceElement;
} else {
list_element_t* element = obj->first_element;
for(int i=1;i<first_index;i++) {
element = element->next;
}
element->next = replaceElement;
}
if(first_index<last_index) {
list_erase(obj, first_index, --last_index);
}
}
...The test program for this isn’t complex, we just add a bunch of elements to the list and then remove some. We also erase more then one element at once in the last call of list_erase(…):
#include "linked_list.h"
#include <stdio.h>
int main(int arg, char** argv)
{
list_t* my_list = list_new();
list_ctr(my_list);
printf("0 Linked List Size: %d\n", list_size(my_list));
list_push_back(my_list, 1);
list_push_back(my_list, 2);
printf("1 Linked List Size: %d\n", list_size(my_list));
printf("First Element: %d\n", list_at(my_list, 0));
list_erase(my_list, 0, 0);
printf("2 Linked List Size: %d\n", list_size(my_list));
printf("First Element: %d\n", list_at(my_list, 0));
list_push_front(my_list, 1);
list_erase(my_list, 1, 1);
printf("3 Linked List Size: %d\n", list_size(my_list));
printf("First Element: %d\n", list_at(my_list, 0));
list_push_back(my_list, 2);
list_push_back(my_list, 3);
list_erase(my_list, 2, 2);
printf("4 Linked List Size: %d\n", list_size(my_list));
printf("First Element: %d\n", list_at(my_list, 0));
printf("Second Element: %d\n", list_at(my_list, 1));
list_push_back(my_list, 3);
list_push_back(my_list, 4);
printf("Third Element: %d\n", list_at(my_list, 2));
printf("Fourth Element: %d\n", list_at(my_list, 3));
list_erase(my_list, 1, 2);
printf("5 Linked List Size: %d\n", list_size(my_list));
printf("First Element: %d\n", list_at(my_list, 0));
printf("Second Element: %d\n", list_at(my_list, 1));
list_dtr(my_list);
return 0;
}The final output is as follows:
0 Linked List Size: 0
1 Linked List Size: 2
First Element: 1
2 Linked List Size: 1
First Element: 2
3 Linked List Size: 1
First Element: 1
4 Linked List Size: 2
First Element: 1
Second Element: 2
Third Element: 3
Fourth Element: 4
5 Linked List Size: 2
First Element: 1
Second Element: 4Summary & Further Ideas
This is a simple implementation of a Linked List Class in pure C. Feel free to optimize the functions and try to use them in your own programs.
If you already read the Article on Vectors in C you may miss the Iterator function begin() and end(). You may use this hint as a “ToDo” for yourself – implement Iterators for the Linked List in C.
This article was first published by Marco Lieblang on moderncprogramming.com. If you are reading this somewhere else, it may be plagiarism.
