exercise17_3.java

来自「java程序设计 机械工业出版社 书籍代码」· Java 代码 · 共 171 行

public class Exercise17_3 {
  public static void main(String[] args) {
    GenericLinkedList1 list1 = new GenericLinkedList1();
    list1.addLast("Happy Days!");
    list1.addLast("Grrr!");
    list1.addLast("Welcome to Java!");
    list1.addLast("Hello World!");

    // Prints list as is.
    list1.printList();

    // Adds a node after Grrr!
    list1.add("I'm sorry!!!",2);

    // Prints list.
    list1.printList();

    // Removes the added node.
    list1.remove(3);

    // Prints list.
    list1.printList();

    // Sorts list.
    list1 = list1.sort(list1);
    list1.printList();
  }
}

class GenericLinkedList1 {
  public TreeNode first;
  public TreeNode last;
  public int count = 0;

  public void addFirst(Object e) {
    if(first == null) {
      first = new TreeNode(e);
      last = first;
    }
    else {
      TreeNode temp = first;
      first = new TreeNode(e);
      first.next = temp;
      temp.previous = first;
    }
    count++;
  }

  public void addLast(Object e) {
    if(last == null) {
      last = new TreeNode(e);
      first = last;
    }
    else {
      TreeNode temp = last;
      last = new TreeNode(e);
      last.previous = temp;
      temp.next = last;
    }
    count++;
  }

  /**
   *  Adds new TreeNode after specified index
   */
  public void add(Object e, int index) {
    if (index == 0) addFirst(e);
    else if (index == count) addLast(e);
    else {
      TreeNode current = first;
      for(int i = 1; i <= index-1; i++)
        current = current.next;
      TreeNode insert = new TreeNode(e);
      insert.next = current.next;
      insert.previous = current;
      current.next.previous = insert;
      current.next = insert;
      count++;
    }
  }

  public void removeFirst() {
    if(first != null) {
      first = first.next;
      if(first != null)
        first.previous = null;
      count--;
    }
  }

  public void removeLast() {
    if(last != null) {
      last = last.previous;
      last.next = null;
      count--;
    }
  }

  /**
   *   Removes node at index
   */
  public void remove(int index) {
    if (index == 1) removeFirst();
    else if (index == count) removeLast();
    else {
        TreeNode current = first;
        for(int i = 1; i <= index-1; i++)
          current = current.next;
        current.previous.next = current.next;
        current.next.previous = current.previous;
        count--;
    }
  }

  public GenericLinkedList1 sort(Object o) {
    GenericLinkedList1 toReturn = new GenericLinkedList1();
    for(int k = 0; k <=((GenericLinkedList1) o).count + 2; k++) {
       TreeNode min =((GenericLinkedList1) o).first;
       TreeNode current = ((GenericLinkedList1) o).first.next;
       if(current == null) {
         toReturn.addLast(min);
       }
       int minIndex = 1;
       for(int i = 1; i < ((GenericLinkedList1) o).count;i++) {
         if(((Comparable)min.element).compareTo(current.element) >= 0) {
           min = current;
           minIndex = i + 1 ;
         }
         current = current.next;
       }

       if((min.element.equals(((GenericLinkedList1)o).first.element)) &&
          (min.element.equals(((GenericLinkedList1)o).last.element))) {
         min.previous = null;
         min.next = null;
       }

       if(minIndex == 1) {
         ((GenericLinkedList1)o).removeFirst();
       }
       else if(minIndex == count) {
         ((GenericLinkedList1)o).removeLast();
       }
       else {
         ((GenericLinkedList1)o).remove(minIndex);
       }
       toReturn.addLast(min.element);
    }
    return toReturn;
  }

  public void printList() {
    TreeNode temp = this.first;
    while(temp != null) {
      System.out.print(temp.element.toString() + " ");
      temp = temp.next;
    }
    System.out.println();
  }

  private class TreeNode {
    public Object element;
    public TreeNode next;
    public TreeNode previous;

    public TreeNode(Object e) {
      element = e;
    }
  }
}