Previous Section
 < Free Open Study > 
Next Section


6.1 Circular Linked Lists

The linked list data structures that we implemented in Chapter 5 are characterized by a linear (line-like) relationship between the elements: Each element (except the first one) has a unique predecessor, and each element (except the last one) has a unique successor. Using linear linked lists does present a problem: Given a pointer to a node anywhere in the list, we can access all the nodes that follow but none of the nodes that precede it. With a singly linked linear list structure (a list whose pointers all point in the same direction), we must always have a pointer to the beginning of the list to be able to access all the nodes in the list.

In addition, the data we want to add to a sorted list may already be in order. Sometimes people manually sort raw data before turning it over to a data entry clerk. Likewise, data produced by other programs are often in some order. Given a Sorted List ADT and sorted input data, we always insert new items at the end of the list. It is ironic that the work done manually to order the data now results in maximum insertion times.

We can, however, change the linear list slightly, making the pointer in the next member of the last node point back to the first node instead of containing NULL (Figure 6.1). Now our list becomes a circular linked list rather than a linear linked list. We can start at any node in the list and traverse the entire list. If we let our external pointer point to the last item in the list rather than the first, we have direct access to both the first and the last elements in the list (Figure 6.2). listData->info references the item in the last node, and listData-> next->info references the item in the first node. We mentioned this type of list structure in Chapter 5, when we discussed circular linked queues.

Click To expand
Figure 6.1: A circular linked list
Click To expand
Figure 6.2: Circular linked lists with the external pointer pointing to the rear element

Circular linked list A list in which every node has a successor; the "last" element is succeeded by the "first" element

We do not need to change any of the declarations in the class SortedType to make the list circular, rather than linear. After all, the members in the nodes are the same; only the value of the next member of the last node has changed. How does the circular nature of the list alter the implementations of the list operations? Because an empty circular list has a NULL pointer, the IsEmpty operation does not change at all. However, using a circular list requires an obvious change in the algorithms that traverse the list. We no longer stop when the traversing pointer becomes NULL. Indeed, unless the list is empty, the pointer never becomes NULL. Instead, we must look for the external pointer itself as a stop sign. Let's examine these changes in the Sorted List ADT.

Finding a List Item

The RetrieveItem, InsertItem, and DeleteItem operations all require a search of the list. Rather than rewriting each of these with minor variations, let's write a general FindItem routine that takes item as a parameter and returns location, predLoc, and found. InsertItem and DeleteItem need the location of the predecessor node (predLoc); RetrieveItem can just ignore it.

In the linear list implementation, we searched the list using a pair of pointers, location and predLoc. (Remember the inchworm?) We modify this approach slightly for the circular list. In the linear list version, we initialized location to point to the first node in the list and set predLoc to NULL (Figure 6.3a). For the circular list search, we initialize location to point to the first node and predLoc to point to its "predecessor''-the last node in the list (Figure 6.3b).

The search loop executes until (1) a key greater than or equal to the item's key is encountered, or (2) we reach the "end" of the list. In a linear list, the end of the list is detected when location equals NULL. Because the external pointer to the list points to the last element, we know we have processed all of the items and not found a match when location points to the first element again: location = listData->next. Because it makes no sense to search an empty list, let's make it a precondition that the list is not empty. Because we now have overloaded the relational operators "<" and "==", we use them in our algorithm.

Click To expand
Figure 6.3: Initializing for FindItem

Following the execution of the loop, if a matching key is found, location points to the list node with that key and predLoc points to its predecessor in the list (Figure 6.4a). Note that if item's key is the smallest key in the list, then predLoc points to its predecessor-the last node in the circular list (Figure 6.4b). If item's key is not in the list, then predLoc points to its logical predecessor in the list and location points to its logical successor (Figure 6.4c). Notice that predLoc is correct even if item's key is greater than any element in the list (Figure 6.4d). Thus predLoc is set correctly for inserting an element whose key is larger than any currently in the list.

Click To expand
Figure 6.4: The FindItem operation for a circular list

The following C++ code implements our FindItem algorithm as a function template. Notice two things in the function heading. First, NodeType was defined in Chapter 5 as a struct template, so each declaration using NodeType must include an actual parameter (the name of a data type) in angle brackets. For example, listData is declared in the code to be of type NodeType<ItemType>* and not simply NodeType*. Second, observe the syntax for the declarations of location and predLoc. You see an asterisk (*) and an ampersand (&) next to each other. Although this syntax may look strange at first, it is consistent with the usual way we indicate passing-by-reference: Place an & after the data type of the parameter. Here we place an & after the data type NodeType<ItemType>*, which is a pointer to a node.

template<claas ItemType>
void FindItem(NodeType<ItemType>* listData, ItemType item,
     NodeType<ItemType>*& location, NodeType<ItemType>*& predLoc,
     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 and
//       predLoc contains the address of someItem's predecessor:
//       otherwise, location contains the address of item's logical
//       successor and predLoc contains the address of item's
//       logical predecessor.
{
  bool moreToSearch = true;

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

Note that FindItem is not a member function of the class SortedType. It is an auxiliary or "helper" operation, hidden within the implementation, that is used by SortedType member functions.

Inserting Items into a Circular List

The algorithm to insert an element into a circular linked list is similar to that for the linear list insertion.

The task of allocating space is the same as that carried out for the linear list. We allocate space for the node using the new operator and then store item into newNode-> info. The next task is equally simple; we just call FindItem:

FindItem(listData, item, location, predLoc, found);

Of course, we do not find the element because it isn't there; it is the predLoc pointer that interests us. The new node is linked into the list immediately after Node(predLoc). To put the new element into the list, we store predLoc->next into newNode->next and newNode into predLoc->next.

Figure 6.5(a) illustrates the general case. What are the special cases? First, we have the case of inserting the first element into an empty list. In this case, we want to make listData point to the new node, and to make the new node point to itself (Figure 6.5b). In the insertion algorithm for the linear linked list, we also had a special case when the new element key was smaller than any other key in the list. Because the new node became the first node in the list, we had to change the external pointer to point to the new node. The external pointer to a circular list, however, doesn't point to the first node in the list-it points to the last node. Therefore, inserting the smallest list element is not a special case for a circular linked list (Figure 6.5c). However, inserting the largest list element at the end of the list is a special case. In addition to linking the node to its predecessor (previously the last list node) and its successor (the first list node), we must modify the external pointer to point to Node(newNode)-the new last node in the circular list (Figure 6.5d).

The statements to link the new node to the end of the list are the same as those for the general case, plus the assignment of the external pointer, listData. Rather than checking for this special case before the search, we can treat it together with the general case: Search for the insertion place and link in the new node. Then, if we detect that we have added the new node to the end of the list, we reassign listData to point to the new node. To detect this condition, we compare item to listData->info.

The resulting implementation of InsertItem is shown here.

template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
  NodeType<ItemType>* newNode;
  NodeType<ItemType>* predLoc;
  NodeType<ItemType>* location;
  bool found;

  newNode = new NodeType<ItemType>;
  newNode->info = item;
  if (listData != NULL)
  {
    FindItem(listData, item, location, predLoc, found);
    newNode->next = predLoc->next;
    predLoc->next = newNode:

    // If this is last node in list, reassign listData.
    if (listData->info < item)
      listData = newNode;
  }
  else       // Inserting into an empty list.
  {
    listData = newNode;
    newNode->next = newNode;
  }
  length++;
}

Click To expand
Figure 6.5: Inserting into a circular linked list

Deleting Items from a Circular List

To delete an element from the circular linked list, we use the same general algorithm we developed for the linear list:

For the first task, we use FindItem. After the return from FindItem, location points to the node we wish to delete, and predLoc points to its predecessor in the list. To remove Node(location) from the list, we simply reset predLoc->next to jump over the node we are deleting. That works for the general case, at least (see Figure 6.6a).

What kind of special cases do we have to consider? In the linear list version, we had to check for deleting the first (or first-and-only) element. From our experience with the insertion operation, we might surmise that deleting the smallest element (the first node) of the circular list is not a special case; Figure 6.6(b) shows that guess to be correct. However, deleting the only node in a circular list is a special case, as we see in Figure 6.6(c). The external pointer to the list must be set to NULL to indicate that the list is now empty. We can detect this situation by checking whether predLoc equals location after the execution of FindItem; if so, the node we are deleting is the only one in the list.

We might also guess that deleting the largest list element (the last node) from a circular list is a special case. As Figure 6.6(d) illustrates, when we delete the last node, we first do the general-case processing to unlink Node(location) from the list, then we reset listData to point to its predecessor, Node(predLoc). We can detect this situation by checking whether location equals listData after the search.

Click To expand
Figure 6.6: Deleting from a circular linked list
template<class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
{
  NodeType<ItemType>* location;
  NodeType<ItemType>* predLoc ;
  bool found;

  FindItem(listData, item, location, predLoc, found);
  if (predLoc == location) // Only node in list?
    listData = NULL;
  else
  {
    predLoc->next = location->next;
    if (location == listData)  // Deleting last node in list?
      listData = predLoc;
  }
  delete location;
  length-- ;
}

Having worked through a number of the list operations in detail, we leave the circular implementation of the other Sorted List ADT operations as a programming assignment. None of the operations we have looked at so far has become shorter or much simpler when the implementation changed to a circular list. Why, then, might we want to use a circular, rather than linear, linked list? Circular lists are useful for applications that require access to both ends of the list. (The circular linked version of the queue in Chapter 5 is a good example of this scenario.)



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