Linked list is a type of data structure which has two parts – Data part, Next part. The combination of both data part and next part is called a node. The data part stores the data and the next part stores the reference (or the address) to the next node.
Let’s take a practical example to define the linked list. .
Assume that 70 students are being taken for an excursion along with their class teacher. The teacher books the ticket and they get random seats allotted which is quite normal if you aren’t thinking of booking an entire bogie. As for the teacher’s part, the situation has become worse as she has to keep track of all the students and can’t afford to miss out on even a single student. To solve this problem, she takes 71 chits and writes the name of all the 70 students from the list she has. She keeps one chit with her and writes the name and berth details of the first student in the list. Then she tells each to write the name of the next student along with their berth no.
With this, when they reach their destination, the teacher can simply go to the first student and thereby go and call all the students one by one as the former always had a reference to the latter.
And think of what the last student will write in the reference part? The answer would be nothing.
This is what the linked list actually does, it stores the data as well as stores a reference to the next node just like the case each student did in the above example.
You might be amazed to know its advantage over the usual arrays which contains a bunch of elements assigned continuously in the memory where you also need to know its size beforehand. Linked list can be roughly called as a dynamic array, and in this you don’t need to assign a definite size and can also create fresh nodes whenever and wherever necessary.
Before beginning the coding part, I would like to introduce some terms which I have already discussed above in a graphical fashion.
Here is the node which contains two parts explained in the image just below it.
Now as the nodes are randomly placed in the free memory, you will have to connect them to each other which will be done by the next part of each node. Just give the address of the next element to the former node and they are linked!
Check the situation after linking all the elements.
As you can see, the last node is pointed nowhere and ends up with a dangling next part. To avoid problems and to be on the safer side, we point it to NULL rather than leaving it as it is in the case right now.
Now the case looks something like this and looks alot more safer. Isn’t it?
Enough of discussions now, let’s start the fun part. Jump on to the next page for the coding part.