Doubly Linked List Data Structure all Operations | C++ Program to Implement Doubly Linked List
In this tutorial we will understand the working of Doubly Linked List & see all operations of Doubly Linked List. If you don’t know what a Linked List Data Structure is please check this post.
Doubly Linked list is a type of Linked List Data structure which behaves like a two way list/chain. The reason it is called a two way list or two way chain is because we can traverse this list in two directions –
- start from the head node to the end.
- go back in the reverse direction.
As you can see from the diagram, each node object has 1 data field & 2 pointer fields. The data field contains the actual data where as the pointer fields(next & previous pointers) points to the next node & previous node in the doubly linked list. Since the nodes are not stored in contiguous memory locations, these extra pointer fields assists in locating the next & previous nodes in memory. As we have 2 pointers: one pointing to the next node and one pointing to the previous node, we can traverse in 2 directions starting from the head node to the end and vice versa.
Following are the standard Singly Linked List Operations –
- Traverse – Iterate through the nodes in the linked list starting from the head node.
- Append – Attach a new node (to the end) of a list
- Prepend – Attach a new node (to the beginning) of the list
- Insert – attach a new node to a specific position on the list
- Delete – Remove/Delink a node from the list
- Count – Returns the no of nodes in linked list
C++ Program to Implement Doubly Linked List –
#include<iostream>
using namespace std;
class Node {
public:
int key;
int data;
Node * next;
Node * previous;
Node() {
key = 0;
data = 0;
next = NULL;
previous = NULL;
}
Node(int k, int d) {
key = k;
data = d;
}
};
class DoublyLinkedList {
public:
Node * head;
DoublyLinkedList() {
head = NULL;
}
DoublyLinkedList(Node * n) {
head = n;
}
// 1. CHeck if node exists using key value
Node * nodeExists(int k) {
Node * temp = NULL;
Node * ptr = head;
while (ptr != NULL) {
if (ptr - > key == k) {
temp = ptr;
}
ptr = ptr - > next;
}
return temp;
}
// 2. Append a node to the list
void appendNode(Node * n) {
if (nodeExists(n - > key) != NULL) {
cout << "Node Already exists with key value : " << n - > key << ". Append another node with different Key value" << endl;
} else {
if (head == NULL) {
head = n;
cout << "Node Appended as Head Node" << endl;
} else {
Node * ptr = head;
while (ptr - > next != NULL) {
ptr = ptr - > next;
}
ptr - > next = n;
n - > previous = ptr;
cout << "Node Appended" << endl;
}
}
}
// 3. Prepend Node - Attach a node at the start
void prependNode(Node * n) {
if (nodeExists(n - > key) != NULL) {
cout << "Node Already exists with key value : " << n - > key << ". Append another node with different Key value" << endl;
} else {
if (head == NULL) {
head = n;
cout << "Node Prepended as Head Node" << endl;
} else {
head - > previous = n;
n - > next = head;
head = n;
cout << "Node Prepended" << endl;
}
}
}
// 4. Insert a Node after a particular node in the list
void insertNodeAfter(int k, Node * n) {
Node * ptr = nodeExists(k);
if (ptr == NULL) {
cout << "No node exists with key value: " << k << endl;
} else {
if (nodeExists(n - > key) != NULL) {
cout << "Node Already exists with key value : " << n - > key << ". Append another node with different Key value" << endl;
} else {
Node * nextNode = ptr - > next;
// inserting at the end
if (nextNode == NULL) {
ptr - > next = n;
n - > previous = ptr;
cout << "Node Inserted at the END" << endl;
}
//inserting in between
else {
n - > next = nextNode;
nextNode - > previous = n;
n - > previous = ptr;
ptr - > next = n;
cout << "Node Inserted in Between" << endl;
}
}
}
}
// 5. Delete node by unique key. Basically De-Link not delete
void deleteNodeByKey(int k) {
Node * ptr = nodeExists(k);
if (ptr == NULL) {
cout << "No node exists with key value: " << k << endl;
} else {
if (head - > key == k) {
head = head - > next;
cout << "Node UNLINKED with keys value : " << k << endl;
} else {
Node * nextNode = ptr - > next;
Node * prevNode = ptr - > previous;
// deleting at the end
if (nextNode == NULL) {
prevNode - > next = NULL;
cout << "Node Deleted at the END" << endl;
}
//deleting in between
else {
prevNode - > next = nextNode;
nextNode - > previous = prevNode;
cout << "Node Deleted in Between" << endl;
}
}
}
}
// 6th update node
void updateNodeByKey(int k, int d) {
Node * ptr = nodeExists(k);
if (ptr != NULL) {
ptr - > data = d;
cout << "Node Data Updated Successfully" << endl;
} else {
cout << "Node Doesn't exist with key value : " << k << endl;
}
}
// 7th printing
void printList() {
if (head == NULL) {
cout << "No Nodes in Doubly Linked List";
} else {
cout << endl << "Doubly Linked List Values : ";
Node * temp = head;
while (temp != NULL) {
cout << "(" << temp - > key << "," << temp - > data << ") <--> ";
temp = temp - > next;
}
}
}
};
int main() {
DoublyLinkedList obj;
int option;
int key1, k1, data1;
do {
cout << "\nWhat operation do you want to perform? Select Option number. Enter 0 to exit." << endl;
cout << "1. appendNode()" << endl;
cout << "2. prependNode()" << endl;
cout << "3. insertNodeAfter()" << endl;
cout << "4. deleteNodeByKey()" << endl;
cout << "5. updateNodeByKey()" << endl;
cout << "6. print()" << endl;
cout << "7. Clear Screen" << endl << endl;
cin >> option;
Node * n1 = new Node();
//Node n1;
switch (option) {
case 0:
break;
case 1:
cout << "Append Node Operation \nEnter key & data of the Node to be Appended" << endl;
cin >> key1;
cin >> data1;
n1 - > key = key1;
n1 - > data = data1;
obj.appendNode(n1);
//cout<<n1.key<<" = "<<n1.data<<endl;
break;
case 2:
cout << "Prepend Node Operation \nEnter key & data of the Node to be Prepended" << endl;
cin >> key1;
cin >> data1;
n1 - > key = key1;
n1 - > data = data1;
obj.prependNode(n1);
break;
case 3:
cout << "Insert Node After Operation \nEnter key of existing Node after which you want to Insert this New node: " << endl;
cin >> k1;
cout << "Enter key & data of the New Node first: " << endl;
cin >> key1;
cin >> data1;
n1 - > key = key1;
n1 - > data = data1;
obj.insertNodeAfter(k1, n1);
break;
case 4:
cout << "Delete Node By Key Operation - \nEnter key of the Node to be deleted: " << endl;
cin >> k1;
obj.deleteNodeByKey(k1);
break;
case 5:
cout << "Update Node By Key Operation - \nEnter key & NEW data to be updated" << endl;
cin >> key1;
cin >> data1;
obj.updateNodeByKey(key1, data1);
break;
case 6:
obj.printList();
break;
case 7:
system("cls");
break;
default:
cout << "Enter Proper Option number " << endl;
}
} while (option != 0);
return 0;
}