We employ a very simple, straightforward design for singly linked lists. The reference front points to the first node in sequence and constant null indicates the end of the list. Borrowing from the notion of index range in an array, singly linked list have a reference range [front, null). In designing a doubly linked list, we are going to add features that take full advantage of the bidirectional references in a DNode object. A doubly linked list contains a sentinel nodecalled header. The sentinel is a DNode object containing a null data value. A linked list algorithm never use this value. The actually data items in the list begin with the successor of the header node. The first node in the list has reference header.next. The successor of the last node in the list is the header. That is , the next field in the last node has the value header. In a similar way, the prev field in the header references the last node in the list. In this way, a doubly linked list is circular. You can think of this as a watch with a band consisting of detachable links. The header is the clock face, and the actual nodes are the links in the band.
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 :
DNode
The result of the declaration is an empty list with a single header node and reference values that point to the header itself.
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 :
- if(header.next == header || header.prev == header) {
- // Empty Circular Doubly linked list
- }
Updating a Doubly Linked List :
The ability to add and remove elements efficiently is the key motivation behind the design of doubly linked list. In this section, we develop the algorithms for general insert and delete operations at any position in the list. The methods addBefore() and remove() implements all of the reference updates to link and unlink a node. The presence of a header allows a programmer to use these methods without modification when adding or removing nodes at the ends of the list. You don't want to lost sight of this fact. Unlike a singly linked list, which requires separate algorithms to add and remove an element at the front or back of the list, the same operation for a doubly linked list can be implemented easily by using only the general addBefore() and remove methods.
- The addBefore() Method
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 :
- 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 :
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").
Supplement :
* [ 資料結構 小學堂 ] 鏈結串列 : 環狀鏈節串列
沒有留言:
張貼留言