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 –
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 | #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; } |