Reviewed and fact-checked by Sayantoni Das
A linked list is the most sought-after data structure when it comes to handling dynamic data elements. A linked list consists of a data element known as a node. And each node consists of two fields: one field has data, and in the second field, the node has an address that keeps a reference to the next node.
What is a Linked List?
- A linked list is a linear data structure that stores a collection of data elements dynamically.
- Nodes represent those data elements, and links or pointers connect each node.
- Each node consists of two fields, the information stored in a linked list and a pointer that stores the address of its next node.
- The last node contains null in its second field because it will point to no node.
- A linked list can grow and shrink its size, as per the requirement.
- It does not waste memory space.
Representation of a Linked List
This representation of a linked list depicts that each node consists of two fields. The first field consists of data, and the second field consists of pointers that point to another node.
Here, the start pointer stores the address of the first node, and at the end, there is a null pointer that states the end of the Linked List.
Creation of Node and Declaration of Linked Lists
|
struct node { int data; struct node * next; }; struct node * n; n=(struct node*)malloc(sizeof(struct node*)); |
It is a declaration of a node that consists of the first variable as data and the next as a pointer, which will keep the address of the next node.
Here you need to use the malloc function to allocate memory for the nodes dynamically.
Types of Linked Lists
The linked list mainly has three types, they are:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Singly Linked List
A singly linked list is the most common type of linked list. Each node has data and an address field that contains a reference to the next node.
Doubly Linked List
There are two pointer storage blocks in the doubly linked list. The first pointer block in each node stores the address of the previous node. Hence, in the doubly linked inventory, there are three fields that are the previous pointers, that contain a reference to the previous node. Then there is the data, and last you have the next pointer, which points to the next node. Thus, you can go in both directions (backward and forward).
Circular Linked List
The circular linked list is extremely similar to the singly linked list. The only difference is that the last node is connected with the first node, forming a circular loop in the circular linked list.
Circular link lists can either be singly or doubly-linked lists.
- The next node's next pointer will point to the first node to form a singly linked list.
- The previous pointer of the first node keeps the address of the last node to form a doubly-linked list.
Essential Operation on Linked Lists
- Traversing: To traverse all nodes one by one.
- Insertion: To insert new nodes at specific positions.
- Deletion: To delete nodes from specific positions.
- Searching: To search for an element from the linked list.
Traversal
In this operation, you will display all the nodes in the linked list.
When the temp is null, it means you traversed all the nodes, and you reach the end of the linked list and get out from the while loop.
|
struct node * temp = start; printf(“\n list empty are-”); while (temp!= NULL) { printf(‘%d “, temp -> data) temp=temp -> next; } |
Insertion
You can add a node at the beginning, middle, and end.
Insert at the Beginning
- Create a memory for a new node.
- Store data in a new node.
- Change next to the new node to point to start.
- Change starts to tell the recently created node.
|
struct node *NewNode; NewNode=malloc(sizeof(struct node)); NewNode -> data = 40; NewNode -> next= start; start= NewNode; |
Insert at the End
- Insert a new node and store data in it.
- Traverse the last node of a linked list
- Change the next pointer of the last node to the newly created node.
|
struct node *NewNode; NewNode=malloc(sizeof(struct node)); NewNode-> data = 40; NewNode->next = NULL; struct node *temp = start; while( temp->next ! = NULL){ temp=temp -> next; } temp -> next = NewNode; |
Insert at the Middle
- Allocate memory and store data in the new node.
- Traverse the node, which is just before the new node.
- Change the next pointer to add a new node in between.
|
struct node *NewNode; NewNode= malloc(sizeof(struct node)); NewNode -> data = 40; struct node - > temp = start; for(int i=2; i<position; i++){ if (temp -> next!= NULL) temp = temp -> next; }} NewNode -> next = temp -> next; temp -> next = NewNode; |
Deletion
You can also do deletion in the linked list in three ways either from the end, beginning, or from a specific position.
Delete from the Beginning
- The point starts at the second node.
|
start = start -> next; |
Delete from the End
- Traverse the second last element in the linked list.
- Change its next pointer to null.
|
struct node * temp = start; while(temp -> next -> next!= NULL){ temp=temp -> next; } temp -> next = NULL; |
Delete from the Middle
- Traverse the element before the element to be deleted.
- Change the next pointer to exclude the node from the linked list.
|
for (int i = 2; i, position; i++){ if (temp -> next ! = NULL) temp = temp -> next; } } temp-> next = temp -> next -> next; |
Searching
The search operation is done to find a particular element in the linked list. If the element is found in any location, then it returns. Else, it will return null.
Operations on Linked-Lists
Code to Insert at the Beginning of the Linked List
|
void insertatbeg() { struct node *NewNode; int item; NewNode = (struct node *) malloc(sizeof(struct node *)); if(NewNode == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter value\n"); scanf("%d",&item); NewNode->data = item; NewNode->next = start; start = NewNode; printf("\nNode inserted"); } } |
Code to Insert at the End of the Linked List
|
void insertatend() { struct node *NewNode,*temp; int item; NewNode = (struct node*)malloc(sizeof(struct node)); if(NewNode == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter value?\n"); scanf("%d",&item); NewNode->data = item; if(start == NULL) { NewNode -> next = NULL; start = NewNode; printf("\nNode inserted"); } else { temp = start; while (temp -> next != NULL) { temp = temp -> next; } temp->next = NewNode; NewNode->next = NULL; printf("\nNode inserted"); } } } |
Code to Insert at the Middle of the Linked List
|
void insertmiddle() { int i,position,item; struct node *NewNode, *temp; NewNode = (struct node *) malloc (sizeof(struct node)); if(NewNode == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter element value"); scanf("%d",&item); NewNode-> data = item; printf("\n Enter the location after which you want to insert an element "); scanf("\n%d",&position); temp=start; for(i=0;i<position;i++) { temp = temp->next; if(temp == NULL) { printf("\can't insert\n"); return; } } NewNode ->next = temp ->next; temp ->next = NewNode; printf("\nNode inserted"); } } |
Code to Delete From the Beginning of the Linked List
|
void deleteatbeg() { struct node *NewNode; if(start == NULL) { printf("\nList is empty\n"); } else { NewNode = start; start = NewNode->next; free(NewNode); printf("\nNode deleted from the beginning\n"); } } |
Code to Delete From the End of the Linked List
|
void deleteatend() { struct node *NewNode,*NewNode1; if(start == NULL) { printf("\list is empty"); } else if(start -> next == NULL) { start = NULL; free(NewNode); printf("\n node of the list deleted\n"); } else { NewNode = start; while(NewNode->next != NULL) { NewNode1 = NewNode; NewNode = NewNode ->next; } NewNode1->next = NULL; free(NewNode); printf("\nDeleted Node from the last\n"); } } |
Code to Delete From the Middle of the Linked List
|
void deletemiddle() { struct node *NewNode,*NewNode1; int position,i; printf("\n what location of the node \n"); scanf("%d",&position); NewNode=start; for(i=0;i<position;i++) { NewNode1 = NewNode; NewNode = NewNode->next; if(NewNode == NULL) { printf("\nCan't delete"); return; } } NewNode1 ->next = NewNode ->next; free(NewNode); printf("\nDeleted node %d ",position+1); } |
Code to Search for an Element From the Linked List.
|
void search() { struct node *NewNode; int item,i=0,flag; NewNode = start; if(NewNode == NULL) { printf("\nEmpty List\n"); } else { printf("\nEnter an item which you want to search\n"); scanf("%d",&item); while (NewNode!=NULL) { if(NewNode->data == item) { printf("item found at position%d ",i+1); flag=0; } else { flag=1; } i++; NewNode = NewNode -> next; } if(flag==1) { printf("Item not found\n"); } } } |
Code to Show Data Elements of the Linked-List
|
void show() { struct node *NewNode; NewNode = start; if(NewNode == NULL) { printf("Nothing to print"); } else { printf("\nprinting values\n"); while (NewNode!=NULL) { printf("\n%d",NewNode->data); NewNode = NewNode -> next; } } } |
Application of a Linked List
- A linked list is used to implement stacks and queues.
- A linked list also helps to implement an adjacency matrix graph.
- It is used for the dynamic memory location.
- The linked list makes it easy to deal with the addition and multiplication of polynomial operations.
- Implementing a hash table, each bucket of the hash table itself behaves as a linked list.
- It is used in a functionality known as undo in Photoshop and Word.
With that, you have reached the end of this tutorial on Linked Lists.
Next Steps
“Stack in data structure” can be next in the line of news topic. It makes sense to learn about stack representation, implementation, and application, where stack plays a vital role.
If you are perhaps looking to build a career in data analytics, do explore Simplilearn’s Data Analytics Certification Program in partnership with Purdue University & in collaboration with IBM. Featuring ask-me-anything sessions from IBM, a masterclass from Purdue, and many great benefits, this program will give you the work-ready data analytics training you need to succeed today.
If you have any queries regarding linked lists in data structures, please feel free to comment below. Our experts will be happy to resolve your question as soon as possible.
