
Doubly linked list: A doubly linked list is a little different from singly-linked lists.
It contains an extra pointer previous which points to the previous node of the linked lists.
Following are the important terms to understand the concept of a doubly-linked list :
- node− Each node of a linked list can store a data called an element.
- next − Each node of a linked list contains a pointer to the next node called next.
- prev− Each node of a linked list contains a pointer to the previous node called prev
Doubly Linked List Representation:
As per the above illustration, the following are the important points to be considered.
- Doubly Linked List contains a pointer element called head.
- Each node carries a data and two pointer fields called next and prev.
- Each node is linked with its next node using its next pointer.
- Each node is linked with its previous node using its previous pointer.
- The last node carries a pointer as null to mark the end of the list.
Creating a node in doubly linked list in C++ :
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node * next; // pointer to the next node in dll
node * prev; // pointer to the previous node in dll
node(int val) // constructor which declares the node.
{
data = val;
next = NULL;
prev = NULL;
}
};
Basic operations on doubly linked lists:
In a doubly-linked list, we perform the following operations:
- Insertion
- Deletion
- Display
Insertion:
In a double-linked list, the insertion operation can be performed in three ways as follows…
- Inserting At Beginning of the list
- Inserting At End of the list
- Inserting At Specific location in the list
Deletion :
In a double-linked list, the deletion operation can be performed in three ways as follows…
- Deleting from Beginning of the list
- Deleting from End of the list
- Deleting a Specific Node
Advantages of a Doubly Linked List
- Allows us to iterate in both directions.
- We can delete a node easily as we have access to its previous node.
- Reversing is easy.
- Can grow or shrink in size dynamically.
Disadvantages of a Doubly Linked List
- They use more memory than arrays because of the storage used by their pointers.
Complete Working Program with all operations:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node * next;
node * prev;
node(int val) {
data = val;
next = NULL;
prev = NULL;
}
};
void insertAtTail(node * & head, int val) {
node * new_node = new node(val);
if (head == NULL) {
head = new_node;
return;
}
node * temp = head;
while (temp -> next != NULL) {
temp = temp -> next;
}
temp -> next = new_node;
new_node -> prev = temp;
}
void insertAtHead(node * & head, int val) {
node * ptr = new node(val);
ptr -> next = head;
if (head != NULL) {
head -> prev = ptr;
}
head = ptr;
}
void insertAtMiddle(node * & head, int val, int pos) {
node * ptr = new node(val);
node * temp = head;
for (int i = 0; i < pos - 2; i++) {
temp = temp -> next;
}
ptr -> next = temp -> next;
temp -> next = ptr;
ptr -> prev = temp;
if (ptr -> next != NULL) {
ptr -> next -> prev = ptr;
}
}
void deleteAtFirst(node * & head) {
node * todelete = head;
head = head -> next;
head -> prev = NULL;
delete todelete;
}
void deleteAtLast(node * & head) {
if (head -> next == NULL) {
deleteAtFirst(head);
return;
}
node * temp = head;
while (temp -> next != NULL) {
temp = temp -> next;
}
temp -> prev -> next = NULL;
free(temp);
}
void deleteAtposition(node * & head, int n) {
if (n == 1) {
deleteAtFirst(head);
return;
}
node * temp = head;
while (temp != NULL && n != 1) {
temp = temp -> next;
n--;
}
temp -> prev -> next = temp -> next;
if (temp -> next != NULL) {
temp -> next -> prev = temp -> prev;
}
}
void display(node * head) {
node * temp = head;
while (temp != NULL) {
cout << temp -> data << "-->";
temp = temp -> next;
}
cout << "NULL\n";
}
int main() {
node * head = NULL;
insertAtTail(head, 2);
insertAtTail(head, 3);
insertAtTail(head, 4);
insertAtTail(head, 5);
insertAtTail(head, 6);
display(head);
insertAtHead(head, 1);
display(head);
insertAtMiddle(head, 7, 2);
display(head);
cout << "delete at the first:\n";
deleteAtFirst(head);
display(head);
cout << "delete at the last:\n";
deleteAtLast(head);
display(head);
cout << "delete at the particular position:\n";
deleteAtposition(head, 3);
display(head);
return 0;
}
Output:
2–>3–>4–>5–>6–>NULL
1–>2–>3–>4–>5–>6–>NULL
1–>7–>2–>3–>4–>5–>6–>NULL
delete at the first:
7–>2–>3–>4–>5–>6–>NULL
delete at the last:
7–>2–>3–>4–>5–>NULL
delete at the particular position:
7–>2–>4–>5–>NULL
Special thanks to Ayush Pandey for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article