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.
Implementation in C
#include #include #include #include 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] ]linked_list_algorithms.htm
- 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.
- 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.
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:
- The size of array must be known in advance before using it in the program.
- Increasing size of the array is a time taking process. It is almost impossible to expand the size of the array at run time.
- 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,
- 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.
- 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
| 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
struct 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.
| 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. . |
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.
| 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. . |
Linked List in C: Menu Driven Program
#include #include 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;inext; 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;inext; 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