Double Linked List
A Double Linked List is one in which all nodes are linked together by multiple links which helps in accessing both the successor (next node) node and the predecessor (previous node) node. Therefore each node in a doubly linked list fields(pointers) to the left node(previous) and the right node(next).
This helps to traverse the list in the forward direction and backward direction.
- Link - Each link of a linked list can store a data called an element.
- Next - Each link of a linked list contains a link to the next link called Next.
- Prev - Each link of a linked list contains a link to the previous link called Prev.
- LinkedList - A Linked List contains the connection link to the first link called First and to the last link called Last.
Doubly Linked List Representation
- Doubly Linked List contains a link element called first and last.
- Each link carries a data fields and two link fields called next and prev.
- Each link is linked with its next link using its next link.
- Each link is linked with its previous link using its previous link.
- The last link carries a link as null to mark the end of the list.
Basic Operations
- Insertion - Adds an element at the beginning of the list.
- Deletion - Deletes an element at the beginning of the list.
- Insert Last - Adds an element at the end of the list.
- Delete Last - Deletes an element from the end of the list.
- Insert After - Adds an element after an item of the list.
- Delete - Deletes an element from the list using the key.
- Display forward - Displays the complete list in a forward manner.
- Display backward - Displays the complete list in a backward manner.
Listing: Following program showing the all deletion methods on doubly Linked List.
/* A C program for deletion operations on doubly linked list. */
#include <stdio.h>
#include <stdlib.h>
/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};
/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
void deleteNode(struct node **head_ref, struct node *del)
{
/* base case */
if(*head_ref == NULL || del == NULL)
return;
/* If node to be deleted is head node */
if(*head_ref == del)
*head_ref = del->next;
/* Change next only if node to be deleted is NOT the last node */
if(del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be deleted is NOT the first node */
if(del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
return;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
/* Let us create the doubly linked list 10<->8<->4<->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
printf("\n Original Linked list ");
printList(head);
/* delete nodes from the doubly linked list */
deleteNode(&head, head); /*delete first node*/
deleteNode(&head, head->next); /*delete middle node*/
deleteNode(&head, head->next); /*delete last node*/
/* Modified linked list will be NULL<-8->NULL */
printf("\n Modified Linked list ");
printList(head);
getchar();
}
Reverse a Doubly Linked List: This operation is used for reversing all the elements present in the list.
Listing: Following Program showing the reverse operation on doubly linked list.
/* Program to reverse a doubly linked list */
#include <stdio.h>
#include <stdlib.h>
/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};
/* Function to reverse a Doubly Linked List */
void reverse(struct node **head_ref)
{
struct node *temp = NULL;
struct node *current = *head_ref;
/* swap next and prev for all nodes of
doubly linked list */
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
/* Before changing head, check for the cases like empty list and list with only one node */
if(temp != NULL )
*head_ref = temp->prev;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
printf("\n Original Linked list ");
printList(head);
/* Reverse doubly linked list */
reverse(&head);
printf("\n Reversed Linked list ");
printList(head);
getchar();
}