Doubly Linked Lists in C++

In this tutorial, we will learn about Doubly Linked Lists in C++.

We will learn the following –

  • What are Doubly Linked Lists(DLL)?
  • Advantages and disadvantages of DLL of Singly Linked Lists?
  • Different operations on DLL

What are Doubly Linked Lists?

Once we know about Singly linked lists, this is very easy to understand.
Doubly linked lists contain one data element and 2 references. One reference points to the next element and the other reference points to the previous element.

struct Node 
{ 
int data; 
struct Node *prev; 
struct Node *next; 
};

The first node is called the Head. And the previous pointer of the Head node points to NULL. The next pointer of the Head node points to the next node in the list. Similarly, the next pointer of the last node in the list points to NULL and the previous pointer of the last node points to it’s previous data element, as it’s shown in the image.

Doubly Linked Lists in C++

Advantages and disadvantages of Doubly Linked List over Singly Linked List

Advantages – 

  1. A DLL can be traversed in both ways.
  2. Insertion and deletion in a DLL are much faster. When the previous node of the node is known, it’s easier to insert and delete because we don’t have to traverse the whole list from the head node.

Disadvantages – 

  1. DLL takes up more memory because of the extra pointer.
  2. Extra operations have to be done for every insertion or deletion of an element. We need to modify the previous pointers with the next pointer. These might take up some extra computation power if the list is very large.

Different operations on Doubly Linked List in C++

Insertion –

We insert an element almost the same way as we do it in Singly Linked List(SLL).
The function insert() inserts the data element into the beginning of the Doubly Linked List. It creates a new Node and inserts the data element in the data field of the newnode. Then the previous pointer in new Node points to NULL, as it is entered at the beginning and the next pointer points to the head. If the head is not NULL, then the previous pointer of head points to the new Node. Finally, the head is the new Node. That is, the linked list starts from there.

The following code shows how it’s done –

void insert(int data) 
{ 
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); 
   new_node->data  = data; 
   new_node->prev = NULL; 
   new_node->next = head;     
   if(head !=  NULL) 
      head->prev = new_node ;     
   head = new_node; 
}

Deletion – 

To delete an element in the starting of a Doubly Linked List, we first give the head node pointer to another temp pointer. And then we assign the head->next pointer as the head because we have to remove the first element. Then, we point temp->next as NULL because temp holds the older head pointer. Lastly, we free the temp pointer because we don’t want to waste memory or cause memory leaks.

The following code shows how it’s done –

void delete() 
{ 
   struct Node* temp = (struct Node*) malloc(sizeof(struct Node)); 
   temp = head;
   head = head->next;
   temp->next = NULL;
   free(temp);
}

Display – 

Display method is the same as it is in the SLL. To display, we traverse the whole list until node->next is NULL. We stop there as we have encountered the last element of the list.

The following code shows the traversal –

void display() 
{ 
  struct Node* temp = head; 
  while (temp != NULL) 
  { 
    cout<< temp->data <<" "; 
    temp = temp->next; 
  } 
}

 

Read more articles:

Leave a Reply

Your email address will not be published. Required fields are marked *