sortablelinkedlist.java

来自「java版的数据结构的完全代码 免费提供了 学习数据结构的请下载」· Java 代码 · 共 39 行

// Introduced in Chapter 8
/** A linked List of Comparables. */
public class SortableLinkedList<E extends Comparable<E>>
  extends LinkedList<E> {

  /** Add target in order, assuming this List is currently sorted. */
  protected void addInOrder(E target) {
    Predecessor<E> prev = this;
    ListNode<E> node = getNext();
    while ((node != null)
		  && (node.getItem().compareTo(target) < 0)) {
      prev = node;
      node = node.getNext();
    }
    prev.setNext(new ListNode<E>(target, node));
  }

  /** Arrange the elements in this List from smallest to largest. */
  public void insertionSort() {
    SortableLinkedList<E> newList = new SortableLinkedList<E>();
    for (E e : this) {
      newList.addInOrder(e);
    }
    setNext(newList.getNext());
  }
  
  public static void main(String[] args) {
    SortableLinkedList<String> ls = new SortableLinkedList<String>();
    ls.add("command-line-args-please");
    for (String s : args) {
      ls.add(s);
    }
    System.out.println(ls);
    ls.insertionSort();
    System.out.println(ls);
  }

}