Till now we've talked about linked lists and the basic operations associated with it. But today we're gonna talk about linked lists only, but with a slight variation.
In a linked list, traversal can be done one way(a node only had "next" component associated with it), in a doubly linked list, traversal can be done both ways. That means, we can go from one node to its next node as well as move to its previous node(node will have "next" as well as "previous" component associated with it).
So, we can make use of its doubly traversable property to do the insertion and deletion operations.
Basic structure
typedef struct node{
int val;
struct node *next;
struct node *prev;
}NODE;
Here, as you can see, we have defined pointer to the next node and pointer to the previous node for the current node.
Create Node
NODE *createnode(int val){
NODE *newnode = (NODE *)malloc(sizeof(NODE));
newnode->val = val;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
Here, we have made both - next and prev to point at NULL initially when the node is created. When we later link the node to a linked list, we'll redefine the values for the next and prev pointers.
Insertion
Insertion is done the same way it is done in a singly linked list. For more clarity check this post out. We're gonna do insertion from the rear end here.
The C code for it is -
NODE *insertnode(NODE *head, int val){
NODE *newnode = createnode(val);
if(head == NULL){
head = newnode;
}
else{
NODE *temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
//temp reaches the end node;
temp->next = newnode;
newnode->prev = temp;
}
return head;
}
Additionally we've linked the "prev" of the newnode to node that it is being inserted after so that later on we can move both ways from the current node (forward as well as backwards).
Deletion
Even deletion is same as what we did in the Singly Linked List. For any queries, take a look at this article.
View Website
View Website
View Website
Here we're gonna perform deletion at index value entered by the user.
The C code for it is:
NODE* deletenode(NODE *head, int idx){
if(head == NULL){
printf("Empty Linked List!\n");
}
else{
NODE *temp = head;
int count=0;
if(idx == 0){//first element is the target
head = head->next;
printf("head data: %d\n",head->val);
temp = head->prev;
temp->next = NULL;
printf("temp data: %d\n",temp->val);
head->prev = NULL;
}
else{
while(count!=idx && temp->next!=NULL){
temp = temp->next;
count++;
}//temp reaches the target element
if(count==idx && temp->next == NULL){//last element is the target;
temp->prev->next = NULL;
temp->prev = NULL;
}
else{
NODE *temp1 = temp->next;//next node of the target node
NODE *temp2 = temp->prev;//the element before the target node
temp->next = NULL;
temp->prev = NULL;
temp2->next = temp1;//the next of node before the target node is set to the node next to the target node
temp1->prev = temp2;
}
free(temp);
}
}
return head;
}
This code first checks if the list is empty or not, then it traverses to the destination node, links the previous of the destination node to the next of the destination node. Finally, it frees the destination node.
Note that I've given separate conditions for deletion of the last and First nodes.
Display
Display function is exactly the same way as done in a simple linked list. In it, we just have to traverse throughout the linked list using while-loop until the next of the current node becomes zero.
void display(NODE *head){
if(head == NULL){
printf("Empty Linked List\n");
}else{
NODE *temp = head;
printf("Linked List: ");
while(temp!=NULL){
printf("%d ", temp->val);
temp = temp->next;
}printf("\n");
}
}
Full code
The whole program looks something like this:
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int val;
struct node *next;
struct node *prev;
}NODE;
NODE *createnode(int val){
NODE *newnode = (NODE *)malloc(sizeof(NODE));
newnode->val = val;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
NODE *insertnode(NODE *head, int val){
NODE *newnode = createnode(val);
if(head == NULL){
head = newnode;
}
else{
NODE *temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
//temp reaches the end node;
temp->next = newnode;
newnode->prev = temp;
}
return head;
}
NODE* deletenode(NODE *head, int idx){
if(head == NULL){
printf("Empty Linked List!\n");
}
else{
NODE *temp = head;
int count=0;
if(idx == 0){
head = head->next;
printf("head data: %d\n",head->val);
temp = head->prev;
temp->next = NULL;
printf("temp data: %d\n",temp->val);
head->prev = NULL;
}
else{
while(count!=idx && temp->next!=NULL){
temp = temp->next;
count++;
}//temp reaches the target element
if(count==idx && temp->next == NULL){//last element is the target;
temp->prev->next = NULL;
temp->prev = NULL;
}
else{
NODE *temp1 = temp->next;//next node of the target node
NODE *temp2 = temp->prev;//the element before the target node
temp->next = NULL;
temp->prev = NULL;
temp2->next = temp1;//the next of node before the target node is set to the node next to the target node
temp1->prev = temp2;
}
free(temp);
}
}
return head;
}
void display(NODE *head){
if(head == NULL){
printf("Empty Linked List\n");
}else{
NODE *temp = head;
printf("Linked List: ");
while(temp!=NULL){
printf("%d ", temp->val);
temp = temp->next;
}printf("\n");
}
}
int main(){
NODE *head = NULL;
printf("\tDOUBLY LINKED LIST IMPLEMENTATION: \n");
printf("\n\tEnter: \n\t1. Insert\n\t2. Delete \n\t3. Display \n\t4. Exit\n");
int ch;
do{
printf("Enter choice: ");
scanf(" %d", &ch);
switch(ch){
case 1:
{
//Insert
printf("enter the element to be inserted: ");
int val;
scanf(" %d", &val);
head = insertnode(head, val);
break;
}
case 2:
{
//delete
printf("Enter the index of element to be deleted: ");
int idx;
scanf(" %d", &idx);
head = deletenode(head, idx);
break;
}
case 3:
{
//Display
display(head);
break;
}
case 4:
{
//exit
printf("EXITING...\n");
break;
}
default:
{
printf("Enter Valid Choice!\n");
break;
}
}
}
while(ch!=4);
}
This is it!
Thanks for reading! I hope you enjoyed this article. You can check out my other posts here.
Comments (0)