Circularly Linked Lists

So far in our discussion of linked lists, we've used one reference to name the head of the list, and another to name the tail. But, we do have another option.

So far, the successor of the tail has, by convention been null. We can use this reference to name the head. In other words, we just change the convention: Instead of "tail.next should contain be null", we force "tail.next should name the first node in the list". If we do this, "tail.getNext()" will return a reference to the head of the list. For a double linked list, we do the same thing with "head.prev": It names the tail node, so head.getPrev() returns a reference to the tail node.

On its face, this saves one reference -- we don't need a tail reference variable. That's not much of a savings -- especially since it will add time-consuming code to set and check the new references. Someone in class mentioned that it saved a special case or two, but it also creates some more. The space-time trade-off certainly doesn't justify a circularly-linked list.

Instead these structures are usually used to represent things that are circular in nature -- where there really isn't a "head" or "tail", per se. Instead, you might modelling a Ferris Wheel, which people board only from the bottom, but where the bottom rotates.

Or, you might imagine a buffer for a device, such as a printer. A normal linked list would need to create and destroy a node for each job, which takes time, and which will eventualyl summon the garbage collector. Another technique is to use a circular buffer, as we did to implement a queue with a vector. The same circular approach can be taken with a linked list -- saving the node creation, destruction, &c.

Sorting and the Comparable/I> interface

The next topic we are going to discuss is sorting: Organizing a list so that its elements are in ascending or descending order by value. This value is determined by the objects stored within the list. Specifically, the list will hold only those objects that implement the Comparable interface, which requires the int compareTo(Comparable otherNode) method. This method compares the node with the otherNode. If otherNode is greater, it returns a negative number. If it, itself, is greater than otherNode, it returns a positive number. If they are equal, it returns 0. This enables nodes to be compared pairwise and placed in order.

Bubble Sort

A bubble sort traverses the array, or a selected portion of the array, length-1 times (a less efficient version of the bubble sort could pass through the array length times and still produce a sorted array). With each pass through the array, the bubble sort compares adjacent values, swapping them if necessary. This actually results in "bubbling" the highest value in the array up to the highest index (length-1) by the end of the first pass through the array, the second-highest value up to the second-highest index (length-2) after the second pass through the array, and so on. By the time the bubble sort has made length-1 passes through the array (or a selected portion of the array), every item, including the lowest item, is guaranteed to be in its proper place in the array.

Let's see how the bubble sort works on an array of integers. We start at the lowest pair of indexes, and work our way up to the highest.

The following shows one entire pass through the array using a bubble sort. Turn your head sideways to the left to read this array. The array indexes are the left-hand, red column. The two adjacent items currently being compared are bold. Note that there are eight total items in the array. Notice that we will make seven comparisons (there are eight columns after the red column) during this first pass.

7 7 7 7 7 7 7 7 9
6 4 4 4 4 4 4 9 7
5 5 5 5 5 5 9 4 4
4 6 6 6 6 9 5 5 5
3 3 3 3 9 6 6 6 6
2 1 1 9 3 3 3 3 3
1 2 9 1 1 1 1 1 1
0 9 2 2 2 2 2 2 2

What has happened to the 9 that started at index 0? It happened to be the highest value in the array, so every time we compared adjacent values we had to swap until the 9 was finally in the last position in the array. After one pass through the array, we have successfully moved the highest value into the highest index.

On our next pass through the array, we'll move the second-highest value into the second-highest index. This time we will stop at the second-to-last pair of values, since we already know that the highest value is at the highest index. The 9 is in blue, since it is already at its proper index.

7 9 9 9 9 9 9 9
6 7 7 7 7 7 7 7
5 4 4 4 4 4 6 6
4 5 5 5 5 6 4 4
3 6 6 6 6 5 5 5
2 3 3 3 3 3 3 3
1 1 2 2 2 2 2 2
0 2 1 1 1 1 1 1

On the second pass through, the second-highest value was already in the second-highest position in the array, but we did move some of the other values one step closer to being in the correct position. Notice that this time, we made only six comparisons (see that there are only seven columns after the red column). There's no need to make the seventh comparison, since the 9 is already in its proper place. 

We continue this process until we have moved every value to the correct index.

Selection Sort

Now let's look at another easy sort, called the selection sort.

In the selection sort, we set up the index so that it points to the "bottom" of the list, and we keep track of where the "top" is. Using the index, we traverse the list and keep track of the lowest value until the index gets to the top. We then swap what is in the top space and lowest value, move the top index down, reset the index to the bottom of the list, and repeat.

Let's take a look at an example. We will start with the same set of numbers we used before. To make the example easier to explain, we'll use an array so that we can refer to the index of a number.

0 1 2 3 4 5 6 7
9 2 1 3 6 5 4 7

So the first step in the selection sort is to get the lowest value into the topmost slot (i.e. index of 0). We will loop through all of the values, keeping track of which slot contains the lowest value. Since we are trying to fill index 0, we will assume that the lowest value is already there unless we find one that is lower - we initialize our best index to be index 0.

As we scan through, we find that the lowest value is the 1 which is at index 2, so we swap the value at index 0 with the value at index 2.

0 1 2 3 4 5 6 7
1 2 9 3 6 5 4 7

Now the lowest value is at index 0, so the next step is to get the next-lowest value into index 1. When we scan through the numbers, we find that the next-lowest value, the 2, is already at index 1, so we do not need to swap.

If we continue through the array one index at a time, we will eventually move every value into the appropriate index, resulting in a sorted array.

Sorting Linked Lists

Since we spoke more recently about linked lists than arrays or Vectors, and expecially since this type of manipulation is good reinforcement for the end-of-semester exam, we'll first discuss implementing these sorts using linked lists -- then come back and discuss the indexed structures.

The "search for the lowest" phase of the sort is very natural in a list structure -- it is a simple linear, forward, traversal. To track the current position and/or the "best so far", we cna just use Node references. So, the only real trick is going to be swapping two nodes of a list.

Swapping the Easy Way

If our Node class allows us to change the data member of a Node, life is grand: 

void swap (Node first, Node second) {

  Comparable tempData = first.getData();
  first.setData(second.getData());
  second.setData(tempData);

}

Making Life More Difficult

But, as you know, neither the doubly-linked or singly linked Node classes we've discussed so far have a setData() method. This makes life a good bit more challenging for us -- we must actually alter the list's structure.

The code here is a little different between a doubly-linked list and a singly linked list -- only because the doubly linked list has an extra reference. Otherwise, the algorithm is the same.

Since the doubly-linked list is more involved, let's consider it -- interpolating for a singly-linked list should be straight-forward enough: 

void swap (Node first, Node second) {

  // Algorithm: If problem, do nothing. Otherwise...
  // Algorithm: Insert each after the other, find predecessors, delete each


  // Special case: Either reference is null -- do nothing
  if ( (null == first) || (null == second) )
    return;

  // Special case: Swap with self -- do nothing
  if (first == second)
    return;


  // Inserting each will require a newNode to represent the new position.
  Node newNode;


  // Insert second after first
  newNode = new Node (first, second.getData(), first.getNext());

  if (null != first.getNext())
    first.getNext().setPrev(newNode);

  first.setNext (newNode); // must do after first.getNext() above. 


  // Insert first after second
  newNode = new Node (second, first.getData(), second.getNext());

  if (null != second.getNext())
    second.getNext().setPrev(newNode);

  second.setNext (newNode); // must do after second.getNext() above. 



  // Find predecessors 
  Node firstPrev = first.getPrev();
  Node secondPrev = second.getPrev();


  // Delete first and second -- replacements are successors

  // Delete first
  if (null == firstPrev) {
    // first was the head node
    head = first.getNext();
    first.getNext().setPrev(null);
  }
  else {
    first.getNext().setPrev (firstPrev);
    firstPrev.setNext (first.getNext());
  }


  // Delete second
  if (null == secondPrev) {
    // second was the head node
    head = second.getNext();
    second.getNext().setPrev(null);
  }
  else {
    seconed.getNext().setPrev (secondPrev);
    secondPrev.setNext (second.getNext());
  }
  
  
  // All done
}