A linked list is a user-defined data structure, which is a collection of nodes, and each node points to another node. Linked lists store elements in a sequential manner, and each node points to its successor node. They are often used in place of the array because some operations of the linked list have less time complexity as compared to an array. Some important terminologies we use in a linked list are:
- Node
- Next
- Linked list
Node: A node in a linked list contains elements and the next pointer.
Next: Next is a pointer, which we assign inside the node so it can point to the next node.
Linked List: The linked list is a collection of sequential nodes.
Linked List Representation
In the linked list, each node is linked with another node, and each node contains a next pointer, which usually points to the address of the next node, except the last node.
- The first node in the linked list is known as the head node.
- Each node contains some data value and a next pointer.
- The next pointer holds the address of the next node.
- The next pointer of the last node contains a Null value.
Types of Linked Lists
There are 3 main types of linked lists:
- Simple linked list
- Doubly linked list
- Circular linked list
Simple Linked List
In a simple linked list, each node contains some data value and the address of the next sequential node in the next pointer. Each node contains only one pointer variable, so we can only traverse forward.
Simple Linked List Implementation Using C programming language:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
void display(struct node* head)
{
struct node *temp = head;
printf("\n\nElements Presesnt in the linked List are \n");
while(temp != NULL)
{
printf("%d --->",temp->data);
temp = temp->next;
}
}
void InsertAtMiddle(struct node *head, int position, int value) {
struct node *temp = head;
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = value;
int i;
for(i=2; inext != NULL) {
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
}
void InsertAtBeginning(struct node** headRef, int value) {
struct node* head = *headRef;
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->next = head;
head = newNode;
*headRef = head;
}
void InsertAtEnd(struct node* head, int value){
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->next = NULL;
struct node *temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
void DeleteFromDeginning(struct node** headRef){
struct node* head = *headRef;
head = head->next;
*headRef = head;
}
void deleteFromEnd(struct node* head){
struct node* temp = head;
while(temp->next->next!=NULL)
{
temp = temp->next;
}
temp->next = NULL;
}
void DeleteFromMiddle(struct node* head, int position){
struct node* temp = head;
int i;
for(i=2; inext != NULL) {
temp = temp->next;
}
}
temp->next = temp->next->next;
}
Doubly Linked List
In the doubly linked list , each node contains two pointers, except the head node; one pointer points to the next node, and the second pointer points to the previous node. In the doubly linked list, we can traverse back and forth direction.
Circular Linked List
A circular linked list is similar to a simple linked list, but here, the last node of the list points to the head of the node instead of Null. In the circular linked list, the next pointer of the last node contains the address of the first node, which is the head node.
Operations on Linked List
Here are some basic operations we can perform on a linked list:
- Insertion
- Deletion
- Traverse
- Search
- Sorting
1. Insertion
In the insertion operation, we add new nodes or elements to the present linked list. The insertion operation itself is divided into 3 parts:
- Insert at the beginning of a linked list
- Insert in the middle of a liked list
- Insert at the last of a liked list.
2. Deletion
In deletion, we go through each node of the list and try to delete the target element by removing its pointer variable. In deletion operation, we assign the target element's next pointer value to its previous node's next pointer.
3. Traverse
The traverse operation refers to the process of visiting and inspecting each node in the list sequentially. It involves moving through the linked list from the beginning (head node) to the end, examining or performing operations on each node along the way.
4. Search
The search operation begins at the head node of the linked list. The search operation involves finding a specific element within the list. Think of a linked list as a chain of connected nodes, where each node contains a piece of data and a reference to the next node in the sequence.
5. Sorting
Sorting refers to the process of arranging the elements or nodes within the list in a specific order, often ascending or descending, based on a few criteria, like numerical or alphabetical values.
Conclusion
In conclusion, linked lists are fundamental data structures in computer science that offer flexible storage for various applications. They help in multiple fields in various areas, such as memory management, symbol tables, and graph algorithms.
We hope this tutorial helps you understand the key concepts of the linked list.
People are also reading: