Types of Linked list
Single linked list
A single linked list is a linked list in which all nodes are connected with each other in sequence. Each node of a singly linked list has two fields. The first field is used to store the data, and the second field is used to link or pointer to the next field.
Doubly linked list
The doubly linked list is also called a two-way list in which every node is divided into three fields.
- The first field of the linked list is called the previous pointer field, which holds the address of the previous element of the list.
- The second field of the linked list stores the information.
- The third field of the linked list is called next pointer, which points to the next element of the linked list.
Two pointer variables are used in the doubly linked list which contains the address of the first element of the list and the last element of the list. If the previous part of the first element of the linked list remains NULL, that it indicates that there is no other node behind this node. If the next part of the last element of the linked list remains NULL,it indicates that there is no node next to it. The doubly link list can be traversed in both directions.
Representation of doubly link list
Suppose user wants to store integer value in linked list. For this, the doubly linked list structure must be in memory, so the structure will define.
Node Structure:
struct node
{
int info;
struct node * prev, *next;
};
Insert a node at the beginning
This algorithm is for adding a new node at the beginning:
Step 1: Allocate the memory for the new node. struct node* new = malloc(size of ( struct node)) Step 2: Enter the address of the head in a temporary variable. struct node* temp= head Step 3: Insert the data item into the information part of the new node. New -> info = item Step 4: NULL the previous part of the new node. New -> prev = NULL Step 5: Enter the head address in the next part of the new node. New -> next = head Step 6: It will check whether the head is NULL or not. If the head is NULL, then execute step7; otherwise, it will not. Step 7: Insert a new node in the head; therefore, the head will point to the new node. Step 8: Enter the address of the new node in the previous part of the head. Head -> prev = new Step9: EXIT
Function:
Insertatfirst (struct node ** head, int item)
{
struct node*new = malloc (sizeof (struct node));
new -> info = item;
new -> prev = NULL;
new -> next = head;
if (head = = NULL)
head = new;
else
{
head -> prev = new;
head = new;
}
}
Traversing the Doubly Linked list
- In order Traversal: For this, the following step is followed.
Step 1: The Linked list pointer will proceed until the head is NULL.
while (head != NULL)
Step 2: It will print every information part of the linked list and keep moving the head.
print head -> Info
head = head -> next
- Reverse Order Traversal: For this, the following step is followed.
Step 1: The Linked list pointer will proceed until the tail is NULL.
while (tail != NULL)
Step 2: It will print every information part of the linked list and keep moving the tail.
print tail -> Info
tail = tail -> next
Deletion from Doubly Link List
Delete a node at the beginning
If the doubly linked list is empty, then it will return the linked list; Otherwise, we will delete the node that indicates the head pointer. For this, the following step is followed.
Step 1: Take a temporary pointer, in which you will enter the address of the head. struct node *temp = head Step 2: You will check the head is NULL or not. If the head is NULL, then it will be returned. if (head = = NULL) return Step 3: If the head is not NULL, then assign the next part of the head to the next head. head = head -> next free (temp) Step 4: The head, which is pointing to the node, assign the NULL in its previous part. head -> prev = NULL Step 5: Exit
Function:
deletefromfirst (struct node *head)
{
struct node *temp = head;
if (head = = NULL)
return;
head = head -> next;
free (temp);
head -> prev = NULL;
}
Delete a node at the end
To delete the last node of the linked list, you will check three conditions.
- If the doubly linked list is empty, then it will return the linked list.
- If there is only one node in the linked list, you will delete it, and insert NULL in the head.
- If there is more than one item in the linked list, it will reach the last node first and then delete the last node. For this, the following step is followed.
Step 1: Take a temporary pointer, in which you will enter the address of the head. struct node *temp = head Step 2: You will check the head is NULL or not. If the head is NULL, then it will be returned. if (head = = NULL) return Step 3: You will check the next node of the head is NULL or not. If the next node of the head is NULL, then you will repeat the steps from 4 to 6. Step 4: Insert the NULL in the head. head=NULL Step 5: Free the temporary pointer. free(t) Step 6: return Step 7: You will run the temp until the next part of temp is NULL. while (temp -> next == NULL) temp = temp -> next Step 8: Insert the NULL in the previous of the temp. temp -> prev -> next = NULL Step 9: Free the temp free(temp) Step 10: exit
Function:
deletefromlast (struct node *head)
{
struct node * temp = head;
if (head = = NULL)
return;
if (head -> next = = NULL)
{
head = NULL;
free (temp);
return;
}
while (temp -> next != NULL)
temp = temp -> next;
temp -> prev -> next = NULL;
free (temp);
}
Circular Linked List
Each node in a circular linked list is connected like a circle. There is no NULL value at the end of the circular linked list. In this, the last node stores the address of the first node, i.e., the first and last node are adjacent.
There are two types of circular linked list:
- Single circular linked list
- Doubly circular linked list.