Linear Data Structures — Linked List — What, Why and How Explained
Imagine you have gone to a crowded place, say to a k-pop concert with your friends and you don’t have any electronics or compass with you.
Now one of your friends wants to go a bit far away to fetch something, say light sticks. If he goes to fetch it, then he won't be able to find and reach you in the large crowd :(
How would you solve this problem? Here is a solution for it given that you have sufficient friends with you. You have to make your friends stand in pairs with an even amount of distance between them till the target place. In the pair of your friends standing at equal distances, one of them should look at the next friend pair nearer to the target place, and the other person to look at the previous friend pair. Now your friend after reaching the target place can return to the initial place easily (and the friends who stand in pairs of course) with the help of the person in the pair who was looking over the previous pair.
If you managed to set up or understand this, then Congratulations! you have successfully implemented(understood) a doubly-linked list.
If you didn’t understand the practical example don’t worry about it, you will understand it at the end of this article :)
What is a data structure and why should you care? Data structures are a core concept of Software Development. I would like to quote from Wikipedia.
In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms.
Even though Data Structures are important but why Linked List when there are a lot of Data Structures? Here are the advantages of linked list
- Dynamic Data structure: Linked list unlike arrays is dynamic data structures. It basically means that amount of data it can store is not fixed i.e, we can increase or decrease the size of the linked list as per the needs.
- Insertion and deletion operations are easier.
- Efficient Memory Utilization: Unlike arrays, there is no need to pre-allocate memory.
- Linear Data Structures: As it is a linear data structure, accessing the data can be done sequentially.
- Easy Implementation of Other Linear Data Structures: Linear Data Structures such as Stack, Queue can be easily implemented using the Linked list.
With why you should learn the linked list, lets deep dive into the linked list!
Linked List is made of nodes.
A single Node in Linked List consists of 2 parts:-
- Data: This is where the data is stored.
- Reference to the next Node. This consists of a reference to the next node. using this reference we can access data in the next node. We generally name it as “next”
If you are using low-level language like C then you will be using pointers to create a reference to the next node. pointers are nothing but variables that hold the address of another variable. So we will be storing the address of the next node in the reference part of the node.
In case you are using other languages then you create a reference just by assigning another variable to it.
What I mean by “A references B” is that the variable “A” and the variable “B”, share the same memory block. So changing A changes the value stored and hence changes the value accessed by B. In other words, A and B reference the same memory block.
This is what a typical Linked List Looks like 👆.
Here are some key things to note:-
- we have each node’s reference part referencing its next node.
- We have a variable named “head” that references the first node.
- The last Node in the linked list has no node after it, so it’s reference part stores NULL/null / None(this is a special value in programming languages)
Let's start to build our linked list!
Adding Nodes to a Linked List
We will start with the head variable referencing nothing or in other words, we initialize it with null/NULL/None.
Now let's add our first Node. Let's create a new instance of the Node class and assign it to the“ head”. As there is no Node after the first Node, its reference part will reference nothing.
Now let's add another Node!
We can add a new Node to a linked list in three ways:-
- In the beginning. This is the fastest way of adding a Node to the linked list. It only takes constant time every time!
- In the last. You can do it in two ways. One takes constant time and the other takes linear time. If you maintain a variable holding reference to the last Node, then it will take constant time. In the other case, you would have to transverse the whole list to reach the end of the linked list, So it takes a linear amount of time.
- In between the beginning and last. The time taken varies between the above cases.
Psuedo code to add the new Node to the beginning of Linked List:-
if head is null
then, assign new Node to head, i.e head references the new Node
else
assign head, to the next of new Node.
assign newNode to the headPsuedo Code to add the new Node to the last of the list if you don’t maintain a variable to hold a reference to the last Node. This is a slow implementation as it takes a linear amount of time, So its best to maintain a tail variable holding reference to the last Node, then it will take constant time.
if head is null
then, assign the new Node to head, i.e head references the new Node.
else
tranverse the linked list till the last Node
then assign the new Node to the next of the last Node.Psuedo Code to add the New Node to the last by maintaining a reference to the last Node.
if head or tail is null
then, assign the new Node to both head and tail
else
assign the new Node to the next of tail
assing the new Node to tailCode Examples in python for addition to the beginning and also add to the end, both in constant time!
Congratulations! We have built our Linked List from Scratch.
Time Complexity of a Linked List
Variants of Linked List
1.Singly Linked List
2.Doubly Linked List
A doubly linked list not only holds a reference to the next node but also holds a reference to the previous node, which makes it possible to traverse the list in both directions.
3.Circular Linked List
References: