In this article I’ll explain a new data structure, the list.

When I refer to a list here I mean a linked list (and it’s variants). But what is a linked list?

You can think of it as a chain. On each link of the chain there will be data and the link that follows it.

How does this idea transfers in the code?

struct list{
    void *data;
    struct list *next;
};

If you think about it you just have to store the first element of the list. The next elements can be accessed throught the “next” element.

Now you might be wondeting what’s the interest of this data structure?

First it will prove very useful in the future with other data structure.

Second, it is interesting because each link is separated in the memory. Thus an element doen’t use one large block of memory. It rather uses small blocks at different places of the memory. The downside of that is that you use a bit more memory because of the next pointer.

If we do it this way, everytime we add an element at the beginning, the first element (the only one we store) will change. This means we should or use a double pointer, or return the new element.

Or we could cheat. The “cheat” is using a thing called a sentinel. The sentinel is an element without data that comes before the rest just to avoid the issue of moving the start.

Now that we have the how set, let’s talk about what. What methods do we need?

Well of course we want to create and delete the structure, we want to add and delete elements. We might also want to insert and delete at a certain place too. Then we can add some fancy stuff like spliting the list in half. Or we could return just the first element. Or we could reverse the list.

We’ll talk about how to implement them on the next post. In the future we will also see some different kind of linked lists.