Singly Linked Lists

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.

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

Data Structure	Time Complexity								Space Compleity
	Average				Worst				Worst
	Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion
Singly Linked List	θ(n)	θ(n)	θ(1)	θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)

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.

SN	Operation	Description
1	Insertion at beginning	It involves inserting any element at the front of the list. We just need to a few link adjustments to make the new node as the head of the list.
2	Insertion at end of the list	It involves insertion at the last of the linked list. The new node can be inserted as the only node in the list or it can be inserted as the last one. Different logics are implemented in each scenario.
3	Insertion after specified node	It involves insertion after the specified node of the linked list. We need to skip the desired number of nodes in order to reach the node after which the new node will be inserted. .

Insertion in singly linked list at beginning

Inserting a new element into a singly linked list at beginning is quite simple. We just need to make a few adjustments in the node links. There are the following steps which need to be followed in order to inser a new node in the list at beginning.

• Allocate the space for the new node and store data into the data part of the node. This will be done by the following statements.

1. ptr = (struct node *) malloc(sizeof(struct node *));  
2.             ptr → data = item   

• Make the link part of the new node pointing to the existing first node of the list. This will be done by using the following statement.

1. ptr->next = head;  

• At the last, we need to make the new node as the first node of the list this will be done by using the following statement.

1. head = ptr;  

Algorithm

• Step 1: IF PTR = NULL

Write OVERFLOW
     Go to Step 7
    [END OF IF]

• Step 2: SET NEW_NODE = PTR
• Step 3: SET PTR = PTR → NEXT
• Step 4: SET NEW_NODE → DATA = VAL
• Step 5: SET NEW_NODE → NEXT = HEAD
• Step 6: SET HEAD = NEW_NODE
• Step 7: EXIT

C Function

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. void beginsert(int);  
4. struct node  
5. {  
6.     int data;  
7.     struct node *next;  
8. };  
9. struct node *head;  
10. void main ()  
11. {  
12.     int choice,item;  
13.     do   
14.     {  
15.         printf("\nEnter the item which you want to insert?\n");  
16.         scanf("%d",&item);  
17.         beginsert(item);  
18.         printf("\nPress 0 to insert more ?\n");  
19.         scanf("%d",&choice);  
20.     }while(choice == 0);  
21. }  
22. void beginsert(int item)  
23.     {  
24.         struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
25.         if(ptr == NULL)  
26.         {  
27.             printf("\nOVERFLOW\n");  
28.         }  
29.         else  
30.         {  
31.             ptr->data = item;  
32.             ptr->next = head;  
33.             head = ptr;  
34.             printf("\nNode inserted\n");  
35.         }  
36.           
37.     }  

Output

Enter the item which you want to insert?
12

Node inserted

Press 0 to insert more ?
0

Enter the item which you want to insert?
23

Node inserted

Press 0 to insert more ?
2

Insertion in singly linked list at the end

In order to insert a node at the last, there are two following scenarios which need to be mentioned.
The node is being added to an empty list
The node is being added to the end of the linked list

in the first case,

The condition (head == NULL) gets satisfied. Hence, we just need to allocate the space for the node by using malloc statement in C. Data and the link part of the node are set up by using the following statements.
ptr->data = item;  
                ptr -> next = NULL;  
Since, ptr is the only node that will be inserted in the list hence, we need to make this node pointed by the head pointer of the list. This will be done by using the following Statements.
Head = ptr     

In the second case,

The condition Head = NULL would fail, since Head is not null. Now, we need to declare a temporary pointer temp in order to traverse through the list. temp is made to point the first node of the list.
Temp = head   
Then, traverse through the entire linked list using the statements:
while (temp→ next != NULL)  
            temp = temp → next;  
At the end of the loop, the temp will be pointing to the last node of the list. Now, allocate the space for the new node, and assign the item to its data part. Since, the new node is going to be the last node of the list hence, the next part of this node needs to be pointing to the null. We need to make the next part of the temp node (which is currently the last node of the list) point to the new node (ptr) .
temp = head;  
        while (temp -> next != NULL)  
        {  
            temp = temp -> next;  
        }  
        temp->next = ptr;  
        ptr->next = NULL;  

Algorithm

Step 1: IF PTR = NULL Write OVERFLOW
    Go to Step 1
   [END OF IF]
Step 2: SET NEW_NODE = PTR
Step 3: SET PTR = PTR - > NEXT
Step 4: SET NEW_NODE - > DATA = VAL
Step 5: SET NEW_NODE - > NEXT = NULL
Step 6: SET PTR = HEAD
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: EXIT

C Function

#include<stdio.h>  
#include<stdlib.h>  
void lastinsert(int);  
struct node  
{  
    int data;  
    struct node *next;  
};  
struct node *head;  
void main ()  
{  
    int choice,item;  
    do   
    {  
        printf("\nEnter the item which you want to insert?\n");  
        scanf("%d",&item);  
        lastinsert(item);  
        printf("\nPress 0 to insert more ?\n");  
        scanf("%d",&choice);  
    }while(choice == 0);  
}  
void lastinsert(int item)  
    {  
        struct node *ptr = (struct node*)malloc(sizeof(struct node));     
        struct node *temp;  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW");     
        }  
        else  
        {  
            ptr->data = item;  
            if(head == NULL)  
            {  
                ptr -> next = NULL;  
                head = ptr;  
                printf("\nNode inserted");  
            }  
            else  
            {  
                temp = head;  
                while (temp -> next != NULL)  
                {  
                    temp = temp -> next;  
                }  
                temp->next = ptr;  
                ptr->next = NULL;  
                printf("\nNode inserted");  
              
            }  
        }  
    }  
Output
Enter the item which you want to insert?
12

Node inserted
Press 0 to insert more ?
0

Enter the item which you want to insert?
23

Node inserted
Press 0 to insert more ?
2

Insertion in singly linked list after specified Node

In order to insert an element after the specified number of nodes into the linked list, we need to skip the desired number of elements in the list to move the pointer at the position after which the node will be inserted. This will be done by using the following statements.
emp=head;  
            for(i=0;i<loc;i++)  
            {  
                temp = temp->next;  
                if(temp == NULL)  
                {  
                    return;  
                }  
              
            }  
Allocate the space for the new node and add the item to the data part of it. This will be done by using the following statements.
ptr = (struct node *) malloc (sizeof(struct node));  
        ptr->data = item;  
Now, we just need to make a few more link adjustments and our node at will be inserted at the specified position. Since, at the end of the loop, the loop pointer temp would be pointing to the node after which the new node will be inserted. Therefore, the next part of the new node ptr must contain the address of the next part of the temp (since, ptr will be in between temp and the next of the temp). This will be done by using the following statements.
ptr→ next = temp → next   
now, we just need to make the next part of the temp, point to the new node ptr. This will insert the new node ptr, at the specified position.
temp ->next = ptr;   

Algorithm

STEP 1: IF PTR = NULL
WRITE OVERFLOW
    GOTO STEP 12
   END OF IF
STEP 2: SET NEW_NODE = PTR
STEP 3: NEW_NODE → DATA = VAL
STEP 4: SET TEMP = HEAD
STEP 5: SET I = 0
STEP 6: REPEAT STEP 5 AND 6 UNTIL I
STEP 7: TEMP = TEMP → NEXT
STEP 8: IF TEMP = NULL
WRITE "DESIRED NODE NOT PRESENT"
     GOTO STEP 12
    END OF IF
 END OF LOOP
STEP 9: PTR → NEXT = TEMP → NEXT
STEP 10: TEMP → NEXT = PTR
STEP 11: SET PTR = NEW_NODE
STEP 12: EXIT

C Function

#include<stdio.h>  
#include<stdlib.h>  
void randominsert(int);  
void create(int);  
struct node  
{  
    int data;  
    struct node *next;  
};  
struct node *head;  
void main ()  
{  
    int choice,item,loc;  
    do   
    {  
        printf("\nEnter the item which you want to insert?\n");  
        scanf("%d",&item);  
        if(head == NULL)  
        {  
            create(item);  
        }  
        else  
        {  
            randominsert(item);  
        }  
        printf("\nPress 0 to insert more ?\n");  
        scanf("%d",&choice);  
    }while(choice == 0);  
}  
void create(int item)  
{  
      
        struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW\n");  
        }  
        else  
        {  
            ptr->data = item;  
            ptr->next = head;  
            head = ptr;  
            printf("\nNode inserted\n");  
        }  
}  
void randominsert(int item)  
    {  
        struct node *ptr = (struct node *) malloc (sizeof(struct node));  
        struct node *temp;  
        int i,loc;  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW");  
        }  
        else  
        {  
              
            printf("Enter the location");  
            scanf("%d",&loc);             
            ptr->data = item;  
            temp=head;  
            for(i=0;i<loc;i++)  
            {  
                temp = temp->next;  
                if(temp == NULL)  
                {  
                    printf("\ncan't insert\n");  
                    return;  
                }  
              
            }  
            ptr ->next = temp ->next;   
            temp ->next = ptr;   
            printf("\nNode inserted");  
        }  
          
    }  

Output

Enter the item which you want to insert?
12

Node inserted

Press 0 to insert more ?
2

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.

SN	Operation	Description
1	Deletion at beginning	It involves deletion of a node from the beginning of the list. This is the simplest operation among all. It just need a few adjustments in the node pointers.
2	Deletion at the end of the list	It involves deleting the last node of the list. The list can either be empty or full. Different logic is implemented for the different scenarios.
3	Deletion after specified node	It involves deleting the node after the specified node in the list. we need to skip the desired number of nodes to reach the node after which the node will be deleted. This requires traversing through the list.
4	Traversing	In traversing, we simply visit each node of the list at least once in order to perform some specific operation on it, for example, printing data part of each node present in the list.
5	Searching	In searching, we match each element of the list with the given element. If the element is found on any of the location then location of that element is returned otherwise null is returned. .

Deletion in singly linked list at beginning

Deleting a node from the beginning of the list is the simplest operation of all. It just need a few adjustments in the node pointers. Since the first node of the list is to be deleted, therefore, we just need to make the head, point to the next of the head. This will be done by using the following statements.

1. ptr = head;  
2.             head = ptr->next;  

Now, free the pointer ptr which was pointing to the head node of the list. This will be done by using the following statement.

1. free(ptr)  

Algorithm

• Step 1: IF HEAD = NULL

Write UNDERFLOW
     Go to Step 5
    [END OF IF]

• Step 2: SET PTR = HEAD
• Step 3: SET HEAD = HEAD -> NEXT
• Step 4: FREE PTR
• Step 5: EXIT

C function

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. void create(int);  
4. void begdelete();  
5. struct node  
6. {  
7.     int data;  
8.     struct node *next;  
9. };  
10. struct node *head;  
11. void main ()  
12. {  
13.     int choice,item;  
14.     do   
15.     {  
16.         printf("\n1.Append List\n2.Delete node\n3.Exit\n4.Enter your choice?");  
17.         scanf("%d",&choice);  
18.         switch(choice)  
19.         {  
20.             case 1:  
21.             printf("\nEnter the item\n");  
22.             scanf("%d",&item);  
23.             create(item);  
24.             break;   
25.             case 2:  
26.             begdelete();  
27.             break;   
28.             case 3:  
29.             exit(0);  
30.             break;    
31.             default:  
32.             printf("\nPlease enter valid choice\n");  
33.         }  
34.                   
35.     }while(choice != 3);  
36. }  
37. void create(int item)  
38.     {  
39.         struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
40.         if(ptr == NULL)  
41.         {  
42.             printf("\nOVERFLOW\n");  
43.         }  
44.         else  
45.         {  
46.             ptr->data = item;  
47.             ptr->next = head;  
48.             head = ptr;  
49.             printf("\nNode inserted\n");  
50.         }  
51.           
52.     }  
53. void begdelete()  
54.     {  
55.         struct node *ptr;  
56.         if(head == NULL)  
57.         {  
58.             printf("\nList is empty");  
59.         }  
60.         else   
61.         {  
62.             ptr = head;  
63.             head = ptr->next;  
64.             free(ptr);  
65.             printf("\n Node deleted from the begining ...");  
66.         }  
67.     }  

Output

1.Append List
2.Delete node
3.Exit
4.Enter your choice?1

Enter the item
23

Node inserted

1.Append List
2.Delete node
3.Exit
4.Enter your choice?2

 Node deleted from the begining ...

Deletion in singly linked list at the end

There are two scenarios in which, a node is deleted from the end of the linked list.

1. There is only one node in the list and that needs to be deleted.
2. There are more than one node in the list and the last node of the list will be deleted.

In the first scenario,

the condition head → next = NULL will survive and therefore, the only node head of the list will be assigned to null. This will be done by using the following statements.

1. ptr = head  
2.         head = NULL  
3.         free(ptr)  

In the second scenario,

The condition head → next = NULL would fail and therefore, we have to traverse the node in order to reach the last node of the list.

For this purpose, just declare a temporary pointer temp and assign it to head of the list. We also need to keep track of the second last node of the list. For this purpose, two pointers ptr and ptr1 will be used where ptr will point to the last node and ptr1 will point to the second last node of the list.

this all will be done by using the following statements.

1. ptr = head;   
2.                 while(ptr->next != NULL)  
3.                 {  
4.                     ptr1 = ptr;  
5.                     ptr = ptr ->next;  
6.                 }  

Now, we just need to make the pointer ptr1 point to the NULL and the last node of the list that is pointed by ptr will become free. It will be done by using the following statements.

1. ptr1->next = NULL;  
2.                 free(ptr);  

Algorithm

• Step 1: IF HEAD = NULL

Write UNDERFLOW
   Go to Step 8
  [END OF IF]

• Step 2: SET PTR = HEAD
• Step 3: Repeat Steps 4 and 5 while PTR -> NEXT!= NULL
• Step 4: SET PREPTR = PTR
• Step 5: SET PTR = PTR -> NEXT

[END OF LOOP]

• Step 6: SET PREPTR -> NEXT = NULL
• Step 7: FREE PTR
• Step 8: EXIT

C Function :

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. void create(int);  
4. void end_delete();  
5. struct node  
6. {  
7.     int data;  
8.     struct node *next;  
9. };  
10. struct node *head;  
11. void main ()  
12. {  
13.     int choice,item;  
14.     do   
15.     {  
16.         printf("\n1.Append List\n2.Delete node\n3.Exit\n4.Enter your choice?");  
17.         scanf("%d",&choice);  
18.         switch(choice)  
19.         {  
20.             case 1:  
21.             printf("\nEnter the item\n");  
22.             scanf("%d",&item);  
23.             create(item);  
24.             break;   
25.             case 2:  
26.             end_delete();  
27.             break;   
28.             case 3:  
29.             exit(0);  
30.             break;    
31.             default:  
32.             printf("\nPlease enter valid choice\n");  
33.         }  
34.                   
35.     }while(choice != 3);  
36. }  
37. void create(int item)  
38.     {  
39.         struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
40.         if(ptr == NULL)  
41.         {  
42.             printf("\nOVERFLOW\n");  
43.         }  
44.         else  
45.         {  
46.             ptr->data = item;  
47.             ptr->next = head;  
48.             head = ptr;  
49.             printf("\nNode inserted\n");  
50.         }  
51.           
52.     }  
53. void end_delete()  
54.     {  
55.         struct node *ptr,*ptr1;  
56.         if(head == NULL)  
57.         {  
58.             printf("\nlist is empty");  
59.         }  
60.         else if(head -> next == NULL)  
61.         {  
62.             head = NULL;  
63.             free(head);  
64.             printf("\nOnly node of the list deleted ...");  
65.         }  
66.               
67.         else  
68.         {  
69.             ptr = head;   
70.             while(ptr->next != NULL)  
71.                 {  
72.                     ptr1 = ptr;  
73.                     ptr = ptr ->next;  
74.                 }  
75.                 ptr1->next = NULL;  
76.                 free(ptr);  
77.                 printf("\n Deleted Node from the last ...");  
78.             }     
79.         }  

Output

1.Append List
2.Delete node
3.Exit
4.Enter your choice?1

Enter the item
12

Node inserted

1.Append List
2.Delete node
3.Exit
4.Enter your choice?2

Only node of the list deleted ...

Deletion in singly linked list after the specified node :

In order to delete the node, which is present after the specified node, we need to skip the desired number of nodes to reach the node after which the node will be deleted. We need to keep track of the two nodes. The one which is to be deleted the other one if the node which is present before that node. For this purpose, two pointers are used: ptr and ptr1.

Use the following statements to do so.

1. ptr=head;  
2.         for(i=0;i<loc;i++)  
3.         {  
4.             ptr1 = ptr;       
5.             ptr = ptr->next;  
6.               
7.             if(ptr == NULL)  
8.             {  
9.                 printf("\nThere are less than %d elements in the list..",loc);  
10.                 return;  
11.             }  
12.         }  

Now, our task is almost done, we just need to make a few pointer adjustments. Make the next of ptr1 (points to the specified node) point to the next of ptr (the node which is to be deleted).

This will be done by using the following statements.

1. ptr1 ->next = ptr ->next;  
2.         free(ptr);  

Algorithm

• STEP 1: IF HEAD = NULL

WRITE UNDERFLOW
    GOTO STEP 10
   END OF IF

• STEP 2: SET TEMP = HEAD
• STEP 3: SET I = 0
• STEP 4: REPEAT STEP 5 TO 8 UNTIL I
• STEP 5: TEMP1 = TEMP
• STEP 6: TEMP = TEMP → NEXT
• STEP 7: IF TEMP = NULL

WRITE "DESIRED NODE NOT PRESENT"
    GOTO STEP 12
    END OF IF

• STEP 8: I = I+1

END OF LOOP

• STEP 9: TEMP1 → NEXT = TEMP → NEXT
• STEP 10: FREE TEMP
• STEP 11: EXIT

C function

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. void create(int);  
4. void delete_specified();  
5. struct node  
6. {  
7.     int data;  
8.     struct node *next;  
9. };  
10. struct node *head;  
11. void main ()  
12. {  
13.     int choice,item;  
14.     do   
15.     {  
16.         printf("\n1.Append List\n2.Delete node\n3.Exit\n4.Enter your choice?");  
17.         scanf("%d",&choice);  
18.         switch(choice)  
19.         {  
20.             case 1:  
21.             printf("\nEnter the item\n");  
22.             scanf("%d",&item);  
23.             create(item);  
24.             break;   
25.             case 2:  
26.             delete_specified();  
27.             break;   
28.             case 3:  
29.             exit(0);  
30.             break;    
31.             default:  
32.             printf("\nPlease enter valid choice\n");  
33.         }  
34.                   
35.     }while(choice != 3);  
36. }  
37. void create(int item)  
38.     {  
39.         struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
40.         if(ptr == NULL)  
41.         {  
42.             printf("\nOVERFLOW\n");  
43.         }  
44.         else  
45.         {  
46.             ptr->data = item;  
47.             ptr->next = head;  
48.             head = ptr;  
49.             printf("\nNode inserted\n");  
50.         }  
51.           
52.     }  
53. void delete_specified()  
54.     {  
55.         struct node *ptr, *ptr1;  
56.         int loc,i;   
57.         scanf("%d",&loc);  
58.         ptr=head;  
59.         for(i=0;i<loc;i++)  
60.         {  
61.             ptr1 = ptr;       
62.             ptr = ptr->next;  
63.               
64.             if(ptr == NULL)  
65.             {  
66.                 printf("\nThere are less than %d elements in the list..\n",loc);  
67.                 return;  
68.             }  
69.         }  
70.         ptr1 ->next = ptr ->next;  
71.         free(ptr);  
72.         printf("\nDeleted %d node ",loc);  
73.     }     

Output

1.Append List
2.Delete node
3.Exit
4.Enter your choice?1

Enter the item
12

Node inserted

1.Append List
2.Delete node
3.Exit
4.Enter your choice?1

Enter the item
23

Node inserted

1.Append List
2.Delete node
3.Exit
4.Enter your choice?2
12

There are less than 12 elements in the list..

1.Append List
2.Delete node
3.Exit
4.Enter your choice?2
1

Deleted 1 node 

Traversing in singly linked list

Traversing is the most common operation that is performed in almost every scenario of singly linked list. Traversing means visiting each node of the list once in order to perform some operation on that. This will be done by using the following statements.

1. ptr = head;   
2.         while (ptr!=NULL)  
3.             {  
4.                 ptr = ptr -> next;  
5.             }  

Algorithm

• STEP 1: SET PTR = HEAD
• STEP 2: IF PTR = NULL

   WRITE "EMPTY LIST"
  GOTO STEP 7
  END OF IF

• STEP 4: REPEAT STEP 5 AND 6 UNTIL PTR != NULL
• STEP 5: PRINT PTR→ DATA
• STEP 6: PTR = PTR → NEXT

[END OF LOOP]

• STEP 7: EXIT

C function

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. void create(int);  
4. void traverse();  
5. struct node  
6. {  
7.     int data;  
8.     struct node *next;  
9. };  
10. struct node *head;  
11. void main ()  
12. {  
13.     int choice,item;  
14.     do   
15.     {  
16.         printf("\n1.Append List\n2.Traverse\n3.Exit\n4.Enter your choice?");  
17.         scanf("%d",&choice);  
18.         switch(choice)  
19.         {  
20.             case 1:  
21.             printf("\nEnter the item\n");  
22.             scanf("%d",&item);  
23.             create(item);  
24.             break;   
25.             case 2:  
26.             traverse();  
27.             break;   
28.             case 3:  
29.             exit(0);  
30.             break;    
31.             default:  
32.             printf("\nPlease enter valid choice\n");  
33.         }  
34.                   
35.     }while(choice != 3);  
36. }  
37. void create(int item)  
38.     {  
39.         struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
40.         if(ptr == NULL)  
41.         {  
42.             printf("\nOVERFLOW\n");  
43.         }  
44.         else  
45.         {  
46.             ptr->data = item;  
47.             ptr->next = head;  
48.             head = ptr;  
49.             printf("\nNode inserted\n");  
50.         }  
51.           
52.     }  
53. void traverse()  
54.     {  
55.         struct node *ptr;     
56.         ptr = head;   
57.         if(ptr == NULL)  
58.         {  
59.             printf("Empty list..");  
60.         }  
61.         else  
62.         {  
63.             printf("printing values . . . . .\n");   
64.             while (ptr!=NULL)  
65.             {  
66.                 printf("\n%d",ptr->data);  
67.                 ptr = ptr -> next;  
68.             }  
69.         }  
70.      }  

Output

1.Append List
2.Traverse
3.Exit
4.Enter your choice?1

Enter the item
23

Node inserted

1.Append List
2.Traverse
3.Exit
4.Enter your choice?1

Enter the item
233

Node inserted

1.Append List
2.Traverse
3.Exit
4.Enter your choice?2
printing values . . . . .

233
23

Searching in singly linked list

Searching is performed in order to find the location of a particular element in the list. Searching any element in the list needs traversing through the list and make the comparison of every element of the list with the specified element. If the element is matched with any of the list element then the location of the element is returned from the function.

Algorithm

• Step 1: SET PTR = HEAD
• Step 2: Set I = 0
• STEP 3: IF PTR = NULL

  WRITE "EMPTY LIST"
  GOTO STEP 8
  END OF IF

• STEP 4: REPEAT STEP 5 TO 7 UNTIL PTR != NULL
• STEP 5: if ptr → data = item

  write i+1
 End of IF

• STEP 6: I = I + 1
• STEP 7: PTR = PTR → NEXT

[END OF LOOP]

• STEP 8: EXIT

C function

1.     #include<stdio.h>  
2. #include<stdlib.h>  
3. void create(int);  
4. void search();  
5. struct node  
6. {  
7.     int data;  
8.     struct node *next;  
9. };  
10. struct node *head;  
11. void main ()  
12. {  
13.     int choice,item,loc;  
14.     do   
15.     {  
16.         printf("\n1.Create\n2.Search\n3.Exit\n4.Enter your choice?");  
17.         scanf("%d",&choice);  
18.         switch(choice)  
19.         {  
20.             case 1:  
21.             printf("\nEnter the item\n");  
22.             scanf("%d",&item);  
23.             create(item);  
24.             break;   
25.             case 2:  
26.             search();  
27.             case 3:  
28.             exit(0);  
29.             break;    
30.             default:  
31.             printf("\nPlease enter valid choice\n");  
32.         }  
33.                   
34.     }while(choice != 3);  
35. }  
36.     void create(int item)  
37.     {  
38.         struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
39.         if(ptr == NULL)  
40.         {  
41.             printf("\nOVERFLOW\n");  
42.         }  
43.         else  
44.         {  
45.             ptr->data = item;  
46.             ptr->next = head;  
47.             head = ptr;  
48.             printf("\nNode inserted\n");  
49.         }  
50.           
51.     }  
52. void search()  
53. {  
54.     struct node *ptr;  
55.     int item,i=0,flag;  
56.     ptr = head;   
57.     if(ptr == NULL)  
58.     {  
59.         printf("\nEmpty List\n");  
60.     }  
61.     else  
62.     {   
63.         printf("\nEnter item which you want to search?\n");   
64.         scanf("%d",&item);  
65.         while (ptr!=NULL)  
66.         {  
67.             if(ptr->data == item)  
68.             {  
69.                 printf("item found at location %d ",i+1);  
70.                 flag=0;  
71.             }   
72.             else  
73.             {  
74.                 flag=1;  
75.             }  
76.             i++;  
77.             ptr = ptr -> next;  
78.         }  
79.         if(flag==1)  
80.         {  
81.             printf("Item not found\n");  
82.         }  
83.     }     
84.           
85. }  

Output

1.Create
2.Search
3.Exit
4.Enter your choice?1

Enter the item
23

Node inserted

1.Create
2.Search
3.Exit
4.Enter your choice?1

Enter the item
34

Node inserted

1.Create
2.Search
3.Exit
4.Enter your choice?2

Enter item which you want to search?
34
item found at location 1

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