有序链表

一般,在大多数需要使用有序数组的场合也可以使用有序链表,有序链表优于有序数组的地方是插入的速度(因为 元素不需要移动),另外,链表可以扩展到全部有效的使用内存,而数组只能局限于一个固定的大小中。但是, 有序链表实现起来比有序数组更苦难一些。

核心代码

public class Node {
  public int data;
  public Node next;
  public Node(int data) {
    this.data = data;
  }
  public void display() {
    System.out.println(data);
  }
}
public class SortedLinkList {
  private Node first;

  public SortedLinkList() {
    first = null;
  }

  public void insert(int data) {
    Node newNode = new Node(data);
    Node previous = null;
    Node current = first;
    while (current != null && data > current.data) {
      previous = current;
      current = current.next;
    }
    if (previous == null) {
      first = newNode;
    } else {
      previous.next = newNode;
    }
    newNode.next = current;
  }

  public Node remove(){
    Node temp =first;
    first=first.next;
    return temp;
  }

  public boolean isEmpty() {
    return (first == null);
  }

  public void display() {
    Node current = first;
    while (current != null) {
      current.display();
      current = current.next;
    }
  }

}

参考资料