Doubly Linked Lists (With Code in C, C++, Java, and Python)
Introduction
A doubly linked list is a linear data structure where each node has a link to the next node as well as to the previous node. Each component of a doubly linked list has three components.
prev: It is a pointer that points to the previous node in the list.
data: It holds the actual data.
next: It is a pointer that points to the next node in the list.
Since each node has pointers in both the direction, doubly linked list can be traversed in both forward and backward directions. Figure 1 shows an example of a doubly linked list containing 2 items.
The first node is pointed by a pointer called head and the last node is pointed by a pointer called tail. The first node does not have a previous pointer and the last node does not have the next pointer.
Operations on a doubly linked list
Insert at the head
Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
Set next pointer of the new node to head.
Set the prev pointer of head to the new node.
Set head pointer to the new node.
Insert at the tail
Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
Set next pointer of tail to the new node.
Set prev pointer of the new node to tail.
Set tail pointer to the new node.
Insert at the middle
Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
Seek through the list until you find a node after which you want to insert the new node. Call this node D and node next to it N.
Set D’s next pointer to the new node and new node’s prev pointer to D.
Set the new node’s next pointer to N and N’s prev pointer to the new node.
Find the item in the list
Start with head or tail. Call it curr.
If curr has the item you are looking for, return the item.
Proceeds to the next node. If you started with head use the next pointer to go to the next item otherwise use prev pointer.
Repeat step 2 and 3 until you get null pointer. In case you get to the null pointer, you have come to the end and item is not on the list.
Remove the item at the head
(Note: for all the delete operations, the node needs to be destroyed in order to free the memory. Some languages like Java, Python, etc has a garbage collector that handles this automatically while other languages like C, C++ does not have such a mechanism and programmer has to destroy it explicitly).
Find the next node of the head and call it N.
Set the prev pointer of N to null.
Set both the pointers of the head to null.
Destroy the node pointed by head and set the head pointer to N.
Remove the item at the tail
Find the previous node of the tail and call it N.
Set the next pointer of N to null.
Set both the pointers of the tail to null.
Destroy the node pointed by tail and set the tail pointer to N.
Remove item anywhere in the list
Seek through the list until you found the desired node. Call it D.
Set D’s previous node’s next pointer to D’s next node and set D’s next node’s prev pointer to D’s previous node.
Set both the pointers of D to null.
Destroy the node pointed by D.
Complexities
The table below shows the operation and corresponding complexity of all the operations discussed above.
// C implementation of doubly linked list #include #include
// data structure for Node // data -> the actual value // next -> address of the next node structNode { int data; structNode *next; structNode *prev; };
typedefstructNode *NodePtr;
// global variables head and tail NodePtr head = NULL; NodePtr tail = NULL;
// check if the list is empty intisEmpty(){ return head == NULL; }
// Insert 'value' at the front of the list voidinsertAtFront(int value){ NodePtr node = malloc(sizeof(NodePtr)); node->data = value; node->next = NULL; node->prev = NULL; if (isEmpty()) { head = node; tail = node; } else { node->next = head; head->prev = node; head = node; }
} // insert value at the back of the linked list voidinsertAtBack(int value){ NodePtr node = malloc(sizeof(NodePtr)); node->data = value; node->next = NULL; node->prev = NULL; if (isEmpty()) { head = node; tail = node; } else { tail->next = node; node->prev = tail; tail = node; } } // inserts value after key NodePtr insertAfter(int key, int value){ NodePtr node = malloc(sizeof(NodePtr)); node->data = value; node->next = NULL; node->prev = NULL;
// find the position of key NodePtr currPtr = head; while (currPtr != NULL && currPtr->data != key) { currPtr = currPtr->next; } // if key is not there, raise error if (currPtr == NULL) { printf("%s", "key not found"); } elseif (currPtr->next == NULL) { // if key is the last node, insert right after it currPtr->next = node; node->prev = currPtr; tail = node; } else { // insert between key and item next to key NodePtr nextPtr = currPtr->next; currPtr->next = node; node->prev = currPtr; node->next = nextPtr; nextPtr->prev = node; } } // returns the data at first node inttopFront(){ if (isEmpty()) { printf("%s", "List is empty"); } else { return head->data; } }
// returns the data at last node inttopBack(){ if (isEmpty()) { printf("%s", "List is empty"); } elseif (head->next == NULL) { return head->data; } else { NodePtr currPtr = head; while (currPtr->next != NULL) { currPtr = currPtr->next; } return currPtr->data; } }
// removes the item at front of the linked list and return intpopFront(){ int item; if (isEmpty()) { printf("%s", "List is empty"); return-99999; } else { item = head->data; if (head->next != NULL) { head->next->prev = NULL; } NodePtr next = head->next; free(head); head = next; } return item; }
// remove the item at the list of the linked list and return intpopBack(){ int item; if (isEmpty()) { printf("%s", "List is empty"); return-99999; } else { item = tail->data; if (tail->prev != NULL) { tail->prev->next = NULL; } NodePtr prev = tail->prev; tail->prev = NULL; free(tail); tail = prev;
} return item; }
// removes an item with value 'key' voiddelete(int key){ if (isEmpty()) { printf("%s", "List is empty"); return; } // get to the position of key NodePtr currPtr = head; while(currPtr != NULL && currPtr->data != key) { currPtr = currPtr->next; } if (currPtr == NULL) { printf("%s", "Key is not found in the list"); return; } if (currPtr->prev == NULL) { // this is the first item popFront();
} elseif (currPtr->next == NULL) { // this is the last item popBack();
} else { // anywhere in between first and last NodePtr nextPtr = currPtr->next; NodePtr prevPtr = currPtr->prev; nextPtr->prev = prevPtr; prevPtr->next = nextPtr; currPtr->next = NULL; currPtr->prev = NULL; free(currPtr); currPtr = NULL; } }
// print the linked list voidprint(){ NodePtr currPtr = head; while (currPtr != NULL) { printf("%d", currPtr->data); printf(" "); currPtr = currPtr->next; } printf("\n"); }
// print the linked list voidprintReverse(){ NodePtr currPtr = tail; while (currPtr != NULL) { printf("%d", currPtr->data); printf(" "); currPtr = currPtr->prev; } printf("\n"); }
// check if a key is in the list intfind(int key){ if (isEmpty()) { return0; }
public: MyLinkedList() { head = nullptr; tail = nullptr;
} // Insert 'value' at the front of the list voidinsertAtFront(int value){ NodePtr node = new Node; node->data = value; node->next = nullptr; node->prev = nullptr; if (isEmpty()) { head = node; tail = node; } else { node->next = head; head->prev = node; head = node; } } // insert value at the back of the linked list voidinsertAtBack(int value){ NodePtr node = new Node; node->data = value; node->next = nullptr; if (isEmpty()) { head = node; tail = node; } else { tail->next = node; node->prev = tail; tail = node; } } // inserts value after key voidinsertAfter(int key, int value){ NodePtr node = new Node; node->data = value; node->next = nullptr;
// find the position of key NodePtr currPtr = head; while (currPtr != nullptr && currPtr->data != key) { currPtr = currPtr->next; } // if key is not there, raise error if (currPtr == nullptr) { cout<<"key not found"; } elseif (currPtr->next == nullptr) { // if key is the last node, insert right after it currPtr->next = node; node->prev = currPtr; tail = node; } else { // insert between key and item next to key NodePtr nextPtr = currPtr->next; currPtr->next = node; node->prev = currPtr; node->next = nextPtr; nextPtr->prev = node; } } // returns the data at first node inttopFront(){ if (isEmpty()) { cout<<"List is empty"<<endl; } else { return head->data; } } // returns the data at last node inttopBack(){ if (isEmpty()) { cout<<"List is empty"<<endl; } elseif (head->next == nullptr) { return head->data; } else { NodePtr currPtr = head; while (currPtr->next != nullptr) { currPtr = currPtr->next; } return currPtr->data; } } // removes the item at front of the linked list and return intpopFront(){ int item; if (isEmpty()) { cout<<"List is empty"<<endl; return-99999; } else { NodePtr nextPtr = head->next; if (nextPtr->next != nullptr) { nextPtr->prev = nullptr; } item = head->data; // remove head delete head; // make nextptr head head = nextPtr; } return item; } // remove the item at the list of the linked list and return intpopBack(){ int item; if (isEmpty()) { cout<<"List if empty"<<endl; return-99999; } else { item = tail->data; NodePtr prev = tail->prev; if (prev != nullptr) { prev->next = nullptr; }
tail->prev = nullptr; delete tail; tail = prev; } return item; } // removes an item with value 'key' voidremove(int key){ if (isEmpty()) { cout<<"list is empty"<<endl; return; } // get to the position of key NodePtr currPtr = head; while(currPtr != nullptr && currPtr->data != key) { currPtr = currPtr->next; } if (currPtr == nullptr) { cout<<"Key is not found in the list"<<endl; return; } if (currPtr->prev == nullptr) { // this is the first item popFront(); } elseif (currPtr->next == nullptr) { // this is the last item popBack(); } else { // anywhere in between first and last NodePtr nextPtr = currPtr->next; NodePtr prevPtr = currPtr->prev; nextPtr->prev = prevPtr; prevPtr->next = nextPtr;
// Insert 'value' at the front of the list publicvoidinsertAtFront(int value){ Node node = new Node(value); if(isEmpty()) { head = node; tail = node; } else { node.next = head; head.prev = node; head = node; } }
// insert value at the back of the linked list publicvoidinsertAtBack(int value){ Node node = new Node(value); if (isEmpty()) { head = node; tail = node; } else { tail.next = node; node.prev = tail; tail = node; } }
// inserts value after key publicvoidinsertAfter(int key, int value){ Node node = new Node(value);
// find the position of key Node curr = head; while(null != curr && curr.data != key) { curr = curr.next; }
if (null == curr) { System.out.println("Key not found"); return; }
// removes the item at front of the linked list and return publicintpopFront(){ if (isEmpty()) { System.out.println("List is empty"); return -999999; } int item = head.data; Node next = head.next; if (next != null) { next.prev = null; } head = next; return item; }
// remove the item at the end of the list and return publicintpopBack(){ if (isEmpty()) { System.out.println("List is empty"); return -999999; } int item = tail.data; Node prev = tail.prev; if (prev != null) { prev.next = null; } tail.prev = null; tail = prev; return item; }
// removes an item with value 'key' publicvoidremove(int key){ if (isEmpty()) { System.out.println("List is empty"); return; }
# Insert 'value' at the front of the list definsert_at_front(self, value): node = Node(value) if self.is_empty(): self.head = node self.tail = node else: node.next = self.head self.head.prev = node self.head = node # insert value at the back of the linked list definsert_at_back(self, value): node = Node(value) if self.is_empty(): self.head = node else: self.tail.next = node node.prev = self.tail self.tail = node # inserts value after key definsert_after(self, key, value): node = Node(value)
# find the position of key curr = self.head while curr != Noneand curr.data != key: curr = curr.next
# remove the item at the end of the list and return defpop_back(self): if self.is_empty(): print'List is empty' return
item = self.tail.data prev = self.tail.prev
if prev != None: prev.next = None
self.tail.prev = None self.tail = prev
return item
# removes an item with value 'key' defremove(self, key): if self.is_empty(): print'List is empty' return
# find the position of the key curr = self.head
while curr != Noneand curr.data != key: curr = curr.next
if curr == None: print'key not found' return
# if curr is head, delete the head if curr.prev == None: self.pop_front() elif curr.next == None: # if curr is last item self.pop_back() else: #anywhere between first and last node next_node = curr.next prev_node = curr.prev