[ Data Structures with Java ] Section 10.2 : Doubly Linked Lists (雙向鏈結)

Preface : 
A more flexible linked structure is the doubly linked list whose nodes contain two references that point to the next(successor) and previous (predecessor) node. Such as list has a reference, front, that points to (identifies) the first node in the sequence and a reference, back, that points at the last node in the sequence. You can scan a doubly linked list in both directions. The forward scan starts at front and ends when the link is a reference to back. In the backward direction, simply reverse the process and references : 
 

Doubly Linked Lists Operations : 
Like a singly linked list, a doubly linked list is a sequential structure. However, you can reach an element by starting at the front and moving forward using the reference field next or by starting at back and moving backward using the reference field prev. 
A doubly linked list has clear advantages over a singly linked list. Insert and delete operations need to have only the reference to the node in question. For instance, assume you want to insert a new node at position curr. The operation is a little more complex because you must update both the next and previous references. However, knowing curr, you can access the predecessor node. It is simply curr.previous. Attaching the new node takes four statements instead of two for a singly linked list. The running time is still O(1). 

view plaincopy to clipboardprint?

1. prevNode = curr.prev;  
2. newNode.prev = prevNode;  
3. prevNode.next = newNode;  
4. curr.prev = newNode;  
5. newNode.next = curr;  

 
Deleting the node curr is a two-step process. Link the predecessor of curr to the successor of curr. From curr, you can identify its predecessor prevNode(curr.previous) and its successor succNode (curr.next) : 

view plaincopy to clipboardprint?

1. prevNode = curr.prev;  
2. succNode = curr.next;  
3. succNode.prev = prevNode;   //Statement 1  
4. prevNode.next = succNode;   //Statement 2  

 
We will discuss doubly linked list in detail in Chapter 11. All you need for now is an intuitive understanding of how the lists work. They provide the storage structure for a new List collection called LinkedList. 

Supplement : 
* [ 資料結構 小學堂 ] 鏈結串列 : 雙向鏈結串列