链表是一种基础的数据结构，在某些情况下链表比数组更适合用来表示集合类的抽象数据类型。链表的定义如下：

链表是一种递归的数据结构，它或者为空（null），或者是指向一个节点（node）的引用，该节点含有一个泛型的元素和一个指向另一条链表的引用。

在结构化存储数据集时，链表是数组的一种重要的替代方式。

链表的简单图示如下：

链表结构的示例

一个简单的节点定义如下：

链表中节点的定义
1
2
3
4
5
private class Node
{
    Item item;
    Node next;
}
其中item为某种需要存储的数据，而next代表指向下一个节点的引用。

和数组结构相比，链表更为灵活，可以轻松的向其中插入删除元素而只用更改少量的节点引用，可以任意的增减大小而不用占据多余的内存空间。但是，在获得链表上特定节点的数据时可能会比数组更为耗时。一般情况下外部只会保留对链表中少量节点（一般为第1个节点）的引用，因此为了获得某个节点上的数据需要由一个节点开始不断的遍历下一个节点直到找到所需的节点数据，如果所需的数据在最后一个节点上，那么就需要遍历整个链表。快速的实现获取（插入、删除）任意节点的标准解决方案是使用双向链表，即在每个节点上都保存有指向下一个节点及上一个节点的引用。

栈的链表实现

下压栈的入栈及出栈操作都是在栈的顶部进行的，因此使用链表能够十分方便的实现栈。栈的顶部即为链表的表头，外部引用指向表头节点。当元素入栈时直接在表头添加一个新的节点，并将外部引用指向新的表头；当元素出栈时，取出表头的元素，并修改外部引用为下一个节点。

以下为用链表实现的栈：

链表实现的栈
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
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;
    }
}

用链表实现的栈达到了以下目标：

  • 可以处理任意的数据类型；
  • 所需的空间总是和集合的大小成正比；
  • 操作所需的时间和集合的大小无关。

队列的链表实现

使用链表来实现队列也十分简单。同时保留指向链表表头及表尾的引用，元素入列时将其添加到表尾，同时修改指向表尾的引用；出列时删除表头的节点，同时修改指向表头的引用。需要注意的是，当链表为空添加一个节点或只有一个节点删除节点时要同时修改指向表头和表尾的引用。

以下为用链表实现的队列：

链表实现的队列
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
public class Queue<Item>
{
    private Node first;
    private Node last;
    private int N;
    private class Node
    {
        Item item;
        Node next;
    }
    public boolean isEmpty() { return first == null; }
    public int size() { return N; }
    public void enqueue(Item item)
    {
        Node oldLast = last;
        last = new Node();
        last.item = item;
        if (isEmpty()) {
            first = last;
        } else {
            oldLast.next = last;
        }
        N++;
    }
    public Item dequeue()
    {
        Item item = first.item;
        first = first.next;
        if (size() == 1) { last = null; }
        N--;
        return item;
    }
}

背包的链表实现

用链表实现背包只需要将栈的实现中push()改名为add()并删除pop()方法。在为背包实现遍历时，由于背包的遍历输出顺序并不重要，也可以直接使用栈的遍历输出。