Linked List
- Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
- A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
- The last node of the list contains pointer to the null.
Uses of Linked List
- The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space.
- list size is limited to the memory size and doesn’t need to be declared in advance.
- Empty node can not be present in the linked list.
- We can store values of primitive types or objects in the singly linked list.
Why use linked list over array?
Till now, we were using array data structure to organize the group of elements that are to be stored individually in the memory. However, Array has several advantages and disadvantages which must be known in order to decide the data structure which will be used throughout the program.
Array contains following limitations:
- The size of array must be known in advance before using it in the program.
- Increasing size of the array is a time taking process. It is almost impossible to expand the size of the array at run time.
- All the elements in the array need to be contiguously stored in the memory. Inserting any element in the array needs shifting of all its predecessors.
Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful because,
- It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers.
- Sizing is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program’s demand and limited to the available memory space.
Singly linked list or One way chain
Singly linked list can be defined as the collection of ordered set of elements. The number of elements may vary according to need of the program. A node in the singly linked list consist of two parts: data part and link part. Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each node contains only next pointer, therefore we can not traverse the list in the reverse direction.
Consider an example where the marks obtained by the student in three subjects are stored in a linked list as shown in the figure.
In the above figure, the arrow represents the links. The data part of every node contains the marks obtained by the student in the different subject. The last node in the list is identified by the null pointer which is present in the address part of the last node. We can have as many elements we require, in the data part of the list.
Advantages of Linked Lists
- They are a dynamic in nature which allocates the memory when required.
- Insertion and deletion operations can be easily implemented.
- Stacks and queues can be easily executed.
- Linked List reduces the access time.
Disadvantages of Linked Lists
- The memory is wasted as pointers require extra memory for storage.
- No element can be accessed randomly; it has to access each node sequentially.
- Reverse Traversing is difficult in linked list.
Applications of Linked Lists
- Linked lists are used to implement stacks, queues, graphs, etc.
- Linked lists let you insert elements at the beginning and end of the list.
- In Linked Lists we don’t need to know the size in advance.
Types of Linked Lists
There are 3 different implementations of Linked List available, they are:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Let’s know more about them and how they are different from each other.
Singly Linked List
Singly linked lists contain nodes which have a data part as well as an address part i.e. next, which points to the next node in the sequence of nodes.
The operations we can perform on singly linked lists are insertion, deletion and traversal.
Doubly Linked List
In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.
Circular Linked List
In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
We will learn about all the 3 types of linked list, one by one, in the next tutorials. So click on Next button, let’s learn more about linked lists.
Operation of List
Insertion at the Beginning
Steps to insert a Node at beginning :
- The first Node is the Head for any Linked List.
- When a new Linked List is instantiated, it just has the Head, which is Null.
- Else, the Head holds the pointer to the first Node of the List.
- When we want to add any Node at the front, we must make the head point to it.
- And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new List) or the pointer to the first Node of the List.
- The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.
int LinkedList :: addAtFront(node *n) {
int i = 0;
//making the next of the new Node point to Head
n->next = head;
//making the new Node as Head
head = n;
i++;
//returning the position where Node is added
return i;
}
Inserting at the End
Steps to insert a Node at the end :
- If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
- If the Linked List is not empty then we find the last node, and make it’ next to the new Node, hence making the new node the last Node.
int LinkedList :: addAtEnd(node *n) { //If list is empty if(head == NULL) { //making the new Node as Head head = n; //making the next pointe of the new Node as Null n->next = NULL; } else { //getting the last node node *n2 = getLastNode(); n2->next = n; } } node* LinkedList :: getLastNode() { //creating a pointer pointing to Head node* ptr = head; //Iterating over the list till the node whose Next pointer points to null //Return that node, because that will be the last node. while(ptr->next!=NULL) { //if Next is not Null, take the pointer one step forward ptr = ptr->next; } return ptr; }
Searching for an Element in the List
In searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the data of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point the next Node, and so on.
node* LinkedList :: search(int x) {
node *ptr = head;
while(ptr != NULL && ptr->data != x) {
//until we reach the end or we find a Node with data x, we keep moving
ptr = ptr->next;
}
return ptr;
}
Deleting a Node from the List
Deleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove the Node from the List.
To remove any Node from the list, we need to do the following :
- If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted.
- If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node next to it.
node* LinkedList :: deleteNode(int x) {
//searching the Node with data x
node *n = search(x);
node *ptr = head;
if(ptr == n) {
ptr->next = n->next;
return n;
}
else {
while(ptr->next != n) {
ptr = ptr->next;
}
ptr->next = n->next;
return n;
}
}
Doubly Linked List
Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.
- Link − Each link of a linked list can store a data called an element.
- Next − Each link of a linked list contains a link to the next link called Next.
- Prev − Each link of a linked list contains a link to the previous link called Prev.
- LinkedList − A Linked List contains the connection link to the first link called First and to the last link called Last.
Doubly Linked List Representation
As per the above illustration, following are the important points to be considered.
- Doubly Linked List contains a link element called first and last.
- Each link carries a data field(s) and two link fields called next and prev.
- Each link is linked with its next link using its next link.
- Each link is linked with its previous link using its previous link.
- The last link carries a link as null to mark the end of the list.
Basic Operations
Following are the basic operations supported by a list.
- Insertion − Adds an element at the beginning of the list.
- Deletion − Deletes an element at the beginning of the list.
- Insert Last − Adds an element at the end of the list.
- Delete Last − Deletes an element from the end of the list.
- Insert After − Adds an element after an item of the list.
- Delete − Deletes an element from the list using the key.
- Display forward − Displays the complete list in a forward manner.
- Display backward − Displays the complete list in a backward manner.
Header Linked List
A Header linked list is one more variant of linked list. In Header linked list, we have a special node present at the beginning of the linked list. This special node is used to store number of nodes present in the linked list. In other linked list variant, if we want to know the size of the linked list we use traversal method. But in Header linked list, the size of the linked list is stored in its header itself.
Types of Header linked list
- Grounded header linked list.
- Circular header linked list.
B.C.A study 