A singly linked list is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. By saying that the node contains a pointer to the next node, we mean that the node stores the address of the next node in sequence. A singly linked list allows traversal of data only in one way.
In C, the structure of a Singly linked list can be given as,
struct node
{
int data;
struct node *next;
};
1.) Traversing a Linked List :-
Traversing a linked list means accessing the nodes of the list in order to perform some processing on them. Remember a linked list always contains a pointer variable START which stores the address of the first node of the list. End of the list is marked by storing NULL or –1 in the NEXT field of the last node.
**Algorithm for traversing a linked list**
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR DATA
Step 4: SET PTR = PTR-> NEXT
[END OF LOOP]
Step 5: EXIT
OR
**Algorithm to print the number of nodes in a linked list**
Step 1: [INITIALIZE] SET = 0
Step 2: [INITIALIZE] SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR != NULL
Step 4: SET COUNT = COUNT + 1
Step 5: SET PTR = PTR-> NEXT
[END OF LOOP]
Step 6: Write COUNT
Step 7: EXIT
2.) Searching for a Value in a Linked List :-
Searching a linked list means to find a particular element in the linked list. As already discussed, a linked list consists of nodes which are divided into two parts, the information part and the next part.
**Algorithm to search a linked list**
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Step 3 while PTR != NULL
Step 3: IF VAL = PTR -> DATA
SET POS = PTR
Go To Step 5
ELSE
SET PTR = PTR->NEXT
[END OF IF]
[END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT
3.) Inserting a New Node in a Linked List :-
In this section, we will see how a new node is added into an already existing linked list. We will take four cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning.
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted before a given node.
3.1.) Inserting a Node at the Beginning of a Linked List :-
**Algorithm to insert a new node at the beginning**
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET NEW_NODE-> DATA = VAL
Step 5: SET NEW_NODE-> NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT
3.2.) Inserting an element at the end of a linked list :-
**Algorithm to insert a new node at the end**
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 1
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR->NEXT != NULL
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: EXIT
3.3.) Inserting an element before a given node in a linked list :-
**Algorithm to insert a new node before a node that has value NUM**
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR -> DATA != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 10: PREPTR -> NEXT = NEW_NODE
Step 11: SET NEW_NODE -> NEXT = PTR
Step 12: EXIT
4.) Deleting a Node from a Linked List :-
In this section, we will discuss how a node is deleted from an already existing linked list. We will consider three cases and then see how deletion is done in each case.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The node after a given node is deleted.
4.1.) Deleting the first node of a linked list :-
**Algorithm to delete the first node**
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START -> NEXT
Step 4: FREE PTR
Step 5: EXIT
4.2.) Deleting the Last Node from a Linked List :-
**Algorithm to delete the last node**
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
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
4.3.) Deleting the Node After a Given Node in a Linked List :-
**Algorithm to delete the node after a given node**
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 1
[END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PREPTR->DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR->NEXT
[END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR->NEXT = PTR->NEXT
Step 9: FREE TEMP
Step 10: EXIT
***********************
**Programming Example**
***********************
1. Write a program to create a linked list and perform insertions and deletions of all cases.Write functions to sort and finally delete the entire list at once.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *create_ll(struct node *);
struct node *display(struct node *);
struct node *insert_beg(struct node *);
struct node *insert_end(struct node *);
struct node *insert_before(struct node *);
struct node *insert_after(struct node *);
struct node *delete_beg(struct node *);
struct node *delete_end(struct node *);
struct node *delete_node(struct node *);
struct node *delete_after(struct node *);
struct node *delete_list(struct node *);
struct node *sort_list(struct node *);
//int main(int argc, char *argv[]) //commend line arugment
int main()
{
int option;
do
{
printf(“\n\n *****MAIN MENU *****”);
printf(“\n 1: Create a list”);
printf(“\n 2: Display the list”);
printf(“\n 3: Add a node at the beginning”);
printf(“\n 4: Add a node at the end”);
printf(“\n 5: Add a node before a given node”);
printf(“\n 6: Add a node after a given node”);
printf(“\n 7: Delete a node from the beginning”);
printf(“\n 8: Delete a node from the end”);
printf(“\n 9: Delete a given node”);
printf(“\n 10: Delete a node after a given node”);
printf(“\n 11: Delete the entire list”);
printf(“\n 12: Sort the list”);
printf(“\n 13: EXIT”);
printf(“\n\n Enter your option : “);
scanf(“%d”, &option);
switch(option)
{
case 1: start = create_ll(start);
printf(“\n LINKED LIST CREATED”);
break;
case 2: start = display(start);
break;
case 3: start = insert_beg(start);
break;
case 4: start = insert_end(start);
break;
case 5: start = insert_before(start);
break;
case 6: start = insert_after(start);
break;
case 7: start = delete_beg(start);
break;
case 8: start = delete_end(start);
break;
case 9: start = delete_node(start);
break;
case 10: start = delete_after(start);
break;
case 11: start = delete_list(start);
printf(“\n LINKED LIST DELETED”);
break;
case 12: start = sort_list(start);
break;
default:
printf("Wrong Choioc");
}
}while(option !=13);
getch();
return 0;
}
struct node *create_ll(struct node *start)
{
struct node *new_node, *ptr;
int num;
printf(“\n Enter -1 to end”);
printf(“\n Enter the data : “);
scanf(“%d”, &num);
while(num!=-1)
{
new_node = (struct node*)malloc(sizeof(struct node));
new_node -> data=num;
if(start==NULL)
{
new_node -> next = NULL;
start = new_node;
}
else
{
ptr=start;
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next = new_node;
new_node->next=NULL;
}
printf(“\n Enter the data : “);
scanf(“%d”, &num);
}
return start;
}
struct node *display(struct node *start)
{
struct node *ptr;
ptr = start;
while(ptr != NULL)
{
printf(“\t %d”, ptr -> data);
ptr = ptr -> next;
}
return start;
}
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num;
printf(“\n Enter the data : “);
scanf(“%d”, &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = start;
start = new_node;
return start;
}
struct node *insert_end(struct node *start)
{
struct node *ptr, *new_node;
int num;
printf(“\n Enter the data : “);
scanf(“%d”, &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = NULL;
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = new_node;
return start;
}
struct node *insert_before(struct node *start)
{
struct node *new_node, *ptr, *preptr;
int num, val;
printf(“\n Enter the data : “);
scanf(“%d”, &num);
printf(“\n Enter the value before which the data has to be inserted : “);
scanf(“%d”, &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = new_node;
new_node -> next = ptr;
return start;
}
struct node *insert_after(struct node *start)
{
struct node *new_node, *ptr, *preptr;
int num, val;
printf(“\n Enter the data : “);
scanf(“%d”, &num);
printf(“\n Enter the value after which the data has to be inserted : “);
scanf(“%d”, &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
preptr = ptr;
while(preptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next=new_node;
new_node -> next = ptr;
return start;
}
struct node *delete_beg(struct node *start)
{
struct node *ptr;
ptr = start;
start = start -> next;
free(ptr);
return start;
}
struct node *delete_end(struct node *start)
{
struct node *ptr, *preptr;
ptr = start;
while(ptr -> next != NULL)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = NULL;
free(ptr);
return start;
}
struct node *delete_node(struct node *start)
{
struct node *ptr, *preptr;
int val;
printf(“\n Enter the value of the node which has to be deleted : “);
scanf(“%d”, &val);
ptr = start;
if(ptr -> data == val)
{
start = delete_beg(start);
return start;
}
else
{
while(ptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = ptr -> next;
free(ptr);
return start;
}
}
struct node *delete_after(struct node *start)
{
struct node *ptr, *preptr;
int val;
printf(“\n Enter the value after which the node has to deleted : “);
scanf(“%d”, &val);
ptr = start;
preptr = ptr;
while(preptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next=ptr -> next;
free(ptr);
return start;
}
struct node *delete_list(struct node *start)
{
struct node *ptr; // Lines 252-254 were modified from original code to fix
unresposiveness in output window
if(start!=NULL)
{
ptr=start;
while(ptr != NULL)
{
printf(“\n %d is to be deleted next”, ptr -> data);
start = delete_beg(ptr);
ptr = start;
}
}
return start;
}
struct node *sort_list(struct node *start)
{
struct node *ptr1, *ptr2;
int temp;
ptr1 = start;
while(ptr1 -> next != NULL)
{
ptr2 = ptr1 -> next;
while(ptr2 != NULL)
{
if(ptr1 -> data > ptr2 -> data)
{
temp = ptr1 -> data;
ptr1 -> data = ptr2 -> data;
ptr2 -> data = temp;
}
ptr2 = ptr2 -> next;
}
ptr1 = ptr1 -> next;
}
return start; // Had to be added
}
Output:-
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add the node at the end
5: Add the node before a given node
6: Add the node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a given node
10: Delete a node after a given node
11: Delete the entire list
12: Sort the list
13: Exit
Enter your option : 3
Enter your option : 73
All c programming & algorithm 