To store data in memory, we've used simple variables (like int, double, etc.), arrays, and custom structures. If you want to store a series of values, the easiest way is usually to use arrays.

However, arrays can be quite limited. For example, if you create an array with 10 slots and later realize your program needs more space, you won't be able to expand that array. Similarly, you can't insert a new item right in the middle of it.

Linked lists are a much more flexible way to organize data in memory. Since the C language doesn't provide this kind of storage system by default, we'll build it from scratch ourselves. It's a fantastic exercise that will really help you get more comfortable with C.

Representing a Linked List

So, what exactly is a linked list? Let's begin with something we already know — arrays. You can picture an array in memory like this: here's one containing five integers.

[ ] [ ] [ ] [ ] [ ]

I've shown the array horizontally, but it could just as well be drawn vertically — doesn't really matter.

As I mentioned earlier, arrays are fixed in size. You can't grow them unless you create a new, larger one (see the diagram below). And inserting a new slot in the middle? Also a no-go unless you shift everything over.

[ ] [ ] [ ] [ ] [ ] <- no way to add a sixth slot

C doesn't offer another built-in way to store data, but that doesn't mean we can't create one ourselves. We just need to know how to go about it — and that's exactly what this chapter (and the next few) will help you figure out.

A linked list is a way of organizing a sequence of data in memory. The idea is to chain together a series of structures by connecting them with pointers. You could picture it like this:

[ ] -> [ ] -> [ ] -> [ ] -> [ ]

Each element can contain whatever you want: one or more int, double, etc. In addition to the data, each element includes a pointer to the next one in the list.

I'll admit, it all sounds very theoretical so far — and probably a bit hazy. But for now, just focus on how the elements are connected: they form a chain of pointers. That's where the name "linked list" comes from.

Unlike arrays, the elements in a linked list aren't side-by-side in memory. Each node points to another one that might be located anywhere in memory, not necessarily nearby. That's where all the flexibility comes from.

Building a Linked List

Time to get practical. Let's try creating a structure based on this concept.

Let me remind you — everything we're about to do uses C techniques you already know. Nothing new here. We're just going to design our own structures and functions, and tie them all together into a logical, self-managing system.

For our examples, we'll create a linked list of integers. Each element in the list will be based on the following structure:

typedef struct Element Element;
struct Element
{
    int number;
    Element *next;
};

We could just as easily make a linked list that holds decimal numbers, arrays, or even other structures. The linked list concept works with any type of data. But for now, let's keep it simple so you can really grasp how it all works.

So, what's in this structure?

• 1. A piece of data — here, it's an int, but we could swap that for anything: a double, an array, whatever. This is the value you want to store, and you'll adapt it depending on your program's needs.
• If you want to make it more generic, you could use a void* pointer. That way, you could point to any type of data.
• 2. A pointer to another element of the same type, called next. This is what links the elements together. Each element "knows" where the next one is in memory. Like I mentioned earlier, these nodes aren't sitting side-by-side in memory. That's the big difference from arrays. It also means we can more easily add new nodes later if we need to.
• On the other hand, it doesn't know where the previous element is. So once you move forward, you can't go back. This is what we call a singly linked list. In contrast, doubly linked lists have pointers in both directions and don't have this limitation — but they're more complex.

The Control Structure

In addition to the structure we just created (which we'll duplicate for each element), we'll need another structure to manage the whole linked list. It'll look like this:

typedef struct List List;
struct List
{
    Element *head;
};

This List structure holds a pointer to the first element in the list. We need to keep track of where the list begins. If we know the first element, we can find all the others by "hopping" from one to the next using the next pointers.

A structure with only one field usually isn't very useful. But I think we'll probably want to add more fields later — so let's plan ahead and create this structure now. For instance, we could later include the size of the list (i.e., how many elements it holds).

We'll only need one instance of the List structure. It lets us manage the entire list (represented by an "X" in the diagram below):

[ X ] -> [ ] -> [ ] -> [ ] -> [ ]

The Last Element in the List

We're almost done with our diagram. There's one last detail: how do we mark the end of the list? At some point, we have to stop traversing it.

We could add a pointer to the last element inside the List structure. But there's an easier way: just have the last element's next pointer point to NULL. In other words, set it to NULL to signal the end of the list.

That gives us a complete diagram of our linked list structure:

[ X ] -> [ ] -> [ ] -> [ ] -> [ ] -> NULL

Simple, but effective.

List Management Functions

We've created two structures that allow us to manage a linked list:

• Element, which represents a single item in the list and can be duplicated as many times as needed;
• List, which controls the entire list. We'll only need one instance of this.

That's great, but we're still missing the most important part: the functions that will actually manipulate our linked list. Obviously, we're not going to modify the structures by hand every time we need something! It's much cleaner and safer to use functions that automate all that work. But first, we have to write them.

At first glance, I'd say we'll need functions to:

• initialize the list;
• add an element;
• remove an element;
• display the list's contents;
• delete the entire list.

We could come up with other functions (like calculating the list's size), but those are less essential. For now, we'll focus on the ones I just mentioned. That'll already give us a solid foundation. Once you're comfortable with the concept, I'll encourage you to write more as practice.

Initializing the List

The initialization function is the first one we'll need to call. It creates the control structure and the first element of the list.

Here's the function I suggest. We'll walk through it together afterward, of course:

List *initialize()
{
    List *list = malloc(sizeof(*list));
    Element *element = malloc(sizeof(*element));
 
    if (list == NULL || element == NULL)
    {
        exit(EXIT_FAILURE);
    }
 
    element->integer = 0;
    element->next = NULL;
    List->head = element;
 
    return list;
}

We start by creating the control structure List.

Notice that the type is List (with a capital L) and the variable is list. The capitalization helps distinguish them.

We allocate memory for the control structure using malloc. The size to allocate is calculated automatically with sizeof(*list). That way, the computer knows it should allocate enough memory to hold a List structure.

Then we do the same for the first element. After that, we check that both memory allocations worked. If either failed, we immediately exit the program with exit().

If everything goes well, we initialize our first element:

• the data field integer is set to 0 by default;
• the pointer next is set to NULL because for now, our first element is also the last one. As we saw earlier, the last item in a list should always point to NULL to mark the end.

We've now successfully created in memory a linked list with a single element, shaped something like this:

[ X ] -> NULL

Adding an Element

Now things get a little trickier.

The answer is: it's up to us. We're free to decide. For this chapter, let's look at how to add an element at the beginning of the list. It's easier to understand, and later on I'll suggest an exercise to help you add elements in more specific positions.

We need to write a function that can insert a new item at the start of the list. Let's imagine we have a list with three elements, and we want to add a new one at the beginning. We want to insert our new element at the start of the list.

To do this, we'll need to adjust both the list's head pointer and the next pointer of our new element to link it in properly. Here's the source code I suggest — we'll analyze it just after:

void insert(List *list, int newInteger)
{
    /* Create the new element */
    Element *newElement = malloc(sizeof(*newElement));
    if (list == NULL || newElement == NULL)
    {
        exit(EXIT_FAILURE);
    }
    newElement->integer = newInteger;
 
    /* Insert the element at the beginning of the list */
    newElement->next = list->head;
    list->head = newElement;
}

The insert() function takes the control structure List (which contains the address of the first element) and the number to store in the new element.

First, we allocate memory for the new element and assign it the value newInteger. Then comes the critical part: inserting it into the list.

Since we chose to insert at the beginning, we need to carefully update the pointers in this specific order:

• Point our new element to what will be its successor — currently the first element of the list;
• Point the head pointer to our new element.

This lets us correctly insert the new element into the list, like shown below:

[ ] [ X ] -> [ ] -> [ ] -> [ ] -> [ ] -> NULL

We then reset the "head" to be at the start of the list, and link them together:

[ X ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> NULL

Removing an Element

Just like with insertion, we're going to focus on removing the first element in the list. Technically, you can remove a specific element from the middle, and that'll be one of the exercises I give you later.

Removing an element is straightforward, but you must update the list's pointers in the right order to avoid losing any information.

void remove(List *list)
{
    if (list == NULL)
    {
        exit(EXIT_FAILURE);
    }
 
    if (list->head != NULL)
    {
        Element *toDelete = list->head;
        list->head = list->head->next;
        free(toDelete);
    }
}

We first check that the List pointer isn't NULL, or we can't do anything. Then we check whether there's at least one element in the list — otherwise, there's nothing to delete.

Once we've done those checks, we store the address of the element to be removed in a pointer called toDelete. We then update the head pointer to point to the new first element (currently the second in the list).

Finally, we free the memory occupied by the old first element using free.

This function is short, but could you rewrite it on your own? Remember, you must follow the correct order:

• Make head point to the second element;
• Free the first one.

If you do it in reverse, you'll lose the address of the second element!

Displaying the Linked List

To visualize the content of our list, a display function is ideal! Just start from the first element and print each one in turn, "jumping" from node to node.

void showList(List *list)
{
    if (list == NULL)
    {
        exit(EXIT_FAILURE);
    }
 
    Element *current = list->head;
 
    while (current != NULL)
    {
        printf("%d -> ", current->integer);
        current = current->next;
    }
    printf("NULL\n");
}

This function is simple: we start at the first element and print out each value (an integer). We use the next pointer to move from one element to the next.

We can now test creating and displaying our linked list using a main():

int main()
{
    List *myList = initialize();
 
    insert(myList, 5);
    insert(myList, 8);
    insert(myList, 15);
    remove(myList);
 
    showList(myList);
 
    return 0;
}

In addition to the first element (which we've left at 0), we add three new values to the list. Then we remove one. The final contents of the list will be:

8 -> 5 -> 0 -> NULL

Going Further with Linked Lists

We've now covered the main functions you need to manage a linked list: initialization, adding an item, removing one, etc. But there are a few more that are missing, and I encourage you to try writing them yourself — they make for excellent practice!

• Insert an element in the middle of the list: Right now, we can only add at the beginning, which is usually enough. But if you want to insert in the middle, you'll need a function that takes one extra parameter: the address of the item that should precede the new one. Your function will traverse the list until it finds that item, and then insert the new one right after it.
• Remove an element from the middle: Same idea as inserting in the middle. This time, the parameter should be the address of the item you want to delete.
• Destroy the entire list: Just remove all elements one by one!
• List size: This function tells you how many elements your list contains. Ideally, instead of recalculating it every time, you'd store an integer like nElements in the List structure. Then you just increment it when adding elements and decrement it when removing them.

I recommend grouping all your linked list management functions into two files: Linked_List.c and Linked_List.h. Congratulations, this will be your very first library! You'll be able to reuse it in any program that needs linked lists.

In Summary

• Linked lists offer a flexible way to store data in memory. Unlike arrays, they let you add or remove "slots" at any time.
• The C language doesn't have built-in support for linked lists — you have to build them yourself! But that's a great way to level up your algorithm and programming skills.
• In a linked list, each element is a structure that contains the address of the next one.
• It's best to create a control structure (like List) to keep track of the first element's address.
• There's an upgraded version — more powerful but also more complex — called doubly linked lists, where each element also stores the address of the previous one.

Another important, and adjacent, concept is the notion of pile and file, as well as the distinction between FIFO (First In First Out), and LIFO (Last In First Out). They can make list handling much more efficient.

Enjoyed this C / C++ course?

If you liked this lesson, you can find the book "Learn C Programing for Beginners" from the same authors, available on SiteRaw, in bookstores and in online libraries in either digital or paperback format. You will find a complete C / C++ workshop with many exclusive bonus chapters.

More information