UNIT- 3

Linked Lists

1. Define linked list and its uses

Linked List

• Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
• A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
• The last node of the list contains pointer to the null.

Uses of Linked List

• The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space.
• list size is limited to the memory size and doesn't need to be declared in advance.
• Empty node can not be present in the linked list.
• We can store values of primitive types or objects in the singly linked list.

Why use linked list over array?

Till now, we were using array data structure to organize the group of elements that are to be stored individually in the memory. However, Array has several advantages and disadvantages which must be known in order to decide the data structure which will be used throughout the program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program.
2. Increasing size of the array is a time taking process. It is almost impossible to expand the size of the array at run time.
3. All the elements in the array need to be contiguously stored in the memory. Inserting any element in the array needs shifting of all its predecessors.

Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful because,

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program's demand and limited to the available memory space.

2. Explain one way chain list and operations of linked list

Singly linked list or One way chain

Singly linked list can be defined as the collection of ordered set of elements. The number of elements may vary according to need of the program. A node in the singly linked list consist of two parts: data part and link part. Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor.

One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each node contains only next pointer, therefore we can not traverse the list in the reverse direction.

Consider an example where the marks obtained by the student in three subjects are stored in a linked list as shown in the figure.

In the above figure, the arrow represents the links. The data part of every node contains the marks obtained by the student in the different subject. The last node in the list is identified by the null pointer which is present in the address part of the last node. We can have as many elements we require, in the data part of the list.

Complexity

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such operations is given below.

Node Creation

1. struct node   
2. {  
3.     int data;   
4.     struct node *next;  
5. };  
6. struct node *head, *ptr;   
7. ptr = (struct node *)malloc(sizeof(struct node *));  

Insertion

The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories.

Deletion and Traversing

The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the operation is categorized into the following categories.

3.     Write Linked List in C: Menu Driven Program

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. struct node   
4. {  
5.     int data;  
6.     struct node *next;   
7. };  
8. struct node *head;  
9.   
10. void beginsert ();   
11. void lastinsert ();  
12. void randominsert();  
13. void begin_delete();  
14. void last_delete();  
15. void random_delete();  
16. void display();  
17. void search();  
18. void main ()  
19. {  
20.     int choice =0;  
21.     while(choice != 9)   
22.     {  
23.         printf("\n\n*********Main Menu*********\n");  
24.         printf("\nChoose one option from the following list ...\n");  
25.         printf("\n===============================================\n");  
26.         printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n  
27.         5.Delete from last\n6.Delete node after specified location\n7.Search for an element\n8.Show\n9.Exit\n");  
28.         printf("\nEnter your choice?\n");         
29.         scanf("\n%d",&choice);  
30.         switch(choice)  
31.         {  
32.             case 1:  
33.             beginsert();      
34.             break;  
35.             case 2:  
36.             lastinsert();         
37.             break;  
38.             case 3:  
39.             randominsert();       
40.             break;  
41.             case 4:  
42.             begin_delete();       
43.             break;  
44.             case 5:  
45.             last_delete();        
46.             break;  
47.             case 6:  
48.             random_delete();          
49.             break;  
50.             case 7:  
51.             search();         
52.             break;  
53.             case 8:  
54.             display();        
55.             break;  
56.             case 9:  
57.             exit(0);  
58.             break;  
59.             default:  
60.             printf("Please enter valid choice..");  
61.         }  
62.     }  
63. }  
64. void beginsert()  
65. {  
66.     struct node *ptr;  
67.     int item;  
68.     ptr = (struct node *) malloc(sizeof(struct node *));  
69.     if(ptr == NULL)  
70.     {  
71.         printf("\nOVERFLOW");  
72.     }  
73.     else  
74.     {  
75.         printf("\nEnter value\n");    
76.         scanf("%d",&item);    
77.         ptr->data = item;  
78.         ptr->next = head;  
79.         head = ptr;  
80.         printf("\nNode inserted");  
81.     }  
82.       
83. }  
84. void lastinsert()  
85. {  
86.     struct node *ptr,*temp;  
87.     int item;     
88.     ptr = (struct node*)malloc(sizeof(struct node));      
89.     if(ptr == NULL)  
90.     {  
91.         printf("\nOVERFLOW");     
92.     }  
93.     else  
94.     {  
95.         printf("\nEnter value?\n");  
96.         scanf("%d",&item);  
97.         ptr->data = item;  
98.         if(head == NULL)  
99.         {  
100.                               ptr -> next = NULL;  
101.                               head = ptr;  
102.                               printf("\nNode inserted");  
103.                           }  
104.                           else  
105.                           {  
106.                               temp = head;  
107.                               while (temp -> next != NULL)  
108.                               {  
109.                                   temp = temp -> next;  
110.                               }  
111.                               temp->next = ptr;  
112.                               ptr->next = NULL;  
113.                               printf("\nNode inserted");  
114.                             
115.                           }  
116.                       }  
117.                   }  
118.                   void randominsert()  
119.                   {  
120.                       int i,loc,item;   
121.                       struct node *ptr, *temp;  
122.                       ptr = (struct node *) malloc (sizeof(struct node));  
123.                       if(ptr == NULL)  
124.                       {  
125.                           printf("\nOVERFLOW");  
126.                       }  
127.                       else  
128.                       {  
129.                           printf("\nEnter element value");  
130.                           scanf("%d",&item);  
131.                           ptr->data = item;  
132.                           printf("\nEnter the location after which you want to insert ");  
133.                           scanf("\n%d",&loc);  
134.                           temp=head;  
135.                           for(i=0;i<loc;i++)  
136.                           {  
137.                               temp = temp->next;  
138.                               if(temp == NULL)  
139.                               {  
140.                                   printf("\ncan't insert\n");  
141.                                   return;  
142.                               }  
143.                             
144.                           }  
145.                           ptr ->next = temp ->next;   
146.                           temp ->next = ptr;   
147.                           printf("\nNode inserted");  
148.                       }  
149.                   }  
150.                   void begin_delete()  
151.                   {  
152.                       struct node *ptr;  
153.                       if(head == NULL)  
154.                       {  
155.                           printf("\nList is empty\n");  
156.                       }  
157.                       else   
158.                       {  
159.                           ptr = head;  
160.                           head = ptr->next;  
161.                           free(ptr);  
162.                           printf("\nNode deleted from the begining ...\n");  
163.                       }  
164.                   }  
165.                   void last_delete()  
166.                   {  
167.                       struct node *ptr,*ptr1;  
168.                       if(head == NULL)  
169.                       {  
170.                           printf("\nlist is empty");  
171.                       }  
172.                       else if(head -> next == NULL)  
173.                       {  
174.                           head = NULL;  
175.                           free(head);  
176.                           printf("\nOnly node of the list deleted ...\n");  
177.                       }  
178.                             
179.                       else  
180.                       {  
181.                           ptr = head;   
182.                           while(ptr->next != NULL)  
183.                           {  
184.                               ptr1 = ptr;  
185.                               ptr = ptr ->next;  
186.                           }  
187.                           ptr1->next = NULL;  
188.                           free(ptr);  
189.                           printf("\nDeleted Node from the last ...\n");  
190.                       }     
191.                   }  
192.                   void random_delete()  
193.                   {  
194.                       struct node *ptr,*ptr1;  
195.                       int loc,i;    
196.                       printf("\n Enter the location of the node after which you want to perform deletion \n");  
197.                       scanf("%d",&loc);  
198.                       ptr=head;  
199.                       for(i=0;i<loc;i++)  
200.                       {  
201.                           ptr1 = ptr;       
202.                           ptr = ptr->next;  
203.                                 
204.                           if(ptr == NULL)  
205.                           {  
206.                               printf("\nCan't delete");  
207.                               return;  
208.                           }  
209.                       }  
210.                       ptr1 ->next = ptr ->next;  
211.                       free(ptr);  
212.                       printf("\nDeleted node %d ",loc+1);  
213.                   }  
214.                   void search()  
215.                   {  
216.                       struct node *ptr;  
217.                       int item,i=0,flag;  
218.                       ptr = head;   
219.                       if(ptr == NULL)  
220.                       {  
221.                           printf("\nEmpty List\n");  
222.                       }  
223.                       else  
224.                       {   
225.                           printf("\nEnter item which you want to search?\n");   
226.                           scanf("%d",&item);  
227.                           while (ptr!=NULL)  
228.                           {  
229.                               if(ptr->data == item)  
230.                               {  
231.                                   printf("item found at location %d ",i+1);  
232.                                   flag=0;  
233.                               }   
234.                               else  
235.                               {  
236.                                   flag=1;  
237.                               }  
238.                               i++;  
239.                               ptr = ptr -> next;  
240.                           }  
241.                           if(flag==1)  
242.                           {  
243.                               printf("Item not found\n");  
244.                           }  
245.                       }     
246.                             
247.                   }  
248.                     
249.                   void display()  
250.                   {  
251.                       struct node *ptr;  
252.                       ptr = head;   
253.                       if(ptr == NULL)  
254.                       {  
255.                           printf("Nothing to print");  
256.                       }  
257.                       else  
258.                       {  
259.                           printf("\nprinting values . . . . .\n");   
260.                           while (ptr!=NULL)  
261.                           {  
262.                               printf("\n%d",ptr->data);  
263.                               ptr = ptr -> next;  
264.                           }  
265.                       }  
266.                   }     
267.                                 

Output:

   *********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

1

Enter value

1

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

2

Enter value?

2

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

3

Enter element value1

Enter the location after which you want to insert 1

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

8

printing values . . . . .

1

2

1

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

2

Enter value?

123

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

1

Enter value

1234

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

4

Node deleted from the begining ...

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

5

Deleted Node from the last ...

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

6

Enter the location of the node after which you want to perform deletion

1

Deleted node 2

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

8

printing values . . . . .

1

1

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

7

Enter item which you want to search?

1

item found at location 1

item found at location 2

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining

2.Insert at last

3.Insert at any random location

4.Delete from Beginning

5.Delete from last

6.Delete node after specified location

7.Search for an element

8.Show

9.Exit

Enter your choice?

9

4.     Explain Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.

• Linked List contains a link element called first.
• Each link carries a data field(s) and a link field called next.
• Each link is linked with its next link using its next link.
• Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.

• Simple Linked List − Item navigation is forward only.
• Doubly Linked List − Items can be navigated forward and backward.
• Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations

Following are the basic operations supported by a list.

• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.

Insertion Operation

Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.

Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −

NewNode.next −> RightNode;

It should look like this −

Now, the next node at the left should point to the new node.

LeftNode.next −> NewNode;

This will put the new node in the middle of the two. The new list should look like this −

Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

Deletion Operation

Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target node −

LeftNode.next −> TargetNode.next;

This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.

TargetNode.next −> NULL;

We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.

Reverse Operation

This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.

First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −

We have to make sure that the last node is not the last node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.

We'll make the head node point to the new first node by using the temp node.

The linked list is now reversed.

A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.

5.     Write a program for Implementation of linked list representation in C

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

struct node {

   int data;

   int key;

   struct node *next;

};

struct node *head = NULL;

struct node *current = NULL;

//display the list

void printList() {

   struct node *ptr = head;

   printf("\n[ ");

   //start from the beginning

   while(ptr != NULL) {

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

      ptr = ptr->next;

   }

   printf(" ]");

}

//insert link at the first location

void insertFirst(int key, int data) {

   //create a link

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

   link->key = key;

   link->data = data;

   //point it to old first node

   link->next = head;

   //point first to new first node

   head = link;

}

//delete first item

struct node* deleteFirst() {

   //save reference to first link

   struct node *tempLink = head;

   //mark next to first link as first

   head = head->next;

   //return the deleted link

   return tempLink;

}

//is list empty

bool isEmpty() {

   return head == NULL;

}

int length() {

   int length = 0;

   struct node *current;

   for(current = head; current != NULL; current = current->next) {

      length++;

   }

   return length;

}

//find a link with given key

struct node* find(int key) {

   //start from the first link

   struct node* current = head;

   //if list is empty

   if(head == NULL) {

      return NULL;

   }

   //navigate through list

   while(current->key != key) {

      //if it is last node

      if(current->next == NULL) {

         return NULL;

      } else {

         //go to next link

         current = current->next;

      }

   }     

   //if data found, return the current Link

   return current;

}

//delete a link with given key

struct node* delete(int key) {

   //start from the first link

   struct node* current = head;

   struct node* previous = NULL;

   //if list is empty

   if(head == NULL) {

      return NULL;

   }

   //navigate through list

   while(current->key != key) {

      //if it is last node

      if(current->next == NULL) {

         return NULL;

      } else {

         //store reference to current link

         previous = current;

         //move to next link

         current = current->next;

      }

   }

   //found a match, update the link

   if(current == head) {

      //change first to point to next link

      head = head->next;

   } else {

      //bypass the current link

      previous->next = current->next;

   }   

   return current;

}

void sort() {

   int i, j, k, tempKey, tempData;

   struct node *current;

   struct node *next;

   int size = length();

   k = size ;

   for ( i = 0 ; i < size - 1 ; i++, k-- ) {

      current = head;

      next = head->next;

      for ( j = 1 ; j < k ; j++ ) {  

         if ( current->data > next->data ) {

            tempData = current->data;

            current->data = next->data;

            next->data = tempData;

            tempKey = current->key;

            current->key = next->key;

            next->key = tempKey;

         }

         current = current->next;

         next = next->next;

      }

   }  

}

void reverse(struct node** head_ref) {

   struct node* prev   = NULL;

   struct node* current = *head_ref;

   struct node* next;

   while (current != NULL) {

      next  = current->next;

      current->next = prev;  

      prev = current;

      current = next;

   }

   *head_ref = prev;

}

void main() {

   insertFirst(1,10);

   insertFirst(2,20);

   insertFirst(3,30);

   insertFirst(4,1);

   insertFirst(5,40);

   insertFirst(6,56);

   printf("Original List: ");

   //print list

   printList();

   while(!isEmpty()) {           

      struct node *temp = deleteFirst();

      printf("\nDeleted value:");

      printf("(%d,%d) ",temp->key,temp->data);

   } 

   printf("\nList after deleting all items: ");

   printList();

   insertFirst(1,10);

   insertFirst(2,20);

   insertFirst(3,30);

   insertFirst(4,1);

   insertFirst(5,40);

   insertFirst(6,56);

   printf("\nRestored List: ");

   printList();

   printf("\n"); 

   struct node *foundLink = find(4);

   if(foundLink != NULL) {

      printf("Element found: ");

      printf("(%d,%d) ",foundLink->key,foundLink->data);

      printf("\n"); 

   } else {

      printf("Element not found.");

   }

   delete(4);

   printf("List after deleting an item: ");

   printList();

   printf("\n");

   foundLink = find(4);

   if(foundLink != NULL) {

      printf("Element found: ");

      printf("(%d,%d) ",foundLink->key,foundLink->data);

      printf("\n");

   } else {

      printf("Element not found.");

   }

   printf("\n");

   sort();

   printf("List after sorting the data: ");

   printList();

   reverse(&head);

   printf("\nList after reversing the data: ");

   printList();

}

If we compile and run the above program, it will produce the following result −

Output

Original List:

[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]

Deleted value:(6,56)

Deleted value:(5,40)

Deleted value:(4,1)

Deleted value:(3,30)

Deleted value:(2,20)

Deleted value:(1,10)

List after deleting all items:

[ ]

Restored List:

[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]

Element found: (4,1)

List after deleting an item:

[ (6,56) (5,40) (3,30) (2,20) (1,10) ]

Element not found.

List after sorting the data:

[ (1,10) (2,20) (3,30) (5,40) (6,56) ]

List after reversing the data:

[ (6,56) (5,40) (3,30) (2,20) (1,10) ]

6.     Explain Doubly linked list in detail with c program

Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer). A sample node in a doubly linked list is shown in the figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the following image.

In C, structure of a node in doubly linked list can be given as :

1. struct node   
2. {  
3.     struct node *prev;   
4.     int data;  
5.     struct node *next;   
6. }   

The prev part of the first node and the next part of the last node will always contain null indicating end in each direction.

In a singly linked list, we could traverse only in one direction, because each node contains address of the next node and it doesn't have any record of its previous nodes. However, doubly linked list overcome this limitation of singly linked list. Due to the fact that, each node of the list contains the address of its previous node, we can find all the details about the previous node as well by using the previous address stored inside the previous part of each node.

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in the following image. Generally, doubly linked list consumes more space for every node and therefore, causes more expansive basic operations such as insertion and deletion. However, we can easily manipulate the elements of the list since the list maintains pointers in both the directions (forward and backward).

In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer points to the starting address 1. Since this is the first element being added to the list therefore the prev of the list contains null. The next node of the list resides at address 4 therefore the first node contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing null or -1 in its next part.

Operations on doubly linked list

Node Creation

1. struct node   
2. {  
3.     struct node *prev;  
4.     int data;  
5.     struct node *next;  
6. };  
7. struct node *head;   

All the remaining operations regarding doubly linked list are described in the following table.

Menu Driven Program in C to implement all the operations of doubly linked list

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. struct node  
4. {  
5.     struct node *prev;  
6.     struct node *next;  
7.     int data;  
8. };  
9. struct node *head;  
10. void insertion_beginning();  
11. void insertion_last();  
12. void insertion_specified();  
13. void deletion_beginning();  
14. void deletion_last();  
15. void deletion_specified();  
16. void display();  
17. void search();  
18. void main ()  
19. {  
20. int choice =0;  
21.     while(choice != 9)  
22.     {  
23.         printf("\n*********Main Menu*********\n");  
24.         printf("\nChoose one option from the following list ...\n");  
25.         printf("\n===============================================\n");  
26.         printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n  
27.         5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");  
28.         printf("\nEnter your choice?\n");  
29.         scanf("\n%d",&choice);  
30.         switch(choice)  
31.         {  
32.             case 1:  
33.             insertion_beginning();  
34.             break;  
35.             case 2:  
36.                     insertion_last();  
37.             break;  
38.             case 3:  
39.             insertion_specified();  
40.             break;  
41.             case 4:  
42.             deletion_beginning();  
43.             break;  
44.             case 5:  
45.             deletion_last();  
46.             break;  
47.             case 6:  
48.             deletion_specified();  
49.             break;  
50.             case 7:  
51.             search();  
52.             break;  
53.             case 8:  
54.             display();  
55.             break;  
56.             case 9:  
57.             exit(0);  
58.             break;  
59.             default:  
60.             printf("Please enter valid choice..");  
61.         }  
62.     }  
63. }  
64. void insertion_beginning()  
65. {  
66.    struct node *ptr;   
67.    int item;  
68.    ptr = (struct node *)malloc(sizeof(struct node));  
69.    if(ptr == NULL)  
70.    {  
71.        printf("\nOVERFLOW");  
72.    }  
73.    else  
74.    {  
75.     printf("\nEnter Item value");  
76.     scanf("%d",&item);  
77.       
78.    if(head==NULL)  
79.    {  
80.        ptr->next = NULL;  
81.        ptr->prev=NULL;  
82.        ptr->data=item;  
83.        head=ptr;  
84.    }  
85.    else   
86.    {  
87.        ptr->data=item;  
88.        ptr->prev=NULL;  
89.        ptr->next = head;  
90.        head->prev=ptr;  
91.        head=ptr;  
92.    }  
93.    printf("\nNode inserted\n");  
94. }  
95.      
96. }  
97. void insertion_last()  
98. {  
99.    struct node *ptr,*temp;  
100.                      int item;  
101.                      ptr = (struct node *) malloc(sizeof(struct node));  
102.                      if(ptr == NULL)  
103.                      {  
104.                          printf("\nOVERFLOW");  
105.                      }  
106.                      else  
107.                      {  
108.                          printf("\nEnter value");  
109.                          scanf("%d",&item);  
110.                           ptr->data=item;  
111.                          if(head == NULL)  
112.                          {  
113.                              ptr->next = NULL;  
114.                              ptr->prev = NULL;  
115.                              head = ptr;  
116.                          }  
117.                          else  
118.                          {  
119.                             temp = head;  
120.                             while(temp->next!=NULL)  
121.                             {  
122.                                 temp = temp->next;  
123.                             }  
124.                             temp->next = ptr;  
125.                             ptr ->prev=temp;  
126.                             ptr->next = NULL;  
127.                             }  
128.                                
129.                          }  
130.                        printf("\nnode inserted\n");  
131.                       }  
132.                   void insertion_specified()  
133.                   {  
134.                      struct node *ptr,*temp;  
135.                      int item,loc,i;  
136.                      ptr = (struct node *)malloc(sizeof(struct node));  
137.                      if(ptr == NULL)  
138.                      {  
139.                          printf("\n OVERFLOW");  
140.                      }  
141.                      else  
142.                      {  
143.                          temp=head;  
144.                          printf("Enter the location");  
145.                          scanf("%d",&loc);  
146.                          for(i=0;i<loc;i++)  
147.                          {  
148.                              temp = temp->next;  
149.                              if(temp == NULL)  
150.                              {  
151.                                  printf("\n There are less than %d elements", loc);  
152.                                  return;  
153.                              }  
154.                          }  
155.                          printf("Enter value");  
156.                          scanf("%d",&item);  
157.                          ptr->data = item;  
158.                          ptr->next = temp->next;  
159.                          ptr -> prev = temp;  
160.                          temp->next = ptr;  
161.                          temp->next->prev=ptr;  
162.                          printf("\nnode inserted\n");  
163.                      }  
164.                   }  
165.                   void deletion_beginning()  
166.                   {  
167.                       struct node *ptr;  
168.                       if(head == NULL)  
169.                       {  
170.                           printf("\n UNDERFLOW");  
171.                       }  
172.                       else if(head->next == NULL)  
173.                       {  
174.                           head = NULL;   
175.                           free(head);  
176.                           printf("\nnode deleted\n");  
177.                       }  
178.                       else  
179.                       {  
180.                           ptr = head;  
181.                           head = head -> next;  
182.                           head -> prev = NULL;  
183.                           free(ptr);  
184.                           printf("\nnode deleted\n");  
185.                       }  
186.                     
187.                   }  
188.                   void deletion_last()  
189.                   {  
190.                       struct node *ptr;  
191.                       if(head == NULL)  
192.                       {  
193.                           printf("\n UNDERFLOW");  
194.                       }  
195.                       else if(head->next == NULL)  
196.                       {  
197.                           head = NULL;   
198.                           free(head);   
199.                           printf("\nnode deleted\n");  
200.                       }  
201.                       else   
202.                       {  
203.                           ptr = head;   
204.                           if(ptr->next != NULL)  
205.                           {  
206.                               ptr = ptr -> next;   
207.                           }  
208.                           ptr -> prev -> next = NULL;   
209.                           free(ptr);  
210.                           printf("\nnode deleted\n");  
211.                       }  
212.                   }  
213.                   void deletion_specified()  
214.                   {  
215.                       struct node *ptr, *temp;  
216.                       int val;  
217.                       printf("\n Enter the data after which the node is to be deleted : ");  
218.                       scanf("%d", &val);  
219.                       ptr = head;  
220.                       while(ptr -> data != val)  
221.                       ptr = ptr -> next;  
222.                       if(ptr -> next == NULL)  
223.                       {  
224.                           printf("\nCan't delete\n");  
225.                       }  
226.                       else if(ptr -> next -> next == NULL)  
227.                       {  
228.                           ptr ->next = NULL;  
229.                       }  
230.                       else  
231.                       {   
232.                           temp = ptr -> next;  
233.                           ptr -> next = temp -> next;  
234.                           temp -> next -> prev = ptr;  
235.                           free(temp);  
236.                           printf("\nnode deleted\n");  
237.                       }     
238.                   }  
239.                   void display()  
240.                   {  
241.                       struct node *ptr;  
242.                       printf("\n printing values...\n");  
243.                       ptr = head;  
244.                       while(ptr != NULL)  
245.                       {  
246.                           printf("%d\n",ptr->data);  
247.                           ptr=ptr->next;  
248.                       }  
249.                   }   
250.                   void search()  
251.                   {  
252.                       struct node *ptr;  
253.                       int item,i=0,flag;  
254.                       ptr = head;   
255.                       if(ptr == NULL)  
256.                       {  
257.                           printf("\nEmpty List\n");  
258.                       }  
259.                       else  
260.                       {   
261.                           printf("\nEnter item which you want to search?\n");   
262.                           scanf("%d",&item);  
263.                           while (ptr!=NULL)  
264.                           {  
265.                               if(ptr->data == item)  
266.                               {  
267.                                   printf("\nitem found at location %d ",i+1);  
268.                                   flag=0;  
269.                                   break;  
270.                               }   
271.                               else  
272.                               {  
273.                                   flag=1;  
274.                               }  
275.                               i++;  
276.                               ptr = ptr -> next;  
277.                           }  
278.                           if(flag==1)  
279.                           {  
280.                               printf("\nItem not found\n");  
281.                           }  
282.                       }     
283.                             
284.                   }