Linked List

2- After creating our building block, now we are going to start serious things. The linked lists as we know it can be seen as a series of houses, imagine there is 5 houses (it can be more, just to illustrate) that looks the same, and one of your new friends live in one of them, now imagine one more time that this friend is new in the town and he/she don’t know the address of his/her house, BUT he/she will tell you that my neighborhood is in front of the central bank or near the Starbucks shop, immediately, if you know well your town you will at least know where to begin looking for his/her home.

THE SAME PHILOSOPHY apply to linked lists, after creating our building block which is the struct Node, we need something that holds or play the role of the Starbucks or central bank for example, we need something that when you have it, you have immediately the access to where or what you want, so we need a starting point. To do this let’s make a pointer that points to the struct Node (our house in that example) for now because we didn’t create our first Node and give it information we make it point to nothing (NULL). (i gave it the name of "list" but it can be anything you want).

3- Till now I hope everything is clear, because it is time to create our first linked list (our sequence of houses). In order to fill the Nodes we will start by making just three elements and the rest will be repetitive (you will see). Our Node consist of value and a pointer that points to the next Node. Therefore, we will build or allocate a place for a new Node and we give it information. In our case, we create the first Node called “p”, we give it one as a value, and because it is the first Node, it will point to nothing (i.e.: NULL), {see illustration bellow}.

After that, we give the address of “p” to our famous Starbucks example which is the starting point “liste”. Now by just knowing the “liste”(holds the address of p) we can grab the whole list of Nodes because all Nodes are connected by pointers, so we just need a starting point to know the whole sequence of Nodes. Now you see that this is very simple just given a value and then passing the address to our starting point (and this step is UNIQUE because whatever or regarding the number of Nodes all we want to have is a single starting point and this is actually the idea of what we call “singly linked list”), from here it’s going to be repetitive because we have all the ingredients to create more Nodes.

What we do next? just ask the user for another value let us say it’s 2 and then put it inside another Node we call it for example “p2” then give the address of this second Node to the previous one which is our “p”. In the beginning, “p” was pointing to nothing but now we created a new one so we want “p” to point to “p2” then the new Node points now to nothing (NULL). Let us continue this way until you feel the repetitive process we are making here. Now we have two Nodes, let us create another one, let’s call it “p3” now ask again the user to enter a value then assign it to its place in “p3” and make “p3” points to NULL and to link it with “p2” we give its address to “p2” (i.e. “p2” points to “p3”). Now I hope you saw a repetitive pattern here :

1- We create a new Node : p2, p3 …,

2- We ask the user to enter a value and then put it in its right place (value field),

3- We link between the new Node and the previous one by giving its address to it (p take the address of p2 means p points to p2, p2 takes the address of p3…),

4- We make the last Node points to nothing = NULL.

5- We repeat the same thing until we want to stop.

So you see we have just five repetitive steps, we can then represent this repetitive process by using a loop (a while loop or for loop).

One remarque here, about the " names " p, p2, p3. They are just names so when we use a loop we can just use one single name for the new Node, and because maybe we will need this process i will make it a function so whenever we need to create a linked list we just call this function.

4 - Now the function “insertion_tete” just create a single Node, so we need to loop through it, which is simple by using a while loop.

HOWEVER, if you write the code or just illustrate it in your mind you will notice that ….. you know what ! let us imagine it together:

We enter the first value for example 1 and we put it in its place now the second Node points to NULL and “liste” holds the address of the first Node. The next time we loop, a new value will be entered, 2 for example another time we do the same thing . The problem is that in that function we always make the “liste” points to the new Node we create so in this second pass of the loop we will have the second Node points to the third one and the “liste” (starting point) holds the address of the third Node so if we want to have an output, the first element we entered will be the last one displayed and FOR NOW (remember this thing for later on) we just want to display what we have entered. (input : 1 2 3 ... output : 1 2 3 )

+ The "insertion_tete" function can be more usefull if we wanted to add a new Node at the beginning of an existing linked list.

To do so, obviously we have to keep the “liste” always points to the first Node, and then we make the New Node created in the last position so we need something that gives us the address of that last position of the linked list, then we do the same process again.

As i said, we need something that gives us the address of that last position of the linked list, then we do the same process again.

So we make a function that all its job is to gives us that last position and to have it we need to loop through the list until we found a NULL value because the last Node always points to NULL (indicate the end of the linked list)

5 - Now we need to make a new function that sum up the two function we did till now, this function will do the same thing but in two cases:

- If we want to create a new linked list, our starting point “liste” will be NULL, which means it points to nothing; in this case we just need to create a single new Node (step 1).

- If the starting point “liste” have some address, which means we already have one Node at least. Therefore, to avoid the problem of (step 2) we will process just the last Node given by the second function so we just need to link between the new created Node and the last one and then make this new/last Node points to NULL.

+ another time, this function "insertion_fin" can come in handy if we wanted to (append) add a new Node at the end of an existing linked list.

6- Congratulations! You’ve learned how to create a linked list, From this point we’re going to play with it 🎮

+ Of course we need something that display the linked list because we want to see what we have entered: hence, we will create a function to display our linked list. The way we are going to do it is very simple: first, we will GET the address of our starting point then we will loop from the first Node until the last one, and how we will know that we’re at the last Node! Easy, the last Node always points to NULL so we will make a condition to stop whenever a NULL encountered, and of course inside the loop we will print the value of the Node and to move on to the next Node we will use the pointer (because remember, the Nodes are connected ).

That is how the display function will work. In the bottom, you will see another version of the display function, which is in recursion form why, is that? The process of looping through the linked list and at the end of each loop, we change the pointer (we move on) to the next one. This process looks repetitive (and it is), so why not removing the loop and using the same function but with the new Node. (Easy right?)

+ Another operation we can do to our linked list is looking for (searching) a value and see if it is in the linked list or not. The way we will process is again very easy: we start our loop from the first Node and check if the value we are looking for matches the values in the value part, if not move to the next one and the process continue until we have a NULL, which means the end of the linked list.

In addition, if we found the desired value we can either return an output to tell the user that the value does exist in the list or return the whole linked list starting from the Node that contains the value we were looking for.

(If you understood this function, you can create other forms of access e.g. looking for a value using its position…)

+ Imagine that you want to sort your linked list, which means you want to sort it based on the values stored in it. How we can do this?

Again J easy peasy >> let us do it using the simplest sorting algorithm you know. We compare the first value of the first Node with all the others except itself (obviously) then we move to the next and so on until we get a sorted linked list >> c.f. the illustration bellow.