链表在java中是非直接支持的数据结构。链表是一种递归的数据结构，它或者为空(null)，或者是指向一个结点(node)的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

实现描述

  • 结点记录

    1
    2
    3
    4
    private class Node {
      Item item;
      Node next;
    }

    上面的代码：

    1. Node类型的实例变量显示了这种数据结构的链式本质
    2. 记录：为了强调我们在组织数据时只使用了Node类，没有定义任何方法且会在代码中直接引用实例变量，这种类型的类有时也被称为记录。在我们的实现中，Node和它的用例代码都会被封装在相同的类中且无法被该类的用例访问。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Stack<Item> {
  private Node first;
  private int N;
  private class Node {
    Item item;
    Node next;
  }
  public boolean isEmpty() {
    return first == null;
  }
  public int size() {
    return N;
  }
  public void push(Item item) {
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
    N++;
  }
  public Item pop() {
    Item item = first.item;
    first = first.next;
    N--;
    return item;
  }
  // 待补充iterator()的实现
  public static void main(String[] args) {
    Stack<String> s = new Stack<String>();
    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals("-")) {
        s.push(item);
      } else if (!s.isEmpty()) {
        StdOut.print(s.pop() + " ");
      }
    }
    StdOut.println("(" + s.size() + " left on stack)");
  }
}

上述实现的特性

满足上述描述的实现几乎达到了任意集合类数据类型的实现的最佳性能：

  • 每项操作的用时都与集合大小无关
  • 空间需求总是不超过集合大小乘以一个常数

参考

  • 《算法》p89-p94