Arrays are a great way of storing and structuring your data, whether that is numbers, characters, strings or any other data type. But how practical is it to add one element before the first element of an array?
It’s doable – definitely – but tricky. That is because we’d have to push each element by one and then add that one value we need on array_name[0].
As we can see we’ll have to move each element of the array by one, before we can add one new element in the front. As “easy” as it seems on this example there are a few downsides that come with it:
- More computational costs
- Time complexity will always be high: we’ll have O(n) because we are always traversing through the array [array_length] times: in this example n;
- If the array length would’ve been 4, we’d have to create an entirely new array.
- Another way of solving this would’ve been by using realloc: slows us down and can be problematic if there isn’t enough “space” where we are so it’d completely move the array elsewhere
As we can imagine, this is not much effective. That is where Linked Lists come in the game. Although they might take up way more space than an array does, it’s easier for a programmer to add elements in the first, middle, or even last element of the list. We wouldn’t need to pre-calculate the number of elements it’d have to have, as we could just allocate some more memory each time we need a new element.
Here a visualization of how adding a new element on an array would look like vs on a linked list:
But wait, what’s a node, what’s a pointer-to-the-next one and what’s a head?
Don’t panic! We will go through them one by one:
- Node: linked lists are made of nodes. A node is some sort of structure which will hold a specific value of the current element and a pointer to the next one.
- Head: it’s the first node of a linked list. Generally no other node is pointing to it and it points to another node. (this of course depends if we have a simple linked list or in other cases doubly or circularly linked lists.
- Tail: it’s the last node of a linked list. It’s pointing to NULL, which means no other node comes after that. That’s a crucial piece of information when it comes to traversing through a linked list, because we somehow need to know where the beginning and the end of this linked list are.
Okay Albina, enough with the theory, how do I implement this in my code??
Yes, you probably want to finish the bonus of libft or any other project you’re doing right now. Well, step by step! In my belief it’s very important to have a clear overview of what tools we can work with and what tools we choose to work with.
First of all we need to define this data structure. In the C programming language we do this by declaring a structure which has:
- A value
- A next pointer to another node
In this case we use typedef and in the end we call it t_list so we can easily work with it throughout our code.
Looks complex? – For sure. But let’s make it easier by writing some code and testing with its functionality.
We create a new node named new_node and then allocate memory for this node. Note that we allocate sizeof(t_list).
Then we check if we allocated properly (in this case new_node would exist) and then set the new_node’s value to the val variable.
Since this would be the last node, we set the value of next to NULL.
soooo how do we remove, add to the front, add to the back or find the size of a linked list?
I’d recommend you ask to your left, ask to your right, ask your pc. It’d be great to get into details but that would be the solution of the next few bonus exercises, which we don’t want to do 😉