Linked List is a multiple blocks of memory linked with each other.
There are basically three types of Linked List, we will be discussing about each on them in detail.
Singly Linked List
Important points:
- Each block consist of two parts i.e., the data and the address of the next node.
- Size of a linked list can always be changed (dynamic size) as per requirement.
- Data is stored in non-contiguous manner. That is why random access of elements are not allowed.
- Extra memory space for pointers are required.
- Insertion and deletion of elements is quite easy as compare to arrays.
Creation of a node in a singly linked list
Nodes are created using structure i.e.,
struct node{
int data;
struct node *next;
};
Here’s a pictorial representation of a single node in a singly linked list.
Creation and traversal of a singly linked list:
#include<iostream>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
//node implementation:
struct node{
int data;
struct node * next;
};
//linked list traversal:
void traversal(struct node *ptr){
while(ptr!=NULL){
cout<<ptr->data<<" ";
ptr=ptr->next;}
}
int main(){
//creating and linking three nodes:
struct node *head;
struct node *second;
struct node *third;
head=(struct node *)malloc(sizeof(struct node));
second=(struct node *)malloc(sizeof(struct node));
third=(struct node *)malloc(sizeof(struct node));
head->data=7;
head->next=second;
second->data=10;
second->next=third;
third->data=40;
third->next=NULL;
traversal(head);
}
Output:
7 10 40Here’s a pictorial representation of the linked list, which is created using the program above.
Insertion in a singly linked list:
#include<iostream>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
struct node * next;
};
//traversal of the linked list
void traversal(struct node *ptr){
while(ptr!=NULL){
cout<<ptr->data<<" ";
ptr=ptr->next;}
}
//insertion at the beginning of the linked list
struct node *insertAtBeg(struct node *head, int data){
struct node *ptr=(struct node *)malloc(sizeof(struct node));
ptr->next=head;
ptr->data=data;
return ptr;
}
//insertion at a given index (in between)
struct node *insertInBetw(struct node *head, int data,int index){
struct node *ptr=(struct node *)malloc(sizeof(struct node));
struct node *p=head;
int i=0;
while(i != index-1){
p=p->next;
i++;
}
ptr->data=data;
ptr->next=p->next;
p->next=ptr;
return head;
}
//insertion at the end
struct node *insertAtEnd(struct node *head,int data){
struct node *ptr=(struct node *)malloc(sizeof(struct node));
struct node *p =head;
while(p->next != NULL){
p=p->next;
}
ptr->data=data;
p->next=ptr;
ptr->next=NULL;
return head;
}
//insertion after a given node
struct node *insertAfterNode(struct node *head, struct node *prevnode, int data){
struct node *ptr=(struct node *)malloc(sizeof(struct node));
ptr->data=data;
ptr->next=prevnode->next;
prevnode->next=ptr;
return head;
}
int main(){
struct node *head;
struct node *second;
struct node *third;
head=(struct node *)malloc(sizeof(struct node));
second=(struct node *)malloc(sizeof(struct node));
third=(struct node *)malloc(sizeof(struct node));
head->data=7;
head->next=second;
second->data=10;
second->next=third;
third->data=40;
third->next=NULL;
}In the above code, seperate functions for all type of insertion is present.We just need to simply call these functions in the main function for inserting elements in our linked list.
Deletion in a singly linked list:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *next;
};
//traversal of the linked list
void trav(struct node *head){
struct node*ptr=head;
while(ptr !=NULL){
cout<<ptr->data<<" ";
ptr=ptr->next;
}
}
//Deletion of the first element
struct node *DltInBeg(struct node *head){
struct node *ptr=head;
head=head->next;
free(ptr);
return head;
}
//Deletion of the element in between
struct node *DltInBtw(struct node *head, int index){
struct node*p=head;
struct node *q=head->next;
for(int i=0;i<index-1;i++){
p=p->next;
q=q->next;
}
p->next=q->next;
free(q);
return head;
}
//Deletion of the last element
struct node *DltEnd(struct node*head){
struct node*p=head;
struct node*q=head->next;
while(q->next != NULL){
p=p->next;
q=q->next;
}
p->next=NULL;
free(q);
return head;
}
//Deletion of any particular given data
struct node *partData(struct node *head,int value){
struct node *p=head;
struct node *q=head->next;
while(q->data != value && q->next !=NULL){
p=p->next;
q=q->next;
}
if(q->data==value){
p->next=q->next;
free(q);
}
return head;
}
int main(){
struct node *head;
struct node *second;
struct node *third;
struct node *fourth;
head=(struct node *)malloc(sizeof(struct node));
second=(struct node *)malloc(sizeof(struct node));
third=(struct node *)malloc(sizeof(struct node));
fourth=(struct node *)malloc(sizeof(struct node));
head->data=7;
head->next=second;
second->data=10;
second->next=third;
third->data=40;
third->next=fourth;
fourth->data=56;
fourth->next=NULL;
return 0;
}
In the above code, separate functions for all type of deletion is present. We just need to simply call these functions in the main function for deleting elements in our linked list.
Doubly Linked List
In doubly linked list each node contain three things i.e., the data, address of the previous and the next node.
Creation of a node:
Nodes are created using the structure i.e.,
struct node{
int data;
struct node *prev;
struct node *next;
};
Here’s a pictorial representation of a single node in a doubly linked list.
Creation and traversal of a doubly linked list:
#include<iostream>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *prev;
struct node *next;
};
//traversal of the elements in forward direction
void travForw(struct node *ptr){
while(ptr != NULL){
cout<<ptr->data<<" ";
ptr=ptr->next;
}
}
//traversal of the elements in backward direction
void travPrev(struct node *ptr){
while(ptr != NULL){
cout<<ptr->data<<" ";
ptr=ptr->prev;
}
}
int main(){
struct node *head;
struct node *second;
struct node *third;
struct node *fourth;
head=(struct node*)malloc(sizeof(struct node));
second=(struct node*)malloc(sizeof(struct node));
third=(struct node*)malloc(sizeof(struct node));
fourth=(struct node*)malloc(sizeof(struct node));
head->data=10;
second->data=11;
third->data=12;
fourth->data=13;
head->prev=NULL;
head->next=second;
second->prev=head;
second->next=third;
third->prev=second;
third->next=fourth;
fourth->prev=third;
fourth->next=NULL;
//printing elements from left to right
travForw(head);
cout<<endl;
//printing elements from right to left
travPrev(fourth);
return 0;
}
Output:
10 11 12 13
13 12 11 10
Here’s a pictorial representation of the linked list, which is created using the program above.
We can traverse, insert, delete similarly as we did in the singly linked list. The only difference in the doubly linked list is that we can traverse from both sides of the list.
Circular Linked List:
Circular Linked List – Detailed Article
Time Complexity:
In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n).
In a doubly-linked list, the time complexity for inserting and deleting an element is O(1).
Read Next: Combinatorial Game Theory | Game of Nim
