Doubly Linked List

A Doubly Linked List (DLL) contains an extra pointer namely “previous pointer” together with the “next pointer”. Other than this, it is similar to Singly Linked List.

Representation of Doubly Linked list

//Node of a Doubly Linked List
struct Node
{
    int data;
    struct Node *next;  //Pointer to next node in DLL
    struct Node *prev;  //Pointer to previous node in DLL
}

• The DLL can traverse in both directions, forward and backward.
• We can quickly insert a new node before a given node.
• The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
• In Singly linked list, while deleting the given node pointer, we need to traverse from first to get the previous node of the given node pointer. But in Doubly Linked List, we can get previous node using previous node.

• Every node of DLL, requires an extra space to store the previous pointer. The DLL can be even implemented using single pointer though, using XOR Linked List (which is memory efficient doubly linked list).
• In both insertion and deletion, we need to modify an extra pointer (prev pointer) where as in Singly linked list we modify only one pointer.

A node can be inserted in four ways:

• At the front of the DLL
• After a given node
• At the end of the DLL
• Before a given node

void push(struct Node** head_ref, int new_data)
{
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

	//Assign a data to the node
	new_node->data = new_data;

	//Adjusting the links
	new_node->next = (*head_ref);
	new_node->prev = NULL;

	if ((*head_ref) != NULL)
		(*head_ref)->prev = new_node;

	//Assigning head to the newly added node
	(*head_ref) = new_node;
}

void insertAfter(struct Node* prev_node, int new_data)
{
	//check if the given prev_node is NULL
	if (prev_node == NULL) {
		printf("the given previous node cannot be NULL");
		return;
	}	

	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

	//Assign the data
	new_node->data = new_data;

	//Make next of new node as next of prev_node
	new_node->next = prev_node->next;

	//Make the next of prev_node as new_node
	prev_node->next = new_node;

	//Make prev_node as previous of new_node
	new_node->prev = prev_node;

	//Change previous of new_node's next node
	if (new_node->next != NULL)
		new_node->next->prev = new_node;
}

void append(struct Node** head_ref, int new_data)
{
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

	struct Node* last = *head_ref; 

	//Assign the data
	new_node->data = new_data;

	//This next of new_node is NULL as it is the last node in the list
	new_node->next = NULL;

	//If the list is empty, this is the only node in the list
	if (*head_ref == NULL) {
		new_node->prev = NULL;
		*head_ref = new_node;
		return;
	}

	//Traverse till the end
	while (last->next != NULL)
		last = last->next;

	//Adjusting the links
	last->next = new_node;
	new_node->prev = last;

	return;
}

void insertBefore(struct Node** head_ref, struct Node* next_node, int new_data)  
{  
    if (next_node == NULL) {  
        printf("the given next node cannot be NULL");  
        return;  
    }  
  
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));  
  
    //Assign the data
    new_node->data = new_data;  
  
    //Make prev of new node as prev of next_node
    new_node->prev = next_node->prev;  
  
    //Make the prev of next_node as new_node
    next_node->prev = new_node;  
  
    //Make next_node as next of new_node 
    new_node->next = next_node;  
  
    //Change next of new_node's previous node
    if (new_node->prev != NULL)  
     new_node->prev->next = new_node;  
    //If the prev of new_node is NULL, it will be the new head node
    else
        (*head_ref) = new_node; 
      
}  

void deleteNode(struct Node** head_ref, struct Node* del) 
{ 
    //Check whether the given list and the node to be deleted are NULL
    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; 
  
    //Free the memory allocated to the deleted node
    free(del); 
    return; 
}