## 2011年2月9日 星期三

### [ Data Structures with Java ] Section 11.2 : Circular Doubly Linked Lists

Preface :
Each node in a doubly linked list, including the header node, has a unique successor and a unique predecessor referenced by the link fields next and prev, respectively. The role of the header is fundamental to a doubly linked list. With its link field next, the header references the first real node in the list. With its link field prev, the header references the last real node in the list. Below is a figure illustrates a list of four integer nodes whose order is 4, 9, 2, 3 from front to back :

Declaring a Doubly Linked List :
The header node defines a doubly linked list. As a result, the declaration of the list begins with the declaration of the header node. With the default constructor in the DNode class, we create an object with a null data value and with link fields that reference the node itself. The default constructor is primarily used to create a header node :

The result of the declaration is an empty list with a single header node and reference values that point to the header itself.

- DNode default constructor :
1. public DNode(){
2.     dataValue = null;
3.     next = this;
4.     prev = this;
5. }

Note the difference between the declaration of a singly linked list and that of a doubly linked list. You can test for an empty singly linked list by comparing front with null. The comparison for a doubly linked list tests whether header.next or header.prev is the header node :

2.     // Empty Circular Doubly linked list
3. }

Updating a Doubly Linked List :

The insert operation adds a new element at a designated reference location in the list. The algorithm creates a new node and adds it to the list immediately before the designated node. The method addBefore() takes a DNode reference argument curr and the value item as arguments. The return value is a reference to the new node. The algorithm involves only updating four links, so the algorithm has running time O(1). Use the accompanying figure to trace the update of the links. We include addBefore() as a static method in the DNode class :

1. public static  DNode addBefore(DNode curr, T item) {
2.     DNode newNode = new DNode(item);
3.     DNode prevNode = curr.prev;
4.     newNode.prev = prevNode;
5.     newNode.next = curr;
6.     prevNode.next = newNode;
7.     curr.prev = newNode;
8.     return newNode;
9. }

- The remove() Method :
The method remove() deletes an element at a specified element location. The algorithm involves updating links in the adjacent successor and predecessor nodes. The methods takes a DNode reference curr as an argument. If curr points back to itself (curr.next = curr), curr is the header node of an empty list, and the method simply returns. The method assumes that the programmer will not attempt to delete header in the case of a nonempty list. The efficiency of the operation derives from the fact that node reference curr can identify both its predecessor and successor nodes. The update of the links requires only two statements, so remove() has running time O(1). Use the accompanying figure to trace the algorithm. We include remove() as a static method in the DNode class :

- Method remove() implementation :
1. public static  void remove(DNode curr) {
2.     if(curr.next == curr) return;
3.     DNode prevNode = curr.prev;
4.     DNode succNode = curr.next;
5.     prevNode.next = succNode;
6.     succNode.prev = prevNode;
7. }

Modifying the Ends of a List :
If a singly linked list, operations that insert or delete nodes at the ends of the list require distinct algorithms. Because doubly linked list is a circular list with a header node, update operations at the ends of the list simply use addBefore() and remove() with arguments that are reference fields in the header.
Adding or removing a node at the front of a list involves calling addBefore() or remove() with reference argument header.next. The insertion occurs immediately before the first node, with the reference value next in the header pointing to the new node. The method remove() deletes the current front node in the list and updates the header to point at a new first node :

With the realization that the header identifies the back of the list, the algorithm to add a node at the back involves calling addBefore() with the header as the reference argument. The operation adds the node immediately before the header, or at the back of the list. A call to the method remove() with reference argument header.prev deletes the last node in the list.

Application : World Jumble
You are familiar with crossword puzzles and other word discovery challenges in the local newspaper. One such challenge is the Word Jumble. The letters in a word appear in random order, and you have to find the reordering that produces the original word. This application uses the static methods in DNodes class to create a simplified word jumble game. The method jumbleLetters() implements the key algorithm. It takes a string argument and returns a jumbled string with the letters in random order. The method uses a doubly linked list of Character nodes to store the letters. For each letter in the original string, a random integer 0 or 1 determines whether the letter should be added at the front or at the back of the list. If the number is 0, the method inserts the character at the front of the list; otherwise, it inserts it at the back of the list. For instance, the string "tank" and the random sequence 1001 create the jumbled list of character n-a-t-k ("natk").

- Method jumbleLetters() implementation :
1. public static String jumbleLetters(String word) {
2.     DNode jumberWordHeader = new DNode();
3.     Random rnd = new Random();
4.     int index;
5.     for(int i=0; i
6.         index = rnd.nextInt(2);
7.         switch(index){
8.         case 0:
10.             break;
11.         case 1:
13.             break;
14.         }
15.     }
16.