More

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.

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 andtraversal 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;
};

void traversal(struct node *ptr){
while(ptr!=NULL){
cout<<ptr->data<<" ";
ptr=ptr->next;}
}
int main(){
struct node *second;
struct node *third;
second=(struct node *)malloc(sizeof(struct node));
third=(struct node *)malloc(sizeof(struct node));
second->data=10;
second->next=third;
third->data=40;
third->next=NULL;
}
``````

Output:

``7 10 40``

Here’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;
};

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->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));
int i=0;
while(i != index-1){
p=p->next;
i++;
}
ptr->data=data;
ptr->next=p->next;
p->next=ptr;

}

//insertion at the end

struct node *insertAtEnd(struct node *head,int data){
struct node *ptr=(struct node *)malloc(sizeof(struct node));
while(p->next != NULL){
p=p->next;
}
ptr->data=data;
p->next=ptr;
ptr->next=NULL;

}

//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;
}
int main(){
struct node *second;
struct node *third;
second=(struct node *)malloc(sizeof(struct node));
third=(struct node *)malloc(sizeof(struct node));
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;

};

while(ptr !=NULL){
cout<<ptr->data<<" ";
ptr=ptr->next;
}
}

//Deletion of the first element

free(ptr);
}

//Deletion of the element in between

struct node *DltInBtw(struct node *head, int index){
for(int i=0;i<index-1;i++){
p=p->next;
q=q->next;
}
p->next=q->next;
free(q);

}

//Deletion of the last element

while(q->next != NULL){
p=p->next;
q=q->next;
}
p->next=NULL;
free(q);
}

//Deletion of any particular given data

struct node *partData(struct node *head,int value){
while(q->data != value && q->next !=NULL){
p=p->next;
q=q->next;

}
if(q->data==value){
p->next=q->next;
free(q);

}
}

int main(){
struct node *second;
struct node *third;
struct node *fourth;
second=(struct node *)malloc(sizeof(struct node));
third=(struct node *)malloc(sizeof(struct node));
fourth=(struct node *)malloc(sizeof(struct node));
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.

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 *second;
struct node *third;
struct node *fourth;
second=(struct node*)malloc(sizeof(struct node));
third=(struct node*)malloc(sizeof(struct node));
fourth=(struct node*)malloc(sizeof(struct node));
second->data=11;
third->data=12;
fourth->data=13;
second->next=third;
third->prev=second;
third->next=fourth;
fourth->prev=third;
fourth->next=NULL;
//printing elements from left to right
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 – 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 Subscribe Today

Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.