Doubly Linked Lists
Doubly Linked List Conceptually
- A doubly linked list, like a singly linked list, is made up of nodes.
- Each node contains data as well as two links (or pointers) to the nodes following and preceding it in the list.
- The head node is the first node in the list, and the tail node is the last node in the list.
- The previous pointer of the head node is set to null, as is the next pointer of the tail node.
- Real-life example would be simply a college day, room or home is your head of the list and college in the tail of the list, and paths or stops in between are the other nodes.
Operations with doubly linked list
- Adding: In a doubly linked list, adding is a little bit complicated as we have to keep track of next and previous pointers of the nodes and sometimes just of head and tail.
- Adding to the head of the doubly linked list: First, we would need to check if there is a current head in the list. if there isn't then we can simply make our new node both the head and tail of the list. But if it isn't empty then we'd need to cover these steps:
- Set the current's head previous pointer to our new node.
- Set our new node next pointer to the current head.
- Set the previous pointer of our new node to None/null
- Adding to the tail of doubly linked: When adding a node to the tail of a doubly linked list, there are two possibilities. If the list is empty, we make the new node the list's head and tail and set the pointers to null. If the list isn't empty, then:
- Set the current tail’s next pointer to the new tail
- Set the new tail’s previous pointer to the current tail
- Set the new tail’s next pointer to None/null.
- Adding to the head of the doubly linked list: First, we would need to check if there is a current head in the list. if there isn't then we can simply make our new node both the head and tail of the list. But if it isn't empty then we'd need to cover these steps:
- Removing from the list: The removal of the head from a doubly linked list is slightly more difficult than the removal of the head from a singly linked list because of the additional pointer and tail attribute. To delete the list's tail, however, is made much easier because we can do so without having to traverse the full list thanks to the prior pointer and tail property.
- Removing the head: In this, we will update the pointers at the beginning of the list. we'll set the previous pointer of our new head which is the next of our current head to null/None and set our new head as the current head of the list. If the head was also the tail of the list then we'll call the removing tail removal process as well.
- Removing the tail: Similarly, here first we will update the next pointer of our new tail which is right before our current tail to null/None. And set out a new tail as the current tail of the list. if the tail was also the head then, we will call the removing head removal process as well.
- Removing from the middle of the list: As that node is neither at the head nor tail of the list, two pointers must be updated:
- The removed node's preceding node's next pointer must be set to its following node.
- We must set the previous pointer of the removed node's following node to its preceding node.
- There is no need to change the pointers of the removed node, as updating the pointers of its neighboring nodes will remove it from the list.
