Data structure — LinkedList
In the previous blog, we discussed arrays one of the most commonly known linear data structure in the programming world. Despite its simplicity and popularity Array by nature got few limitations,
- Arrays are static by nature which makes it less flexible to fit when the amount of data grows or shrinks
- Arrays are quite costly for common operations like insertion and deletion
In this blog, we are going to discuss another linear data structure called LinkedList which help to overcome a few limitations.
LinkedList:
LinkedList is a linear data structure where each element is an object. Unlike Array, LinkedList is doesn't have a contiguous memory structure. Each element is linked to the next through a pointer.
Each element in the LinkedList is called Node. Each node contains a key (the data of interest) and an additional pointer for pointing the next element in the list. Initial pointer in a LinkedList is called Head. It is necessary to mention that “Head” is not another node but a pointer to the first element of the LinkedList. For an empty LinkedList value of Head will be null.
To store a linked list, we just need to remember where the first element is. We can find the rest by following the pointers.
Here in the diagram, as we see Head is a pointer point to a node(an object) which contains two pieces a key of value ‘7’ and another pointer pointing to the next node containing the value ‘10’.
Implementation:
public class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
// Constructor to create a new node
// Next is by default initialized
// as null
Node(int d) {
data = d;
next = null;
}
}
}LinkedList Characteristics:
Dynamic nature:
LinkedList is a dynamic structure, means the list can grow or shrink depending upon the data making it more powerful and flexible than Arrays. Unlike Arrays, LinkedList is not stored in a contiguous memory location. Each element int the list is spread across the memory and are linked by the pointers in the Node. Thus whenever a new element needs to be added a separate memory is allocated enough to store both key and the pointer to the next element.
This nature of LinkedList allows it to be used as the base data structure for several other dynamic structures like stacks, queues etc
Simplified insertion and deletion:
Insertion and deletion are the most expensive operation in the Arrays. It needs shifting of the entire elements around the place of operation. On the worst case when the array is full we end up in copying the entire array to a bigger one to fit.
LinkedList makes this little easier. we need to allocate memory for the data to be inserted by creating a node and simply adjusting the pointer around will do the job.
Thus LinkedList won itself the best choice while the total number of objects is unknown at the beginning.
Linear traversal
As we know Arrays provide constant access time and also allows random access of the elements. On the contrary, the LinkedList provides only linear traversal thus the worst-case runtime could be O(n) .
Also, it is hard to traverse the LinkedList backwards(however we can make it simpler with a doubly-linked list)
Memory usage
This characteristic of LinkedList is quite debatable. It is very obvious to see that LinkedList takes an extra memory space for the pointer. But on the contrary, most of the cases Array might end up with memory allocated but not used. LinkedList scores the extra points here by efficiently occupying the spaces only needed. This outweighs Array even with extra memory for the pointer.
Time & Space complexity:
Improvisation to LinkedList
Doubly LinkedList:
Singly LinkedList or LinkedList is simpler to implement, it is quite hard to traverse that in reverse to overcome this we can use Doubly LinkedList, in which each node takes an extra pointer to point the previous item to the element in addition to the pointer for the next item.
A doubly linked list has more efficient iteration, especially if you need to ever iterate in reverse and more efficient deletion of specific nodes.
Using “Tail” pointer:
It might be handy for some cases to have a pointer for the last item in the LinkedList. It is very common to see a “Tail” pointer that points to the last element in the list. Tail pointer not always is a performance improviser but it can never hurt one to have it. It might not be guaranteed it is useful always but is wise to have when appropriate.
It is not very common to see LinkedList in your day-to-day development but LinkedList play key role in most of the other commonly used things like stacks and queues. One very interesting application of LinkedList is in polynomial representation their manipulations. The main advantage of a linked list for polynomial representation is that it can accommodate the number of polynomials of growing sizes so that their combined size does not exceed the total memory available. If you need a structure which needs to be flexible enough for the growing size of data you know where to look for.
References:
