Doubly Linked List: Structure and Basic Operations

Introduction and Basics of Doubly Linked List

A Doubly Linked List (DLL) is a linear data structure where each node stores data along with two pointers. One pointer points to the previous node, while the other points to the next node. This two-way connection allows traversal in both forward and backward directions.

Each node contains:

• Data → Stores the value.

• Prev Pointer → Points to the previous node.

• Next Pointer → Points to the next node.

Example:

NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL

Here, 10 is the head node and 40 is the tail node.

1. Convert Array to Doubly Linked List

Given an array of integers, create a Doubly Linked List containing the same elements in the same order. Every node should maintain links to both its previous and next nodes.

Algorithm

• Check whether the array is empty because no linked list can be created without elements.

• Create the first node using the first array element and mark it as the head node of the DLL.

• Maintain a pointer to the most recently created node because future nodes must be connected with it.

• Traverse the remaining array elements one by one and create a new node for each value.

• Connect the new node with the previous node by updating both the next and prev pointers.

• Move the tracking pointer to the newly created node and continue until all array elements are processed.

Time Complexity: O(N) because every array element is used exactly once to create a DLL node.

Space Complexity: O(N) because N nodes are created for the resulting Doubly Linked List.

2. Insert Before Head

Given a Doubly Linked List and a value X, insert a new node before the current head node and make it the new head of the list.

Algorithm

• Create a new node containing the value X.

• Check whether the DLL is empty because the new node becomes the head if no nodes exist.

• Connect the new node's next pointer to the current head node.

• Update the current head node's previous pointer so that it points back to the new node.

• Move the head pointer to the newly created node because it is now the first node.

• Return the updated head pointer.

Time Complexity: O(1) because only a fixed number of pointer updates are performed.

Space Complexity: O(1) auxiliary space because no additional data structure is used.

3. Insert Before Tail

Given a Doubly Linked List and a value X, insert a new node immediately before the tail node.

Algorithm

• Check whether the DLL contains fewer than two nodes because special handling may be required.

• Traverse the DLL until the tail node is reached.

• Create a new node containing the given value.

• Locate the node immediately before the tail because insertion will happen between these two nodes.

• Update the previous and next pointers of all affected nodes so that the new node becomes part of the chain.

• Return the head pointer of the updated DLL.

Time Complexity: O(N) because reaching the tail may require traversing the list.

Space Complexity: O(1) because only a few pointers are maintained.

4. Insert Before Kth Node

Given a Doubly Linked List, a position K, and a value X, insert a new node immediately before the Kth node.

Algorithm

• Check whether K equals 1 because insertion before the first node is a head insertion operation.

• Traverse the DLL until the Kth node is reached.

• Create a new node containing the value that needs to be inserted.

• Connect the new node with the node before the Kth node using both previous and next pointers.

• Connect the new node with the Kth node so that all links remain valid.

• Return the updated head pointer after insertion.

Time Complexity: O(N) because locating the Kth node may require traversal.

Space Complexity: O(1) because only constant extra memory is used.

5. Insert Before Given Node

Given a pointer to a node in a Doubly Linked List and a value X, insert a new node immediately before that node.

Algorithm

• Create a new node containing the value X.

• Identify the node that exists immediately before the given node.

• Connect the new node with the previous node through both pointer directions.

• Connect the new node with the given node through both pointer directions.

• Update the surrounding node pointers so the DLL remains connected.

• Return the head pointer if required by the problem.

Time Complexity: O(1) because the target node is already provided.

Space Complexity: O(1) because only pointer modifications are performed.

6. Delete Head Node

Given a Doubly Linked List, delete the first node and return the updated head.

Algorithm

• Check whether the DLL is empty because deletion cannot be performed without nodes.

• Store the current head node temporarily because it will be removed.

• Move the head pointer to the next node in the DLL.

• If a new head exists, set its previous pointer to NULL because it becomes the first node.

• Delete the old head node safely from memory.

• Return the updated head pointer.

Time Complexity: O(1) because deletion occurs directly at the beginning of the DLL.

Space Complexity: O(1) because only temporary pointers are used.

7. Delete Tail Node

Given a Doubly Linked List, remove the last node and return the modified list.

Algorithm

• Check whether the DLL is empty because there is nothing to delete.

• If only one node exists, delete it and return NULL.

• Traverse the DLL until the tail node is reached.

• Identify the node immediately before the tail because it will become the new tail.

• Disconnect the current tail node by updating both pointer links.

• Delete the tail node and return the head pointer.

Time Complexity: O(N) because reaching the tail may require traversal.

Space Complexity: O(1) because only temporary pointers are maintained.

8. Delete Kth Node

Given a Doubly Linked List and an integer K, delete the node present at position K.

Algorithm

• Check whether the DLL is empty because no deletion can be performed.

• If K equals 1, perform head deletion directly.

• Traverse the DLL until the Kth node is reached.

• Identify both the previous and next nodes surrounding the Kth node.

• Connect the surrounding nodes directly using both pointer directions.

• Delete the Kth node and return the updated head pointer.

Time Complexity: O(N) because locating the Kth node may require traversal.

Space Complexity: O(1) because only a few pointers are used.

9. Delete Given Node

Given a pointer to a node in a Doubly Linked List, delete that node while maintaining all valid DLL connections.

Algorithm

• Identify the previous node and next node connected to the given node.

• Check whether either side is missing because the given node may be the head or tail.

• Connect the previous node directly to the next node by updating the next pointer.

• Connect the next node back to the previous node by updating the previous pointer.

• Remove the given node safely from memory.

• Ensure all neighboring links remain valid after deletion.

Time Complexity: O(1) because the target node is directly available.

Space Complexity: O(1) because only pointer modifications are performed.