C program to perform operations on singly linked list

// C program for the all operations in // the Singly Linked List #include #include // Linked List Node struct node { int info; struct node* link; }; struct node* start = NULL; // Function to create list with n nodes initially void createList[] { if [start == NULL] { int n; printf["\nEnter the number of nodes: "]; scanf["%d", &n]; if [n != 0] { int data; struct node* newnode; struct node* temp; newnode = malloc[sizeof[struct node]]; start = newnode; temp = start; printf["\nEnter number to" " be inserted : "]; scanf["%d", &data]; start->info = data; for [int i = 2; i link = newnode; printf["\nEnter number to" " be inserted : "]; scanf["%d", &data]; newnode->info = data; temp = temp->link; } } printf["\nThe list is created\n"]; } else printf["\nThe list is already created\n"]; } // Function to traverse the linked list void traverse[] { struct node* temp; // List is empty if [start == NULL] printf["\nList is empty\n"]; // Else print the LL else { temp = start; while [temp != NULL] { printf["Data = %d\n", temp->info]; temp = temp->link; } } } // Function to insert at the front // of the linked list void insertAtFront[] { int data; struct node* temp; temp = malloc[sizeof[struct node]]; printf["\nEnter number to" " be inserted : "]; scanf["%d", &data]; temp->info = data; // Pointer of temp will be // assigned to start temp->link = start; start = temp; } // Function to insert at the end of // the linked list void insertAtEnd[] { int data; struct node *temp, *head; temp = malloc[sizeof[struct node]]; // Enter the number printf["\nEnter number to" " be inserted : "]; scanf["%d", &data]; // Changes links temp->link = 0; temp->info = data; head = start; while [head->link != NULL] { head = head->link; } head->link = temp; } // Function to insert at any specified // position in the linked list void insertAtPosition[] { struct node *temp, *newnode; int pos, data, i = 1; newnode = malloc[sizeof[struct node]]; // Enter the position and data printf["\nEnter position and data :"]; scanf["%d %d", &pos, &data]; // Change Links temp = start; newnode->info = data; newnode->link = 0; while [i < pos - 1] { temp = temp->link; i++; } newnode->link = temp->link; temp->link = newnode; } // Function to delete from the front // of the linked list void deleteFirst[] { struct node* temp; if [start == NULL] printf["\nList is empty\n"]; else { temp = start; start = start->link; free[temp]; } } // Function to delete from the end // of the linked list void deleteEnd[] { struct node *temp, *prevnode; if [start == NULL] printf["\nList is Empty\n"]; else { temp = start; while [temp->link != 0] { prevnode = temp; temp = temp->link; } free[temp]; prevnode->link = 0; } } // Function to delete from any specified // position from the linked list void deletePosition[] { struct node *temp, *position; int i = 1, pos; // If LL is empty if [start == NULL] printf["\nList is empty\n"]; // Otherwise else { printf["\nEnter index : "]; // Position to be deleted scanf["%d", &pos]; position = malloc[sizeof[struct node]]; temp = start; // Traverse till position while [i < pos - 1] { temp = temp->link; i++; } // Change Links position = temp->link; temp->link = position->link; // Free memory free[position]; } } // Function to find the maximum element // in the linked list void maximum[] { int a[10]; int i; struct node* temp; // If LL is empty if [start == NULL] printf["\nList is empty\n"]; // Otherwise else { temp = start; int max = temp->info; // Traverse LL and update the // maximum element while [temp != NULL] { // Update the maximum // element if [max < temp->info] max = temp->info; temp = temp->link; } printf["\nMaximum number " "is : %d ", max]; } } // Function to find the mean of the // elements in the linked list void mean[] { int a[10]; int i; struct node* temp; // If LL is empty if [start == NULL] printf["\nList is empty\n"]; // Otherwise else { temp = start; // Stores the sum and count of // element in the LL int sum = 0, count = 0; float m; // Traverse the LL while [temp != NULL] { // Update the sum sum = sum + temp->info; temp = temp->link; count++; } // Find the mean m = sum / count; // Print the mean value printf["\nMean is %f ", m]; } } // Function to sort the linked list // in ascending order void sort[] { struct node* current = start; struct node* index = NULL; int temp; // If LL is empty if [start == NULL] { return; } // Else else { // Traverse the LL while [current != NULL] { index = current->link; // Traverse the LL nestedly // and find the minimum // element while [index != NULL] { // Swap with it the value // at current if [current->info > index->info] { temp = current->info; current->info = index->info; index->info = temp; } index = index->link; } // Update the current current = current->link; } } } // Function to reverse the linked list void reverseLL[] { struct node *t1, *t2, *temp; t1 = t2 = NULL; // If LL is empty if [start == NULL] printf["List is empty\n"]; // Else else { // Traverse the LL while [start != NULL] { // reversing of points t2 = start->link; start->link = t1; t1 = start; start = t2; } start = t1; // New head Node temp = start; printf["Reversed linked " "list is : "]; // Print the LL while [temp != NULL] { printf["%d ", temp->info]; temp = temp->link; } } } // Driver Code int main[] { int choice; while [1] { printf["\n\t1 To see list\n"]; printf["\t2 For insertion at" " starting\n"]; printf["\t3 For insertion at" " end\n"]; printf["\t4 For insertion at " "any position\n"]; printf["\t5 For deletion of " "first element\n"]; printf["\t6 For deletion of " "last element\n"]; printf["\t7 For deletion of " "element at any position\n"]; printf["\t8 To find maximum among" " the elements\n"]; printf["\t9 To find mean of " "the elements\n"]; printf["\t10 To sort element\n"]; printf["\t11 To reverse the " "linked list\n"]; printf["\t12 To exit\n"]; printf["\nEnter Choice :\n"]; scanf["%d", &choice]; switch [choice] { case 1: traverse[]; break; case 2: insertAtFront[]; break; case 3: insertAtEnd[]; break; case 4: insertAtPosition[]; break; case 5: deleteFirst[]; break; case 6: deleteEnd[]; break; case 7: deletePosition[]; break; case 8: maximum[]; break; case 9: mean[]; break; case 10: sort[]; break; case 11: reverseLL[]; break; case 12: exit[1]; break; default: printf["Incorrect Choice\n"]; } } return 0; }

Singly Linked List Operations

• Insert in Linked List
• Delete node in Linked List based on position
• Display Nodes in Linked List
• Count Nodes in Linked List

Singly Linked List Example Program [ Insert, Delete, Display and Count]

/* Singly Linked List Example - All Operations Example Program Using Functions in C*/ /* Data Structure Programs,C Linked List Examples */ /* Singly Linked List Example - Insert,Delete,Display and Count Operations*/ #include #include #include struct node { int value; struct node *next; }; void insert[]; void display[]; void delete[]; int count[]; typedef struct node DATA_NODE; DATA_NODE *head_node, *first_node, *temp_node = 0, *prev_node, next_node; int data; int main[] { int option = 0; printf["Singly Linked List Example - All Operations\n"]; while [option < 5] { printf["\nOptions\n"]; printf["1 : Insert into Linked List \n"]; printf["2 : Delete from Linked List \n"]; printf["3 : Display Linked List\n"]; printf["4 : Count Linked List\n"]; printf["Others : Exit[]\n"]; printf["Enter your option:"]; scanf["%d", &option]; switch [option] { case 1: insert[]; break; case 2: delete[]; break; case 3: display[]; break; case 4: count[]; break; default: break; } } return 0; } void insert[] { printf["\nEnter Element for Insert Linked List : \n"]; scanf["%d", &data]; temp_node = [DATA_NODE *] malloc[sizeof [DATA_NODE]]; temp_node->value = data; if [first_node == 0] { first_node = temp_node; } else { head_node->next = temp_node; } temp_node->next = 0; head_node = temp_node; fflush[stdin]; } void delete[] { int countvalue, pos, i = 0; countvalue = count[]; temp_node = first_node; printf["\nDisplay Linked List : \n"]; printf["\nEnter Position for Delete Element : \n"]; scanf["%d", &pos]; if [pos > 0 && pos next; first_node = temp_node; printf["\nDeleted Successfully \n\n"]; } else { while [temp_node != 0] { if [i == [pos - 1]] { prev_node->next = temp_node->next; if[i == [countvalue - 1]] { head_node = prev_node; } printf["\nDeleted Successfully \n\n"]; break; } else { i++; prev_node = temp_node; temp_node = temp_node -> next; } } } } else printf["\nInvalid Position \n\n"]; } void display[] { int count = 0; temp_node = first_node; printf["\nDisplay Linked List : \n"]; while [temp_node != 0] { printf["# %d # ", temp_node->value]; count++; temp_node = temp_node -> next; } printf["\nNo Of Items In Linked List : %d\n", count]; } int count[] { int count = 0; temp_node = first_node; while [temp_node != 0] { count++; temp_node = temp_node -> next; } printf["\nNo Of Items In Linked List : %d\n", count]; return count; }

Types of linked list

There are three types of linked list:
-Singly Linked list.
-Doubly linked list.
-Circular Linked list.

Singly linked list

Singly Linked list is also known as one way list list in which we can traverse only in forward/one direction because a node in singly linked list contains a data part and a link part.
The data part of the node holds the value/element and link part of the node holds the address of its immediate successor.

Operations on Singly linked list

1. Insertion:

The insertion operation in linked list is used to insert the new node. The insertion of node in singly linked list can be performed at different positions.

a] Insertion of node in the beginning:

In this a new node is inserted in the front of already existing linked list. For this we have to follow some steps:

• First we will create a new node and store the data into the data part.
• Now we will point the link part of the new node with the first node[start] of existing linked list
• After that we will make new node as the first node[start]

p=[struct node *] malloc[sizeof[struct node]]; p→data=value; p->next=start; start=p; //new node 'p' will become the first node of the list

b] Insertion of node at the end:

The insertion of node at the end of singly linked list can have two cases:

• First case when there is not even a single node in the list[list is empty]. In this case the condition [start==NULL] will be satisfied.
  Since, 'p' is the only node that will be inserted in the list so we need to make this node point to the 'start' pointer.

p->data=value; p->next=NULL; start=p;

• Second case when we have to add a node at the end of already existing linked list. In this we will use a loop to traverse to the end of list. So, we need to declare a temporary variable temp in order to traverse through the list.
• At the end of the loop, the temp will be point to the last node of the list. The next part of the temp node will point to the new node 'p'. The next part of node 'p' will point to the null.

temp=start; while[temp→next!=NULL] //traverse through the list temp=temp→next; temp=start; while[temp->next!=NULL] temp=temp->next; temp->next=p; //next of temp will point to 'p' p->next=NULL; //next of 'p' will point to null

C] Inserting a node at any specified location:

• In this operation, we will skip some nodes until we reach the specified location. Once we reach the location, we will insert the node there. Here, we will use a for loop to reach the location where we want to insert our new node.

for[i=0;inext; if[temp==NULL] return; }

• Create a new node 'p store the data in the data part.
• The next part of the new node p must contain the address part of the next part of the temp
• Last step would be to make the next part of the temp point to the new node p.

p=[struct node*]malloc[sizeof[struct node]]; p->data=value; p->next=temp->next; temp->next=p;

2. Deletion:

The deletion operation in linked list is used to delete the node. Just like insertion, the deletion operation on linked list can be performed at different positions.

a] Deletion of node in the beginning:

• Deletion of a node in the beginning is a simple operation. Here, we will first copy the address of the first node 'start' to some temporary variable say 'p'.
• Move the first node 'start' to the second node of the linked list i.e.start =start->next.
• Now, free the pointer p.
  The free[] function is used to de-allocate the memory.

p=start; start=start->next; free[p];

b] Deletion of node at the end of linked list:

There can be two cases while implementing deletion operation at the end of a singly linked list.

• First case: if there is only one node in the list,then the condition [start==NULL] will be satisfied and the start node will be assigned to null.

p=start; start=NULL; free[p]; //'p' will be deleted

• Second case: Here we have to traverese the list until we reach the end node of the list. The temp pointer is assigned to start pointer of the list and it will traverse the list till it reaches to the last node.

p=start; while[p->next!=NULL] { p1=p; //'p1' keeps track of second last node. p=p->next; } p1->next=NULL; free[p];

c] Deletion of node at any specified position:

• When we performed insertion operation of node at specified location, we skipped the nodes until we reached the desired location. Similarly, in the deletion operation of node at specified location we will skip some nodes until we reach the specified location.
• Here, we need to keep track of two nodes. One which is to be deleted 'p' and the other which is just before that node 'p1'.

p=start; for[i=0;inext; if[p==NULL] //when the location entered is more than the size of linked list { printf["\nlocation does not exist"]; return; } }

Now,we just have to make some pointer adjustments. The next of p1 will point to the next of p.

p1->next=p->next; free[p]; //'p' will be deleted

3. Traversing

Traversing operation is the most commonly performed operation in singly linked list. Traversing means visiting each node of the linked list at least once in order to perform some operation. Example: printing the elements in the linked list.

p=start; while [p!=NULL] p=p->next;

So these were some operations that we can perform on singly linked list.

A complete program of different types of operations on singly linked list

#include #include struct node { int data; struct node *next; }; struct node *start; /*fuction declaration of all the operations*/ void insert_begin[]; void insert_last[]; void insert_locc[]; void delete_begin[]; void delete_last[]; void delete_locc[]; void print[]; void main [] { int ch=0; while[ch!=8] { printf["\nEnter the operation to be performed\n"]; printf["\n1.Insert in the begining\n2.Insert at last\n3.Insert at any specified position\n4.Delete from Beginning\n5.Delete from last\n6.Delete node after specified location\n7.Show\n8.Exit\n"]; scanf["\n%d",&ch]; switch[ch] { /*function calls of all the operations */ case 1: insert_begin[]; break; case 2: insert_last[]; break; case 3: insert_locc[]; break; case 4: delete_begin[]; break; case 5: delete_last[]; break; case 6: delete_locc[]; break; case 7: print[]; break; case 8: exit[0]; break; default: printf["Enter valid option"]; } } } /*function definition*/ void insert_begin[] //to insert the node at the beginnning of linked list { struct node *p; int value; p=[struct node *] malloc[sizeof[struct node *]]; if[p==NULL] { printf["\nOVERFLOW"]; } else { printf["\nEnter value\n"]; scanf["%d",&value]; p->data=value; p->next=start; start=p; } } void insert_last[] //to insert the node at the last of linked list { struct node *p,*temp; int value; p=[struct node*]malloc[sizeof[struct node]]; if[p==NULL] { printf["\nOVERFLOW"]; } else { printf["\nEnter value\n"]; scanf["%d",&value]; p->data=value; if[start==NULL] { p->next=NULL; start=p; } else { temp=start; while[temp->next!=NULL] { temp=temp->next; } temp->next=p; p->next=NULL; } } } void insert_locc[] //to insert the node at the specified location of linked list { int i,loc,value; struct node *p, *temp; p=[struct node *]malloc[sizeof[struct node]]; if[p==NULL] { printf["\nOVERFLOW"]; } else { printf["\nEnter element value"]; scanf["%d",&value]; p->data=value; printf["\nEnter the location after which you want to insert "]; scanf["\n%d",&loc]; temp=start; for[i=0;inext; if[temp==NULL] { printf["\ncan't insert\n"]; return; } } p->next=temp->next; temp->next=p; } } void delete_begin[] //to delete the node present in the beginning of the linked list { struct node *p; if[start==NULL] { printf["\nList is empty\n"]; } else { p=start; start=p->next; free[p]; } } void delete_last[] //to delete the node present in the last of the linked list { struct node *p,*p1; if[start==NULL] { printf["\nlist is empty"]; } else if[start->next==NULL] { start=NULL; free[start]; printf["\nOnly node of the list deleted ...\n"]; } else { p=start; while[p->next!=NULL] { p1=p; p=p->next; } p1->next=NULL; free[p]; } } void delete_locc[] //to delete the node present at the specified of the linked list { struct node *p,*p1; int loc,i; printf["\n Enter the location of the node after which you want to perform deletion \n"]; scanf["%d",&loc]; p=start; for[i=0;inext; if[p==NULL] { printf["\nCan't delete"]; return; } } p1->next=p->next; free[p]; printf["\nDeleted node %d ",loc+1]; } void print[] //to print the values in the linked list { struct node *p; p=start; if[p==NULL] { printf["Nothing to print"]; } else { printf["\nprinting values\n"]; while [p!=NULL] { printf["\n%d",p->data]; p=p->next; } } }

OUTPUT:

Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 1 Enter value 89 Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 1 Enter value 44 Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 1 Enter value 78 Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 2 Enter value 80 Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 7 printing values 78 44 89 80 Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 5 Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 7 printing values 78 44 89 Enter the operation to be performed 1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit

What is Linked List in C?

A Linked List is a linear data structure. Every linked list has two parts, the data section and the address section that holds the address of the next element in the list, which is called a node.

The size of the linked list is not fixed, and data items can be added at any locations in the list. The disadvantage is that to get to a node, we must traverse to all the way from the first node to the node that we require. The Linked List is like an array but unlike an array, it is not stored sequentially in the memory.

The most popular types of a linked list are:

1. Singly link list
2. Doubly link list

Example of Linked List

Format:[data,address]

Head->[3,1000]->[43,1001]->[21,1002]

In the example, the number 43 is present at location 1000 and the address is present at in the previous node. This is how a linked list is represented.

Singly Linked List in C

Video liên quan