Linked Lists for Dummies
Explaining all the four types.
Earlier I explained Array Data Structure and today I am explaining Linked Lists. A linked list is a linear data structure in which the order of its elements is not pre-defined in the memory.
For example, our to-do list that we make every day in which we define the tasks one after another.
Now I have to tell you that there is not just one type of linked list. In fact, there are 4 types namely,
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Doubly Circular Linked List
I will try to explain all the four types with the best of my efforts, so stay with me till the end.
Singly Linked List
A singly linked list is the simplest of all but first, we have to understand the concept of node and what a node consists of.
Like I told you earlier, unlike Array we cannot store elements in a linked list in a continuous fashion. So how do we make a linked list and store the elements?
As you know everything we store in memory has an address. That address is basically in hexadecimal form. Eg: C800:5
So we use this address to access the next element in the list. We start with HEAD, Head stores the address of the first NODE of the linked list and a NODE is consists of the data part and the address part which contains the address of the next node in the memory.
As you can see in the diagram above the head is connected to the first node and the first node’s address part is pointing towards the next node. But how do we know that we have reached the end of the list?
We store NULL in the last node which states that this is the last element of the list and is not pointing to anything further.
Doubly Linked List
The doubly linked list is an advanced version of the singly linked list and provides us with a very important feature.
In the singly linked list, we can only access the next element, we cannot go back if want to access the previous element. Doubly Linked List comes with this functionality.
Every node now has three parts:
- The data part
- The previous node’s address
- The next node’s address
As the first node doesn’t have any previous node to point to, the previous part of the first node holds NULL. and the last node still contains the NULL to indicate the end of the list.
This implementation of this list is slightly more difficult than the singly linked list but also very fun to make.
Circular Linked List
The circular linked list is a singly linked list but with a twist, unlike the singly in which the last node contains NULL. In circular the last node is pointing back to the first node.
With this feature, we can start accessing the elements from the start even if we reached the end of the list.
This functionality is not provided in the singly linked list as when we reach the end of the singly list, there is no way to start automatically from the beginning.
Doubly Circular Linked List
This is the last of the type of linked list that we are discussing, I promise.
When we combine the functionality of a doubly linked list and a circular linked list, what we get is what we call a doubly circular linked list.
This is the most advanced type of linked list of all four types. More features also mean that this is the hardest to implement and is more prone to errors than the rest.
The FIRST node’s previous is connected to the LAST node and the LAST node in which we usually store NULL is pointing towards the FIRST node.
I know it is difficult to understand in words that’s why I have provided you with the illustrations of how they look when we go and implement them.
Conclusion
Linked lists are a very easy topic but sometimes it is hard for beginners to make sense of them. Thank you for staying with me through the end. You are a very keen learner as I am so glad that I was able to help you in any way in your learning.
