Singly Linked List
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.
Diagrammatic Representation
A node in a singly linked list contains 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 of the node stores the address of its immediate successor.
Time Complexity
Space Complexity
Operations on Singly Linked List
Node Creation
struct node
{ int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));
Insertion
At the beginning - It involves inserting any element at the front of the list.
void Insert_Begining()
{
int item;
struct node *ptr;
printf("Inserting Node in begining :");
ptr = (struct node *)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("\nOverflow\n");
}
else
{
printf("\nEnter data value : ");
scanf("%d", &item);
ptr->data = item;
ptr->link = head;
head = ptr;
printf("Node Inserted");
}
}
At e end - It involves inserting any element at the end of the list.
void Insert_Last()
{
printf("\n\nInserting Node at last :");
int i, n;
printf("\nHow many node to be inserted : ");
scanf("%d", &n);
for (i = 0; i < n; i++){
struct node *temp, *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if (ptr == NULL)
printf("\noverflow");
else{
printf("\nEnter data value : ");
scanf("%d", &item);
ptr->data = item;
ptr->link = NULL;
if (head == NULL){
head = ptr;
printf("Node Inserted");
}
else{
temp = head;
while (temp->link != NULL)
{
temp = temp->link;
}
temp->link = ptr;
printf("Node Inserted");
}
}
}
}
After any specific node - It involves insertion after the specified node of the linked list.
void Insert_Random()
{
printf("\nInserting Node at random position :\n");
int i, location, item;
struct node *ptr, *temp;
printf("Enter Data value : ");
scanf("%d", &item);
printf("Enter the position : ");
scanf("%d", &location);
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = item;
if (ptr == NULL){
printf("\nOverflow");
}
else{
temp = head;
location--;
while (location != 1){
temp = temp->link;
location--;
}
ptr->link = temp->link;
temp->link = ptr;
printf("\nNode Inserted");
}
}
Deletion
From the beginning - It involves deletion of a node from the beginning of the list.
void Delete_Begin()
{
struct node *temp;
printf("\n\nDeleting Node from begining :");
if (head == NULL)
printf("\nList is empty");
else{
temp = head;
head = temp->link;
free(temp);
printf("\nNode deleted from begining...!");
}
}
From the end of the list - It involves deleting the last node of the list.
void Delete_Last()
{
printf("\n\nDeleting Node from last :");
struct node *ptr, *ptr1;
if (head == NULL)
printf("\nList is EMPTY.. !");
else if (head->link == NULL){
free(head);
head = NULL;
printf("\nOnly Node of the Linked List is deleted .. !");
}
else{
ptr = head;
while (ptr->link != NULL)
{
ptr1 = ptr;
ptr = ptr->link;
}
ptr1->link = NULL;
free(ptr);
printf("\nLast Node deleted from the list.. !");
}
}
Delete any specific node data – It involves deleting the node containing any specific data.
void Delete()
{
struct node *ptr, *temp;
int key, i;
printf("\n\nDeleting Node : ");
printf("\nEnter key to delete : ");
scanf("%d", &key);
temp = head;
while (temp->data != key)
{
ptr = temp;
temp = temp->link;
}
ptr->link = temp->link;
free(temp);
printf("Node Deleted..!");
}
Searching
void Search()
{
printf("\n\nSearching element in list : ");
struct node *ptr;
int value, flag = 1, i = 1;
ptr = head;
if (ptr == NULL)
printf("\nEnpty List");
else{
printf("\nEnter key to search : ");
scanf("%d", &value);
while (ptr != NULL){
if (ptr->data == value){
printf("Item found at position : %d", i);
flag = 0;
}
i++;
ptr = ptr->link;
}
if (flag != 0){
printf("Item not found");
}
}
}
Doubly Linked List
It is similar to a regular linked list, but each node in the doubly linked list contains a reference to the next node and the previous node.
In a doubly linked list, each node contains two pointers or references: one pointing to the previous node and another pointing to the next node. This allows for bidirectional traversal of the list, as nodes can be accessed both forwards and backwards.
The first node in the doubly linked list is called the head, while the last node is called the tail. The head node's previous pointer points to null, while the tail node's next pointer also points to null.
Diagrammatic Representation
Syntax –
struct node
{
struct node *prev;
int data;
struct node *next;
}
How doubly linked list is different from singly linked list?
In a singly linked list, each node contains a reference to the next node in the list. This means that you can only traverse the list in one direction, from the head to the tail. If you want to traverse the list in the reverse direction, you have to start from the head and iterate through the entire list, which can be inefficient for large lists.
In contrast, a doubly linked list contains two pointers in each node, one pointing to the previous node and one pointing to the next node. This allows you to traverse the list in both forward and backward directions, which can be useful in certain applications. For example, if you want to insert a new node before a given node in the list, you can easily update the previous and next pointers of the affected nodes to maintain the integrity of the list.
Operations on Doubly Linked List
Insertion at the beginning
void Insert_Begining(){
printf("\n\nInserting node in begining...!");
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
printf("\nOverflow");
else{
printf("\nEnter data value : ");
scanf("%d",&item);
if(head == NULL){
ptr->prev = NULL;
ptr->next = NULL;
ptr->data = item;
head = ptr;
}
else{
ptr->data = item;
ptr->prev = NULL;
ptr->next = head;
head->prev = ptr;
head = ptr;
}
printf("Node Inserted...!");
}
}
Insertion at the end
void Insert_Last(){
printf("\n\nInserting Node at last : ");
int n;
printf("\nHow many node to be inserted : ");
scanf("%d",&n);
for(int i=0;i<n;i++){
struct node *ptr, *temp;
int data;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
printf("\nOverflow");
else{
printf("Enter data value : ");
scanf("%d",&data);
ptr->data = data;
if(head == NULL){
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else{
temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = ptr;
ptr->prev = temp;
ptr->next = NULL;
}
printf("Node Inserted...!\n");
}
}
}
Delete a node at specified position
void Delete(){
printf("\n\nDeleting a node : ");
struct node *ptr, *temp;
int position,c=1;
printf("\nEnter position : ");
scanf("%d",&position);
temp = head;
while(c != position){
ptr = temp;
temp = temp->next;
if(temp == NULL){
printf("Node can't be deleted");
return;
}
c++;
}
ptr->next = temp->next;
temp->next->prev = ptr;
free(temp);
printf("Node Deleted...!");
}
Delete from the beginning
void Delete_Begining(){
struct node *ptr;
printf("\n\nDeleting Node from begining : ");
if(head == NULL)
printf("\nUnderflow");
else if(head->next == NULL){
free(head);
head == NULL;
printf("\nOnly node of the list deleted");
}
else{
ptr = head;
head = head->next;
head->prev = NULL;
free(ptr);
printf("\nNode Deleted...!");
}
}
Delete from the end
void Delete_Last(){
printf("\n\nDeleting node from last : ");
struct node *ptr;
if(ptr == NULL)
printf("\nUnderflow");
else if(head->next == NULL){
free(head);
head == NULL;
printf("\nOnly node of the list deleted");
}
else{
ptr = head;
if(ptr->next != NULL)
ptr = ptr->next;
ptr->prev->next = NULL;
free(ptr);
printf("\nNode Deleted...!");
}
}
Delete any specific key
void Delete_Key(){
printf("\n\nDeleting Node using Key : ");
struct node *ptr, *temp;
int key;
printf("\nEnter key to delete : ");
scanf("%d",&key);
temp = head;
while(temp->data != key){
ptr = temp;
temp = temp->next;
}
temp->next->prev = ptr;
ptr->next = temp->next;
free(temp);
printf("Node Deleted...!");
}
Search
void Search_Key(){
printf("\n\nSearching position of key : ");
struct node *temp;
int key, flag,i=1;
temp = head;
if(temp == NULL)
printf("\nEmpty List");
else{
printf("\nEnter Key : ");
scanf("%d",&key);
while (temp != NULL){
if(temp->data == key){
printf("Item found at position : %d", i);
flag = 0;
}
i++;
temp = temp->next;
}
if (flag != 0){
printf("Item not FOUND....!");
}
}
}