Doubly Linked List in Data Structure

php-doubly-linked-list
doubly-linked-list-javascript
doubly-linked-list
doubly-linked-list
linked-list-in-php

Doubly Linked List in Data Structure

Linked lists are a widely used data structure because of their wide range of applications. Linked lists are also of three types:

1. Singly linked list

2. Doubly linked list

3. Circular linked list

This article will cover doubly linked list in detail.

What is a doubly-linked list?
The singly linked list had a single pointer pointing to the next node. But a doubly linked list contains two pointers. One pointer points to the next node and one pointer to the previous node. Thus, a doubly linked list is a two-way chain.

Every node in a doubly linked list has-

Data
Address of the next node
Address of the previous node
The purpose of a doubly linked list is to enable both-way traversal while still allowing non-contiguous memory storage. Just like a singly linked list, we need to have a starting pointer pointing to the first node. The last node in the list points to NULL.

Representation of Doubly Linked List
A doubly linked list is represented as follows:

Doubly linked list Representation

The above list is comprised of 4 nodes having four data points- A, B, C, D. Each node has two links one pointing forward and one pointing backwards.

Each node has the following structure:

Node structure

It comprises of two pointers and a data field.

a. Data: It constitutes the value of the data item inside the list.

b. Prev: It is a pointer pointing towards the previous node. For the first node, Prev points to NULL.

c. Next: It links the current node to the next node in the linked list. The ‘Next’ of the last node points towards NULL.

Basic Operations on Double Linked List
The basic set of operations that we can perform on a doubly linked list are:

1. Traverse forward: It means visiting each node from the beginning till the end with the help of the ‘Next’ pointer.

2. Traverse backwards: This operation is performed to visit each node but in the reverse direction. It will traverse the list from the end to the beginning.

3. Insertion: This operation inserts an element at any given position in the list.

4. Deletion: Deletion operation helps in deleting a node from the linked list.

5. Display forward: This operation is used to print/display all the data elements of the linked list from beginning till the end.

6. Display backwards: it will display the elements from the end to the beginning.

7. Search: Search operation helps in searching an element by traversing it.

Memory Representation of Doubly Linked List

1. Each node in a doubly-linked list consists of 3 parts- two-pointers and a node.

2. Due to two-pointers additional to data values, a doubly-linked list takes a lot of space as compared to other data structures.

3. The following image shows the memory representation of a linked list.

Memory Representation of Doubly Linked List:

1. Here, -1 represents NULL.

2. The Prev of the first node i.e. A and the Next of the last node i.e. D point towards NULL.

3. This memory representation shows that the values need not be stored contiguously.

4. The values 1000, 1056, 2004 and so on represent addresses in the memory.

5. We traverse the list until we find -1 in the Next of a node.

Creating a Node in Doubly Linked List
Each node in a doubly linked list has data as well pointers. Therefore, we use a structure to create the node.
The structure template for the node looks as follows:

struct Node
{
    int data;     //The data point
    struct Node *Prev;   //Pointer to the previous node
    struct Node *Next;    //Pointer to the next node
};

Traversal in a Doubly Linked List
Traversal refers to linearly visiting each node. In a doubly linked list, we can traverse in both forward and backward directions.

The function to perform the traversal is as follows:

List_traversal(struct Node *Head)
{
    Prev = (struct Node *)malloc(sizeof(struct Node));
    Next = (struct Node *)malloc(sizeof(struct Node));
    if(Head == NULL)   //If the list is empty
        return;
    while(Next->data != NULL)
    {
        Print(Next->data);   //The display operation
        Next = Next->data;
    }
}

The time complexity for the traversal operation is O(n).

Doubly Linked List Methods
There are various inbuilt methods defined inside the doubly-linked list class. A few of these methods are:

1. add_front: This method adds a new node at the beginning of the doubly linked list.

2. add_after: It adds a new node after a particular node.

3. add_before: It is used to add a new node before a particular node in the list.

4. add_end: This method will add a new node at the end of the doubly linked list.

5. forward_traverse: It helps in traversing the list in the forward direction.

6. backward_traverse: It helps in traversing the list in the backward direction.

7. delete: This method deletes a node from the linked list.

Their implementation inside the class is shown below:

class doubly_linked_list
{
  node *First;      // It points to the first node of the list
  node *Last;       // It points to the last node of the list

  public:
      Doubly_Linked_List()
      {
        front = NULL;
        end = NULL;
      }
  void add_front(int );  //Adds a new node at the beginning
  void add_after(node* , int );   //Adds a new node after the given node
  void add_before(node* , int );  //Adds a new node before a given node
  void add_end(int );     //Adds a new node at the end of the list
  void delete_node(node*);    //Ddeletes a particular node
  void forward_traverse();    //traverses the doubly-linked list in forward direction
  void backward_traverse();   //traverses the doubly-linked list in backward direction
};

Insertion in a Linked List
Insertion in a linked list occurs at three different positions:

1. Insertion at the beginning of the list

2. Insertion after a particular node.

3. Insertion at the end of the list

Insertion at the beginning
We insert a node at the beginning such that the next pointer points to the node which was at first before. The previous pointer points to NULL.

Insert at start in Doubly Linked List

Here, we have tried to insert M at the beginning.

The pseudo-code for this operation will be:

Insertion_at_beginning(struct Node *Head, int key)
{
    Prev = (struct Node *)malloc(sizeof(struct Node));
    Next = (struct Node *)malloc(sizeof(struct Node));
    temp = (struct Node *)malloc(sizeof(struct Node));
    if(Head == NULL)
        return;
    while(Next->data != NULL)
    {
        temp->data = key;
        temp->Next = Head;
        Head->Prev = temp;
        Head = temp;
        temp->Prev = NULL;
    }
}

Here, we will make use of an extra pointer ‘temp’ to perform the insertion operation.

Insertion at the End

If the list is empty, we will insert a node right after the Head. If the list is not empty, we first need to traverse the whole list to insert a node at the end of the list.

Insertion at end in Doubly Linked List

In the above diagram, we are inserting M at the end.

The function for insertion at the end is:

Insertion_at_end(struct Node *Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct node));  
    Ptr->Next = NULL;  
    Ptr->Prev=NULL;  
    Ptr->data = key;  
    Head = Ptr;  
    Temp = head;   
    while (temp != NULL)  
        temp = temp -> next;   
    temp->Next = Ptr;   
    Ptr->Prev = temp;   
    Ptr->Next = NULL;   
}

Insertion after a particular node
Insertion after a particular node involves traversing all nodes before that node. We will make use of an extra pointer ‘temp’ for traversing the node up to a particular position.

For example, suppose we wish to insert a node having data value ‘M’ between node ‘B’ and node ‘C’, we will do it as follows:

Insert at particular position in Linked List

The function will be:

Insert_after_particular_position(struct Node *Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct node));  //Allocating memory for the new node
    temp = Head;  
    Ptr->data = key;
    for(i=0; i<position; i++)  
   {  
       temp = temp->Next;  
       if(temp == NULL) // i.e. if the list is empty   
             return;  
   }
   Ptr->Next = temp->Next;   
   Ptr->Prev = temp;   
   temp->Next = Ptr;   
   temp->Next->Prev = Ptr;    
}

Deletion from a Linked List:
Deletion involves deleting nodes from the list. It also works in three different cases:

1. Deletion from beginning

2. Deletion at the end

3. Deleting a node other than the first and the last node

Deletion from the beginning:
It involves deleting the first node of the doubly linked list. The following diagram shows the deletion operation at the beginning of the doubly linked list.

Deletion in doubly linked List

The deletion function will be:

Deletion_from_beginning(int key){
    struct Node *Ptr = Head;  
    if (Head == NULL) return;
    Head = Head->Next;
    Head->Prev = NULL;
    free(Ptr);
}

The free function is used to release the memory space. If we don’t release memory after using it, it might lead to memory leakage problems in future.

Deletion at the end:
If the list is empty, we will directly pass the return statement in the function. If the list contains a single node, we just need to make the Head point towards NULL. When the list has two or more nodes, we need to traverse the whole node and then delete the last node.

Delete at the end in Doubly Linked List

Deletion_at_end(int key){
    struct Node *Ptr = Head;  
    if(Head == NULL)  //If the list is empty
        return;
    if(Ptr->Next == NULL)  //If the list has only one element
    {
        Head->Next = NULL;
        return;
    }
    Ptr->Prev->Next = NULL;
    free(ptr);
}

Deletion after a particular node:
If we know the address of a particular node, we can easily delete the node next to it.
For example, suppose we wish to delete node ‘C’ from the list having nodes: ‘A’, ‘B’, ‘C’ and ‘D’. Then, we will do it as follows:

Deletion from Doubly Linked List

The function will be:

Deletion_after_particular_node(int key){
    struct Node *temp = Head;  
    if(Head == NULL)  //If the list is empty
        return;
    if(temp -> Next == NULL)  //If the list has only 1 node 
        return;   
    while(temp->data != key)  //Traversing the list   
        temp = temp->Next; 
    if(temp->Next->Next == NULL)  //If the node to be deleted is the last node
        temp->Next = NULL;  
    Ptr = temp->Next;  
    temp->Next = Ptr->Next;  
    Ptr->Next->Prev = temp;  
    free(ptr);
}

Doubly Linked List as Circular Linked list:
A doubly linked list contains pointers to both the previous and the next node. A circular list does not contain any NULL pointer. In a circular linked list, the ‘Next’ of the last nodes points to the first node of the list.

Combination of a doubly list and a circular list is known as a doubly-circular list. A doubly-circular linked list looks as follows:

Doubly Linked List as Circular Linked list

1. The ‘Next’ pointer of the last node in the doubly-linked list points to the points to the first node in the list.

2. The ‘Prev’ pointer of the first node points to the last node of the linked list.

3. There is no NULL pointer anywhere in the list.

Advantages of a Doubly Linked List:

1. We can traverse a doubly linked list in both forward and backward direction.

2. Traversal in the backward direction makes the deletion operation more efficient. If the pointer to a node is given, we can easily delete the previous node with O’s time complexity O(1).

3. The insertion operation is also more efficient. If the pointer a node is given, we can easily insert a node before that node.

Disadvantages of a Doubly Linked List:

1. A doubly linked list takes more space than a singly list because of the presence of an extra ‘Prev’ pointer at each node.

2. We need to maintain this extra ‘Prev’ pointer while performing all the operations. This increases the space complexity of all the operations performed on a doubly linked list.

Implementation of Doubly Linked List PHP

Representation:
In PHP, doubly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

//node structure

class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head; 

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }
};

Create a Doubly Linked List
Let us create a simple doubly linked list which contains three data nodes.

<?php
//node structure
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head; 

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  } 
};

// test the code  
//create an empty LinkedList
$MyList = new LinkedList();

//Add first node.
$first = new Node();
$first->data = 10;
$first->next = null;
$first->prev = null;
//linking with head node
$MyList->head = $first;

//Add second node.
$second = new Node();
$second->data = 20;
$second->next = null;
//linking with first node
$second->prev = $first;
$first->next = $second;

//Add third node.
$third = new Node();
$third->data = 30;
$third->next = null;
//linking with second node
$third->prev = $second;
$second->next = $third;
?>

Traverse a Doubly Linked List
A doubly linked list can be traversed using a temp node. Keep on moving the temp node to the next one and displaying its content. At the end of the list, the temp node will become NULL.

<?php
//node structure
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head;

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }

  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while($temp != null) {
        echo $temp->data." ";
        $temp = $temp->next;
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }   
};

// test the code  
//create an empty LinkedList 
$MyList = new LinkedList();

//Add first node.
$first = new Node();
$first->data = 10;
$first->next = null;
$first->prev = null;
//linking with head node
$MyList->head = $first;

//Add second node.
$second = new Node();
$second->data = 20;
$second->next = null;
//linking with first node
$second->prev = $first;
$first->next = $second;

//Add third node.
$third = new Node();
$third->data = 30;
$third->next = null;
//linking with second node
$third->prev = $second;
$second->next = $third;

//print the content of list
$MyList->PrintList();   
?>

The above code will give the following output:

The list contains: 10 20 30

Insertion at front

Insertion at end

Insertion at give position

Deletion at front

Deletion at end

Deletion at give position