The linked list is a linear data structure where each node has two parts. Show 1. Data 2. Reference to the next node In this section, we can store the required information. It can be any data type. ExampleReference to the next nodeIt will hold the next nodes address.
Head Node - Starting node of a linked list. Last Node - Node with reference pointer as NULL. Selecting a data type for the linked listAs we discussed earlier, each node in a linked list has two parts. Data - it can be any data type. int,char,float,double etc. Reference Part - It will hold the address of the next node. So, it is a type pointer.
Here, we need to group two different data types (heterogeneous). Which data type is used to group the different data types?That is a structure. So, every node in a linked list is a structure data type.
struct node { int data; struct node *next; }; where, data - used to store the integer information. struct node *next - It is used to refer to the next node. It will hold the address of the next node.
struct node { int data; struct node *next; }; struct node *head,*middle,*last; head = malloc(sizeof(struct node)); middle = malloc(sizeof(struct node)); last = malloc(sizeof(struct node));
head->data = 10; middle->data = 20; last->data = 30;
1. Stack memory stores all the local variables and function calls (static memory). Example: int a = 10; 2. Heap memory stores all the dynamically allocated variables. Example: int *ptr = malloc(sizeof(int)); Here, memory will be allocated in the heap section. And the ptr resides in the stack section and receives the heap section memory address on successful memory allocation. 3. Address of the dynamic memory which will be assigned to the corresponding variable. headnode middlenode lastnode NULL
head->next = middle; middle->next = last; last->next = NULL; //NULL indicates the end of the linked list
1. head => next = middle. Hence head => next holds the memory address of the middle node (2024). 2. middle => next = last. Hence middle => next holds the memory address of the last node (3024). 3. last => next = NULL which indicates it is the last node in the linked list. 4. The simplified version of the heap memory section.
To print each node's data, we have to traverse the linked list till the end.
1. Create a temporary node(temp) and assign the head node's address. 2. Print the data which present in the temp node. 3. After printing the data, move the temp pointer to the next node. 4. Do the above process until we reach the end.
1. temp points to the head node. temp => data = 10 will be printed. temp will point to the next node (Middle Node). 2. temp != NULL. temp => data = 20 will be printed. Again temp will point to the next node (Last Node). 3. temp != NULL. temp => data = 30 will be printed. Again temp will point to the next node which is NULL. 4. temp == NULL. Stop the process we have printed the whole linked list.
Code
struct node *temp = head; while(temp != NULL) { printf("%d ",temp->data); temp = temp->next; }
If we use the head pointer instead of the temp while printing the linked list, we will miss the track of the starting node. (After printing the data head node will point the NULL). To avoid that, we should not change the head node's address while processing the linked list. We should always use a temporary node to manipulate the linked list.
Example
#include<stdio.h> #include<stdlib.h> int main() { //node structure struct node { int data; struct node *next; }; //declaring nodes struct node *head,*middle,*last; //allocating memory for each node head = malloc(sizeof(struct node)); middle = malloc(sizeof(struct node)); last = malloc(sizeof(struct node)); //assigning values to each node head->data = 10; middle->data = 20; last->data = 30; //connecting each nodes. head->middle->last head->next = middle; middle->next = last; last->next = NULL; //temp is a reference for head pointer. struct node *temp = head; //till the node becomes null, printing each nodes data while(temp != NULL) { printf("%d->",temp->data); temp = temp->next; } printf("NULL"); return 0; }
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:
Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful because,
Singly linked list or One way chainSingly 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 ListThere are various operations which can be performed on singly linked list. A list of all such operations is given below. Node Creationstruct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 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 TraversingThe 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.
Linked List in C: Menu Driven Program#include<stdio.h> #include<stdlib.h> struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf("\n\n*********Main Menu*********\n"); printf("\nChoose one option from the following list ...\n"); printf("\n===============================================\n"); printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n 5.Delete from last\n6.Delete node after specified location\n7.Search for an element\n8.Show\n9.Exit\n"); printf("\nEnter your choice?\n"); scanf("\n%d",&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf("Please enter valid choice.."); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter value\n"); scanf("%d",&item); ptr->data = item; ptr->next = head; head = ptr; printf("\nNode inserted"); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter value?\n"); scanf("%d",&item); 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"); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter element value"); scanf("%d",&item); ptr->data = item; printf("\nEnter the location after which you want to insert "); scanf("\n%d",&loc); 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"); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf("\nList is empty\n"); } else { ptr = head; head = ptr->next; free(ptr); printf("\nNode deleted from the begining ...\n"); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf("\nlist is empty"); } else if(head -> next == NULL) { head = NULL; free(head); printf("\nOnly node of the list deleted ...\n"); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf("\nDeleted Node from the last ...\n"); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf("\n Enter the location of the node after which you want to perform deletion \n"); scanf("%d",&loc); ptr=head; for(i=0;i<loc;i++) { ptr1 = ptr; ptr = ptr->next; if(ptr == NULL) { printf("\nCan't delete"); return; } } ptr1 ->next = ptr ->next; free(ptr); printf("\nDeleted node %d ",loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf("\nEmpty List\n"); } else { printf("\nEnter item which you want to search?\n"); scanf("%d",&item); while (ptr!=NULL) { if(ptr->data == item) { printf("item found at location %d ",i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf("Item not found\n"); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf("Nothing to print"); } else { printf("\nprinting values . . . . .\n"); while (ptr!=NULL) { printf("\n%d",ptr->data); ptr = ptr -> next; } } } 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 Next TopicDoubly Linked List |
