6.9 Sorting of Linked Lists

---

As we know from Chapter 3, arrays and linked lists provide two of the most basic ways to structure data, and we considered an implementation of insertion sort for linked lists as a list-processing example in Section 3.4 (Program 3.10). The sort implementations that we have considered to this point all assume that the data to be sorted is in an array and are not directly applicable if we are working within a system that uses linked lists to organize data. In some cases, the algorithms may be useful, but only if they process data in the essentially sequential manner that we can support efficiently for linked lists.

Program 3.10 is a driver program that is similar to Program 6.1 for testing linked-list sorts. As for the array driver, it initializes the list, sorts it, and shows its contents. As discussed in Chapter 3, it is possible to work with linked lists at a higher level of abstraction, but the low-level approach that we are using makes it easier to concentrate on the link manipulations that characterize the algorithms and data structures, our prime focus in this book. It is a straighforward matter to define an interface for lists and build generic implementations like those that we built for arrays in Section 6.2 (see Exercise 6.66).

There is a ground rule for manipulating linked structures that is critical in many applications but not always evident from our code. In a more complex environment, it could be the case that references to the list nodes that we are manipulating are maintained by other parts of the applications system (that is, they are in multilists). The possibility that nodes could be accessed through references that are maintained outside the sort means that our programs should change only links in nodes, and should not alter keys or other information. For example, when we want to do an exchange, it would seem simplest just to exchange items (as we did when sorting arrays). But then any reference to either node through some other link would find the value changed and probably will not have the desired effect. We need to change the links themselves such that the nodes appear in sorted order when the list is traversed via the links we have access to, without affecting their order when accessed via any other links. Doing so makes the implementations more difficult but usually is necessary.

We can adapt insertion, selection, and bubble sort to linked-list implementations, although each one presents amusing challenges. Selection sort is straightforward: We maintain an input list (which initially has the data) and an output list (which collects the sorted result). It is a straightforward exercise in linked-list manipulation to scan through the list to find the maximum element in the input list, remove it from the list, and add it to the front of the output list (see Figure 6.16). An implementation is given in Program 6.19. Program 3.10 gives an implementation of insertion sort for linked lists, and Exercise 6.68 addresses bubble sort. These methods can be useful for sorting short lists, with the same kinds of performance tradeoffs that we found for their array-based counterparts.

Figure 6.16. Linked-list selection sort

This diagram depicts one step of selection sort for linked lists. We maintain an input list, pointed to by h.next, and an output list, pointed to by out (top). We scan through the input list to make max point to the node before (and t point to) the node containing the maximum item. These are the pointers we need to remove t from the input list (reducing its length by 1) and put it at the front of the output list (increasing its length by 1), keeping the output list in order (bottom). Iterating, we eventually exhaust the input list and have the nodes in order in the output list.

Program 6.19 Linked-list selection sort

Selection sort of a linked list is straightforward, but differs slightly from the array version because it is easier to insert at the front of a list. We maintain an input list (pointed to by h.next), and an output list (pointed to by out). While it is nonempty, we scan the input list to find the maximum remaining element, then remove that element from the input list and insert it at the front of the output list. This implementation uses a private method findMax, which returns a link to the node whose link points to the maximum element on a list.

 private static Node findMax(Node h)    {      for (Node t = h; t.next != null; t = t.next)        if (h.next.item < t.next.item) h = t;      return h;    }  static Node sort(Node h)    { Node head = new Node(-1, h), out = null;      while (head.next != null)        { Node max = findMax(head);          Node t = max.next; max.next = t.next;          t.next = out; out = t;        }      return out;    } 

In some list-processing situations, we may not need to explicitly implement a sort at all. For example, we could choose to keep the list in order at all times, inserting new nodes into the list as in insertion sort. This approach comes at little extra cost if insertions are relatively rare, or the list is small, and in certain other situations. For example, we might need to scan the whole list for some reason before inserting new nodes (perhaps to check for duplicates). We shall discuss an algorithm that uses ordered linked lists in Chapter 14, and we shall see numerous data structures that gain efficiency from order in the data in Chapters 12 and 14.

Exercises

6.63 Give the contents of the input list and output list as Program 6.19 is used for the keys A S O R T I N G E X A M P L E.

6.64 Implement a performance-driver client program for linked-list sorts (see Exercise 6.8).

6.65 Implement an exercise-driver client program for linked-list sorts that tests pathological cases (see Exercise 6.9).

6.66 Design a sortable linked-list ADT that includes a method for random initialization, a method for initialization from the standard input stream, a sort method, and an output method. All should take a node reference as a parameter and provide one as a return value in order to support the functional programming style of Program 6.10.

6.67 Write a class that extends your abstract class from Exercise 6.66 to implement linked lists with records that are double keys.

6.68 Implement bubble sort for a linked list. Caution: Exchanging two adjacent elements on a linked list is more difficult than it might seem at first.

6.69 The insertion-sort method used in Program 3.10 makes the linked-list insertion sort run significantly slower than the array version for some input files. Describe one such file, and explain the problem.

6.70 Implement a linked-list version of shellsort that does not use significantly more time or space than the array version for large random files. Hint: Use bubble sort.

6.71 Develop a linked-list implementation for the array ADT interface in Program 6.5 so that, for example, you can use Program 6.6 to debug linked-list sort implementations.

---

Top