Write a C program to implement the operations on a Doubly linked list. The program should include the following operations.

Write a C program to implement the operations on a Doubly linked list. The program should include the following operations.

1)      Creation of list

2)      Traversal of list

a)      Forward traversal

b)      Reverse traversal

3)      Insertion of element

a)      At the beginning of a list

b)      At the end of a list

c)      Before a given node

d)      After a given node

e)      At a given position.

4)      Deletion of a node

a) First node

b)      Last node

c)      Node with a particular value

d)      Node at a given position.

**CODING**

Source Code:

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<malloc.h>
4.  
5. //definition of the basic element of the linked list, node
6. struct node
7. {
8.     int data;
9.     struct node * prev;
10.     struct node * next;
11. }*head, *end;
12.  
13. //Prototype definitions of the functions
14. void createList(int n);
15. void displayList();
16. void revdisplaylist();
17. void insertAtBeginning(int data);
18. void insertAtEnd(int data);
19. void insertAtBN(int data, int position);
20. void DlListDeleteFirstNode();
21. void DlListDeleteendNode();
22. void DlListDeleteAnyNode(int pos);
23.  
24. int main()
25. {
26.                //Declaration and initialization of variables
27.     int n, data, choice=1, a,insPlc;
28.  
29.                //Initializing head and end pointers to NULL
30.     head = NULL;
31.     end = NULL;
32.    
33.     //Creation of the linked list
34.                printf("\n       CREATE A DOUBLY LINKED LIST      ");
35.                printf("\n-----------------------------------------\n");
36.     printf("\n Enter the total number of nodes: ");
37.     scanf("%d",&n);
38.     createList(n);
39.     displayList();
40.     revdisplaylist();
41.  
42.     //Repeat the following steps until user wants to exit the program
43.     while(choice != 7)
44.     {
45.         //Displaying the menu
46.         printf("\n         DOUBLY LINKED LIST PROGRAM\n");
47.         printf("-----------------------------------------\n");
48.   
49.         printf("1. Insert node at beginning\n");
50.         printf("2. Insert node at end\n");
51.         printf("3. Insert node at a particular position\n");
52.         printf("4. Delete the first node\n");
53.         printf("5. Delete the end node\n");
54.         printf("6. Delete the node at a particular position \n");
55.         printf("7. Exit\n");
56.         printf("--------------------------------------------\n");
57.        
58.         //Inputting the choice from the user
59.                               printf(" Enter your choice : ");
60.         scanf("%d",&choice);
61.  
62.         //Calling functions as per the input of the user
63.         switch(choice)
64.         {
65.            
66.             case 1:
67.                 printf("\n Enter data of first node : ");
68.                 scanf("%d",&data);
69.  
70.                 insertAtBeginning(data);
71.                 displayList();
72.                 revdisplaylist();
73.                 break;
74.             case 2:
75.                 printf("\n Enter data of end node : ");
76.                 scanf("%d",&data);
77.  
78.                 insertAtEnd(data);
79.                 displayList();
80.                 revdisplaylist();
81.                 break;
82.             case 3:
83.                 printf("\n Enter the position(0 to Totalnode+1) where you want to insert new node: ");
84.                 scanf("%d",&n);
85.                 printf("\n Enter inserting data value: ");
86.                 scanf("%d",&data);
87.  
88.                 insertAtBN(data,n);
89.                 displayList();
90.                 revdisplaylist();
91.                 break;
92.             case 4:
93.            
94.                DlListDeleteFirstNode();
95.                 displayList();
96.                 revdisplaylist();
97.                 break;
98.                
99.             case 5:
100.            
101.                DlListDeleteendNode();
102.                 displayList();
103.                 revdisplaylist();
104.                 break;
105.                
106.             case 6:
107.            
108.                //Inputting the position from the user
109.                printf(" Enter the position(1 to Totalnode) to delete a node : ");
110.                scanf("%d",&insPlc);
111.                                                                                                         
112.                DlListDeleteAnyNode(insPlc);
113.                displayList();
114.                revdisplaylist();
115.                 break;
116.                
117.             case 7:
118.                printf("Stop program.Exit ");
119.                 break;
120.             default:
121.                 printf("\n Error! Invalid choice...Try again. ");
122.         }
123.     }
124.     return 0;
125. }
126.  
127. //defining the dunction to create the list
128. void createList(int n)
129. {
130.                //initialization of variables
131.     int i, data;
132.     struct node *newNode;
133.  
134.                //Creating the list
135.     if(n >= 1)
136.     {
137.         head = (struct node *)malloc(sizeof(struct node));
138.  
139.                //Inputting the data into the node
140.         printf(" Enter data of first node: ");
141.         scanf("%d",&data);
142.  
143.         head->data = data;
144.         head->prev = NULL;
145.         head->next = NULL;
146.  
147.         end = head;
148.  
149.        
150.         //Create and link rest of the n-1 nodes
151.         for(i=2; i<=n; i++)
152.         {
153.                //Allocating the memory for the nodes
154.             newNode = (struct node *)malloc(sizeof(struct node));
155.                              
156.                                              //Inputting the data in the nodes
157.             printf(" Enter data of next node: ");
158.             scanf("%d", &data);
159.  
160.             newNode->data = data;
161.             newNode->prev = end; // Link new node with the previous node
162.             newNode->next = NULL;
163.  
164.             end->next = newNode; // Link previous node with the new node
165.             end = newNode;          // Make new node as end/previous node
166.         }
167.  
168.                               //Informing link created successfully
169.         printf("\n........CREATION SUCCESSFUL........\n");
170.     }
171. }
172.  
173. //Function to display the linked list
174. void displayList()
175. {
176.                //initialization and declaration of variables
177.     struct node * temp;
178.     int n = 1;
179.  
180.                //If the linked list is empty
181.     if(head == NULL)
182.     {
183.         printf("List is empty.\n");
184.     }
185.     else
186.     {
187.                //Displaying the elements in the linked list
188.         temp = head;
189.         printf("\n Data in the list:\n");
190.                               printf("------------------\n");
191.         while(temp != NULL)
192.         {
193.             printf("Data of %d node = %d\n", n, temp->data);
194.  
195.             n++;
196.  
197.             //Move the current pointer to next node
198.             temp = temp->next;
199.         }
200.     }
201. }
202.  
203. //Function of reverse the display list
204. void revdisplaylist()
205. {
206.                node *list = end;
207.                printf("\n\nThe list printed from back to front is :\n");
208.  
209.                while(list!=head)
210.                {
211.                               printf("%4d",list->data);
212.                               list=list->prev;
213.                }
214.     printf("%4d\n",list->data);
215. }
216.  
217. //function to insert a node at the begining of the list
218. void insertAtBeginning(int data)
219. {
220.                //declaring a newe node
221.     struct node * newNode;
222.  
223.                //if the list is empty
224.     if(head == NULL)
225.     {
226.         printf("\n Error! List is Empty!\n");
227.     }
228.     else
229.     {
230.                //allocating memory fo the node
231.         newNode = (struct node *)malloc(sizeof(struct node));
232.  
233.         newNode->data = data;
234.         newNode->next = head; // Point to next node which is currently head
235.         newNode->prev = NULL; // Previous node of first node is NULL
236.  
237.         // Link previous address field of head with newnode
238.         head->prev = newNode;
239.  
240.         // Make the new node as head node
241.         head = newNode;
242.     }
243. }
244.  
245. //function to add a node at the end of the list
246. void insertAtEnd(int data)
247. {
248.                //declaratrion opf a new node
249.     struct node * newNode;
250.               
251.                //if the node is empty
252.     if(end == NULL)
253.     {
254.         printf("\n Error! List is empty!\n");
255.     }
256.     else
257.     {
258.                //allocating memoty for the new node
259.         newNode = (struct node *)malloc(sizeof(struct node));
260.  
261.                //inserting the node
262.         newNode->data = data;
263.         newNode->next = NULL;
264.         newNode->prev = end;
265.  
266.         end->next = newNode;
267.         end = newNode;
268.     }
269. }
270.  
271. //function to insert a node at nth position of a doubly linked list
272. void insertAtBN(int data, int position)
273. {
274.                //declaration of variables
275.     int i;
276.     struct node * newNode, *temp;
277.               
278.                //if the list is empty
279.     if(head == NULL)
280.     {
281.         printf("\n Error! List is empty!\n");
282.     }
283.     else
284.     {
285.               
286.         temp = head;
287.         i=1;
288.  
289.         while(i<position-1 && temp!=NULL)
290.         {
291.             temp = temp->next;
292.             i++;
293.         }
294.  
295.                               //when the entered postion is 1
296.         if(position == 0 || position == 1)
297.         {
298.                //calling the dfunction to insert at the begining
299.             insertAtBeginning(data);
300.         }
301.         //the the position is nth
302.         else if(temp == end)
303.         {
304.                //calling the function tp insert at the end
305.             insertAtEnd(data);
306.         }
307.         else if(temp!=NULL)
308.         {
309.                //allocating the memory for the new node
310.             newNode = (struct node *)malloc(sizeof(struct node));
311.  
312.             newNode->data = data;
313.             newNode->next = temp->next; // Connect new node with n+1th node
314.             newNode->prev = temp;          // Connect new node with n-1th node
315.  
316.             if(temp->next != NULL)
317.             {
318.                 //Connect n+1th node with new node
319.                 temp->next->prev = newNode;
320.             }
321.             // Connect n-1th node with new node
322.             temp->next = newNode;
323.         }
324.         else
325.         {
326.                //If the positon is invalid
327.             printf("\n Error! Invalid position...Try again.\n");
328.         }
329.     }
330. }
331.  
332. //defining the function to delete the first node of the list
333. void DlListDeleteFirstNode()
334. {
335.                //creating a new node
336.     struct node * NodeToDel;
337.    
338.                //if the list is empty
339.                if(head == NULL)
340.     {
341.         printf("\n Delete is not possible.List is Empty.\n");
342.     }
343.     else
344.     {
345.         NodeToDel = head;
346.         head = head->next;   // move the next address of starting node to 2 node
347.         head->prev = NULL;      // set previous address of staring node is NULL
348.         free(NodeToDel);            // delete the first node from memory
349.     }
350. }
351.  
352. void DlListDeleteendNode()
353. {
354.     struct node * NodeToDel;
355.  
356.     if(end == NULL)
357.     {
358.         printf(" Delete is not possible.List is Empty.\n");
359.     }
360.     else
361.     {
362.         NodeToDel = end;
363.         end = end->prev;    // move the previous address of the end node to 2nd end node
364.         end->next = NULL;     // set the next address of end node to NULL
365.         free(NodeToDel);            // delete the end node
366.     }
367. }
368.  
369. //Function to delete a node at a particular position of the list
370. void DlListDeleteAnyNode(int pos)
371. {
372.                //declaring a new node-type pointer
373.     struct node *curNode;
374.     int i;
375.  
376.     curNode = head;
377.    
378.     //deleting the node
379.     for(i=1; i<pos && curNode!=NULL; i++)
380.     {
381.         curNode = curNode->next;
382.     }
383.  
384.     if(pos == 1)
385.     {
386.         DlListDeleteFirstNode();
387.     }
388.     else if(curNode == end)
389.     {
390.         DlListDeleteendNode();
391.     }
392.     else if(curNode != NULL)
393.     {
394.         curNode->prev->next= curNode->next;
395.         curNode->next->prev = curNode->prev;
396.  
397.         free(curNode); //Delete the n node
398.     }
399.     else
400.     {
401.         printf(" Invalid position!...Try again.\n");
402.     }
403. }

 

 

(End of Coding)

OUTPUT:

 

CREATE A DOUBLY LINKED LIST

--------------------------------------------

 

 Enter the total number of nodes: 3

 Enter data of first node: 1

 Enter data of next node: 12

 Enter data of next node: 123

 

........CREATION SUCCESSFUL........

 

 Data in the list:

----------------------

Data of 1 node = 1

Data of 2 node = 12

Data of 3 node = 123

 

         DOUBLY LINKED LIST PROGRAM

------------------------------------------------------

1. Insert node at beginning

2. Insert node at end

3. Insert node at a particular position

4. Delete the first node

5. Delete the last node

6. Delete the node at a particular position

7. Exit

----------------------------------------------------------

 Enter your choice : 1

 

 Enter data of first node : 12

 

 Data in the list:

----------------------

Data of 1 node = 12

Data of 2 node = 1

Data of 3 node = 12

Data of 4 node = 123

 

         DOUBLY LINKED LIST PROGRAM

------------------------------------------------------

1. Insert node at beginning

2. Insert node at end

3. Insert node at a particular position

4. Delete the first node

5. Delete the last node

6. Delete the node at a particular position

7. Exit

----------------------------------------------------------

 Enter your choice : 2

 

 Enter data of last node : 1234

 

 Data in the list:

----------------------

Data of 1 node = 12

Data of 2 node = 1

Data of 3 node = 12

Data of 4 node = 123

Data of 5 node = 1234

 

         DOUBLY LINKED LIST PROGRAM

------------------------------------------------------

1. Insert node at beginning

2. Insert node at end

3. Insert node at a particular position

4. Delete the first node

5. Delete the last node

6. Delete the node at a particular position

7. Exit

----------------------------------------------------------

 Enter your choice : 3

 

 Enter the position(0 to Totalnode+1) where you want to insert new node: 0

 

 Enter inserting data value: 123

 

 Data in the list:

----------------------

Data of 1 node = 123

Data of 2 node = 12

Data of 3 node = 1

Data of 4 node = 12

Data of 5 node = 123

Data of 6 node = 1234

 

         DOUBLY LINKED LIST PROGRAM

-------------------------------------------------------

1. Insert node at beginning

2. Insert node at end

3. Insert node at a particular position

4. Delete the first node

5. Delete the last node

6. Delete the node at a particular position

7. Exit

----------------------------------------------------------

 Enter your choice : 4

 

 Data in the list:

----------------------

Data of 1 node = 12

Data of 2 node = 1

Data of 3 node = 12

Data of 4 node = 123

Data of 5 node = 1234

 

         DOUBLY LINKED LIST PROGRAM

-------------------------------------------------------

1. Insert node at beginning

2. Insert node at end

3. Insert node at a particular position

4. Delete the first node

5. Delete the last node

6. Delete the node at a particular position

7. Exit

-----------------------------------------------------------------

 Enter your choice : 5

 

 Data in the list:

----------------------

Data of 1 node = 12

Data of 2 node = 1

Data of 3 node = 12

Data of 4 node = 123

 

         DOUBLY LINKED LIST PROGRAM

-------------------------------------------------------

1. Insert node at beginning

2. Insert node at end

3. Insert node at a particular position

4. Delete the first node

5. Delete the last node

6. Delete the node at a particular position

7. Exit

-----------------------------------------------------------

 Enter your choice : 6

 Enter the position(1 to Totalnode) to delete a node : 1

 

 Data in the list:

----------------------

Data of 1 node = 1

Data of 2 node = 12

Data of 3 node = 123

 

         DOUBLY LINKED LIST PROGRAM

------------------------------------------------------

1. Insert node at beginning

2. Insert node at end

3. Insert node at a particular position

4. Delete the first node

5. Delete the last node

6. Delete the node at a particular position

7. Exit

----------------------------------------------------------

 Enter your choice : 7

Stop program.Exit