Data Structure Class Notes: Doubly Linked List

Mobiprep has created last-minute notes for all topics of Doubly Linked List to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Doubly Linked List.

Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.

A doubly linked list is a linked list data structure that includes a link back to the previous node in each node in the structure. This is contrasted with a singly linked list where each node only has a link to the next node in the list. Doubly linked lists also include a field and a link to the next node in the list.

Answer - Pseudo code:

Step 1: IF AVAIL = NULL

Write OVERFLOW

Go to Step 9

[END OF IF]

Step 2: SET NEW_NODE= AVAIL

Step 3: SET AVAIL = AVAIL🡪 NEXT

Step 4: SET NEW_NODE🡪 DATA = VAL

Step 5: SET NEW_NODE 🡪PREV = NULL

Step 6: SET NEW_NODE 🡪 NEXT= START

Step 7: SET START🡪PREV = NEW_NODE

Step 8: SET START = NEW_NODE

Step 9: EXIT

Answer - Pseudo code:

Step 1: IF AVAIL = NULL

Write OVERFLOW

Go to Step 12

[END OF IF]

Step 2: SET NEW_NODE = AVAIL

Step 3: SET AVAIL = AVAIL🡪 NEXT

Step 4: SET NEW_NODE 🡪 DATA = VAL

Step 5: SET PTR = START

Step 6: Repeat Step 7 while PTR 🡪DATA! = NUM

Step 7: SET PTR = PTR🡪 NEXT

[END OF LOOP]

Step 8: SET NEW_NODE🡪 NEXT = PTR

Step 9: SET NEW_NODE🡪 PREV = PTR 🡪PREV

Step 10: SET PTR🡪 PREV = NEW_NODE

Step 11: SET PTR 🡪PREV🡪NEXT =NEW_NODE

Step 12: EXIT

Answer - Pseudo code:

Step 1: IF AVAIL = NULL

Write OVERFLOW

Go to Step 12

[END OF IF]

Step 2: SET NEW_NODE = AVAIL

Step 3: SET AVAIL = AVAIL🡪 NEXT

Step 4: SET NEW_NODE🡪 DATA = VAL

Step 5: SET PTR = START

Step 6: Repeat Step 7 while PTR🡪 DATA! = NUM

Step 7: SET PTR = PTR 🡪NEXT

[END OF LOOP]

Step 8: SET NEW_NODE 🡪NEXT = PTR 🡪NEXT

Step 9: SET NEW_NODE🡪 PREV = PTR

Step 10: SET PTR 🡪NEXT = NEW_NODE

Step 11: SET PTR🡪 NEXT🡪 PREV = NEW_NODE

Step 12: EXIT

Answer - Pseudo code:

Step 1: IF AVAIL = NULL

Write OVERFLOW

Go to Step 11

[END OF IF]

Step 2: SET NEW_NODE = AVAIL

Step 3: SET AVAIL = AVAIL🡪 NEXT

Step 4: SET NEW_NODE🡪 DATA = VAL

Step 5: SET NEW_NODE🡪 NEXT = NULL

Step 6: SET PTR = START

Step 7: Repeat Step 8 while PTR🡪 NEXT! = NULL

Step 8: SET PTR = PTR🡪 NEXT

[END OF LOOP]

Step 9: SET PTR🡪 NEXT = NEW_NODE

Step 10: SET NEW_NODE 🡪PREV = PTR

Step 11: EXIT

Answer - Pseudo code:

Step 1: IF START = NULL

Write UNDERFLOW

Go to Step 6

[END OF IF]

Step 2: SET PTR = START

Step 3: SET START = START 🡪NEXT

Step 4: SET START 🡪PREV = NULL

Step 5: FREE PTR

Step 6: EXIT

Answer - Pseudo code:

Step 1: IF START = NULL

Write UNDERFLOW

Go to Step 9

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR 🡪DATA! = NUM

Step 4: SET PTR = PTR 🡪NEXT

[END OF LOOP]

Step 5: SET TEMP = PTR🡪 NEXT

Step 6: SET PTR🡪 NEXT = TEMP🡪 NEXT

Step 7: SET TEMP🡪 NEXT🡪 PREV = PTR

Step 8: FREE TEMP

Step 9: EXIT

Answer - Pseudo code:

Step 1: IF START = NULL

Write UNDERFLOW

Go to Step 9

[END OF IF]

Step 2: SET PTR = START [

Step 3: Repeat Step 4 while PTR 🡪DATA! = NUM

Step 4: SET PTR = PTR 🡪NEXT

[END OF LOOP]

Step 5: SET TEMP = PTR 🡪PREV

Step 6: SET TEMP🡪 PREV 🡪NEXT = PTR

Step 7: SET PTR🡪 PREV = TEMP 🡪PREV

Step 8: FREE TEMP

Step 9: EXIT

Answer - Pseudo code:

To delete the node from the last assign null to the next of second last node

Step 1: IF START = NULL

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR 🡪NEXT! = NULL

Step 4: SET PTR = PTR 🡪NEXT

Step 5: SET PTR🡪 PREV🡪 NEXT = NULL

Step 6: FREE PTR

Step 7: EXIT

Code Implementation:

#include <stdio.h>

#include <conio.h>

#include <malloc.h>

struct node

{

struct node *next;

int data;

struct node *prev;

};

struct node *start = NULL;

struct node *create_ll(struct node *);

struct node *display(struct node *);

struct node *insert_beg(struct node *);

struct node *insert_end(struct node *);

struct node *insert_before(struct node *);

struct node *insert_after(struct node *);

struct node *delete_beg(struct node *);

struct node *delete_end(struct node *);

struct node *delete_before(struct node *);

struct node *delete_after(struct node *);

struct node *delete_list(struct node *);

int main()

{

int option;

do

{

printf("\n\n *****MAIN MENU *****");

printf("\n 1: Create a list");

printf("\n 2: Display the list");

printf("\n 3: Add a node at the beginning");

printf("\n 4: Add a node at the end");

printf("\n 5: Add a node before a given node");

printf("\n 6: Add a node after a given node");

printf("\n 7: Delete a node from the beginning");

printf("\n 8: Delete a node from the end");

printf("\n 9: Delete a node before a given node");

printf("\n 10: Delete a node after a given node");

printf("\n 11: Delete the entire list");

printf("\n 12: EXIT");

printf("\n\n Enter your option : ");

scanf("%d", &option);

switch(option)

{

case 1: start = create_ll(start);

printf("\n DOUBLY LINKED LIST CREATED");

break;

case 2: start = display(start);

break;

case 3: start = insert_beg(start);

break;

case 4: start = insert_end(start);

break;

case 5: start = insert_before(start);

break;

case 6: start = insert_after(start);

break;

case 7: start = delete_beg(start);

break;

case 8: start = delete_end(start);

break;

case 9: start = delete_before(start);

break;

case 10: start = delete_after(start);

break;

case 11: start = delete_list(start);

printf("\n DOUBLY LINKED LIST DELETED");

break;

}

}while(option != 12);

getch();

return 0;

}

struct node *create_ll(struct node *start)

{

struct node *new_node, *ptr;

int num;

printf("\n Enter –1 to end");

printf("\n Enter the data : ");

scanf("%d", &num);

while(num != -1)

{

if(start == NULL)

{

new_node = (struct node*)malloc(sizeof(struct node));

new_node -> prev = NULL;

new_node -> data = num;

new_node -> next = NULL;

start = new_node;

}

else

{

ptr=start;

new_node = (struct node*)malloc(sizeof(struct node));

new_node->data=num;

while(ptr->next!=NULL)

ptr = ptr->next;

ptr->next = new_node;

new_node->prev=ptr;

new_node->next=NULL;

}

printf("\n Enter the data : ");

scanf("%d", &num);

}

return start;

}

struct node *display(struct node *start)

{

struct node *ptr;

ptr=start;

while(ptr!=NULL)

{

printf("\t %d", ptr -> data);

ptr = ptr -> next;

}

return start;

}

struct node *insert_beg(struct node *start)

{

struct node *new_node;

int num;

printf("\n Enter the data : ");

scanf("%d", &num);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

start -> prev = new_node;

new_node -> next = start;

new_node -> prev = NULL;

start = new_node;

return start;

}

struct node *insert_end(struct node *start)

{

struct node *ptr, *new_node;

int num;

printf("\n Enter the data : ");

scanf("%d", &num);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

ptr=start;

while(ptr -> next != NULL)

ptr = ptr -> next;

ptr -> next = new_node;

new_node -> prev = ptr;

new_node -> next = NULL;

return start;

}

struct node *insert_before(struct node *start)

{

struct node *new_node, *ptr;

int num, val;

printf("\n Enter the data : ");

scanf("%d", &num);

printf("\n Enter the value before which the data has to be inserted:");

scanf("%d", &val);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

ptr = start;

while(ptr -> data != val)

ptr = ptr -> next;

new_node -> next = ptr;

new_node -> prev = ptr-> prev;

ptr -> prev -> next = new_node;

ptr -> prev = new_node;

return start;

}

struct node *insert_after(struct node *start)

{

struct node *new_node, *ptr;

int num, val;

printf("\n Enter the data : ");

scanf("%d", &num);

printf("\n Enter the value after which the data has to be inserted:");

scanf("%d", &val);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

ptr = start;

while(ptr -> data != val)

ptr = ptr -> next;

new_node -> prev = ptr;

new_node -> next = ptr -> next;

ptr -> next -> prev = new_node;

ptr -> next = new_node;

return start;

}

struct node *delete_beg(struct node *start)

{

struct node *ptr;

ptr = start;

start = start -> next;

start -> prev = NULL;

free(ptr);

return start;

}

struct node *delete_end(struct node *start)

{

struct node *ptr;

ptr = start;

while(ptr -> next != NULL)

ptr = ptr -> next;

ptr -> prev -> next = NULL;

free(ptr);

return start;

}

struct node *delete_after(struct node *start)

{

struct node *ptr, *temp;

int val;

printf("\n Enter the value after which the node has to deleted : ");

scanf("%d", &val);

ptr = start;

while(ptr -> data != val)

ptr = ptr -> next;

temp = ptr -> next;

ptr -> next = temp -> next;

temp -> next -> prev = ptr;

free(temp);

return start;

}

struct node *delete_before(struct node *start)

{

struct node *ptr, *temp;

int val;

printf("\n Enter the value before which the node has to deleted:");

scanf("%d", &val);

ptr = start;

while(ptr -> data != val)

ptr = ptr -> next;

temp = ptr -> prev;

if(temp == start)

start = delete_beg(start);

else

{

ptr -> prev = temp -> prev;

temp -> prev -> next = ptr;

}

free(temp);

return start;

}

struct node *delete_list(struct node *start)

{

while(start != NULL)

start = delete_beg(start);

return start;

}