871249. Doubly Linked List Traversal
Doubly Linked List Traversal
Summary
Displaying a doubly linked list means traversing from both ends (beginning and end) of the list. This problem requires implementing an algorithm to print or display nodes in a doubly linked list, where each node has references to its previous and next elements.
Detailed Explanation
The approach to traverse a doubly linked list is straightforward. We will use two pointers, one starting from the beginning of the list (head) and another starting from the end of the list (tail). The head pointer moves towards the tail while the tail pointer moves towards the head. At each step, we print or display the current node.
Here's a step-by-step breakdown:
- Initialize two pointers,
headandtail, to the beginning and end of the doubly linked list, respectively. - While
headis not equal totail, move theheadpointer one step towards thetailby incrementing its reference to the next node, and move thetailpointer one step towards theheadby decrementing its reference to the previous node. - At each iteration, print or display the current node (i.e., the node pointed to by
headortail). - Continue until
headmeetstail, indicating that all nodes in the list have been traversed.
The time complexity for this algorithm is O(n), where n is the number of nodes in the doubly linked list, as we visit each node exactly once. The space complexity is O(1) since we only use a constant amount of space to store the pointers and variables.
Optimized Solutions
Java
public void printDoublyLinkedList(Node head, Node tail) {
while (head != tail) {
System.out.println(head.data);
head = head.next;
tail = tail.prev;
}
}