Previous Section
 < Free Open Study > 
Next Section


6.2 Doubly Linked Lists

As noted previously, we can use circular linked lists to reach any node in the list from any starting point. Although this structure offers advantages over a simple linear linked list, it remains too limited for certain types of applications. Suppose we want to delete a particular node in a list, given only a pointer to that node (location). This task involves changing the next member of the node preceding Node(location). As we saw in Chapter 5, however, given only the pointer location, we cannot access its predecessor in the list.

Another task that is difficult to perform on a linear linked list is traversing the list in reverse. For instance, suppose we have a list of student records, sorted by grade point average (GPA) from lowest to highest. The dean of students might want a printout of the students' records, sorted from highest to lowest, to use in preparing the Dean's List.

Doubly linked list A linked list in which each node is linked to both its successor and its predecessor

In such a case, where we need to access the node that precedes a given node, a doubly linked list is useful. In a doubly linked list, the nodes are linked in both directions. Each node of a doubly linked list contains three parts:

Info: the data stored in the node

Next: the pointer to the following node

Back: the pointer to the preceding node

Figure 6.7 depicts a linear doubly linked list. Note that the back member of the first node, as well as the next member of the last node, contains a NULL. The following definition might be used to declare the nodes in such a list:

template<class ItemType>
struct NodeType
{
  ItemType info;
  NodeType<ItemType>* next;
  NodeType<ItemType>* back;
}:
Click To expand
Figure 6.7: A linear doubly linked list

Using this definition, let's write member functions InsertItem and DeleteItem using the auxiliary function FindItem.

Finding an Item in a Doubly Linked List

In the FindItem function, we no longer need to use the inchworm search; instead, we can get the predecessor to any node through its back member. We change the FindItem interface slightly. That is, because we no longer need predLoc, we return one pointer, location. If found is true, location points to the node with the same key as item; otherwise, location points to the node that is the logical successor of item. (Recall that FindItem is a function template.)

template<class ItemType>
void FindItem(NodeType<ItemType>* listData, ItemType item,
     NodeType<ItemType>*& location, bool& found)
// Assumption: ItemType is a type for which the operators "<" and
//  "==" are defined-either an appropriate built-in type or a
//  class that overloads these operations.
// Pre:  List is not empty.
// Post: If there is an element someItem whose key matches item's
//       key, then found = true; otherwise, found = false.
//       If found, location contains the address of someItem;
//       otherwise, location contains the address of the logical
//       successor of item.
{
  bool moreToSearch = true;

  location = listData;
  found = false;
  while (moreToSearch && !found)
  {
    if (item < location->info)
      moreToSearch = false; 
    else if (item == location->info)
      found = true;
    else
    {
      location = location->next;
      moreToSearch = (location != NULL);
    }
  }
}

Operations on a Doubly Linked List

The algorithms for the insertion and deletion operations on a doubly linked list are somewhat more complicated than the corresponding operations on a singly linked list. The reason is clear: There are more pointers to keep track of in a doubly linked list.

As an example, consider the InsertItem operation. To link the new node, Node(newNode), after a given node, Node(location), in a singly linked list, we need to change two pointers: newNode->next and location->next (see Figure 6.8a). The same operation on a doubly linked list requires four pointer changes (see Figure 6.8b).

We allocate space for the new node and call FindItem to find the insertion point:

FindItem(listData, item, location, found);

After the return from FindItem, location points to the node that should follow the new node. Now we are ready to link Node(newNode) into the list. Because of the complexity of the operation, you must be careful about the order in which you change the pointers. For instance, when inserting Node(newNode) before Node(location), if we change the pointer in location->back first, we lose our pointer to Node(location)'s predecessor. Figure 6.9 shows the correct order for the pointer changes.

Click To expand
Figure 6.8: Insertions into singly and doubly linked lists
Click To expand
Figure 6.9: Linking the new node into the list

We do have to be careful about inserting an item into an empty list, as it is a special case.

One useful feature of a doubly linked list is its elimination of the need for a pointer to a node's predecessor to delete the node. Through the back member, we can alter the next member of the preceding node to make it jump over the unwanted node. Then we make the back pointer of the succeeding node point to the preceding node.

We do, however, have to be careful about the end cases. If location->back is NULL, we are deleting the first node; if location->next is NULL, we are deleting the last node. If both location->back and location->next are NULL, we are deleting the only node. Figure 6.10 pictures this operation.

Click To expand
Figure 6.10: Deleting from a doubly linked list

We leave the coding of SortedType as a programming assignment.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)