Linked List is a user-defined Data structure, which is a collection of nodes and each node point to another node. Linked list store elements in a sequential manner and each node points to its successor node. Link list often used in the place of the array because some operations of the linked list have less time complexity as compared to an array. Some important terminology we use in Linked list.
- Node
- Next
- Linked list
Node: A node in a linked list contains elements and next pointer. Next: Next is a pointer which we assigned inside Node so it could 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 contain a next pointer which usually points to the address of the next node, except the last node.
- The first node in the linked list known as the head node.
- Each node contains some data value and a next pointer.
- Next pointer holds the address of the next node.
- The next pointer of the last node contains Null value.
Types of Linked List
There are 3 main types of Linked-List:
- Simple Linked List
- Doubly Linked List
- Circular Linked List
Simple Linked List
In simple linked list each node contains some data value and the address of the next sequential node in the next pointer. In simple linked list each node contains only one pointer variable, so we can only traverse forward.
Doubly Linked List
In 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
Circular Linked List is similar to 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
Insertion
In Insertion operation, we add new node or elements to the present linked list. The insertion operation itself 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.
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 target element next pointer value to its previous node next pointer. Traverse In traversing we usually display all the elements present in the linked list. 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;
}
People are also reading: