（四）数据结构之链表

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 3.2k | 阅读时长 ≈ 5 分钟

简介

  链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针)(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。

  使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大。

  在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（”links”）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

  链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的访问和操作。程序语言或面向对象语言，如 C/C++和 Java 依靠易变工具来生成链表。

特性

  • 最简单的动态数据结构
  • 不一定按顺序存储
  • 没有随机访问的能力
  • 可以辅助组成其他数据结构
  • 数据存储在“节点”（Node） 中
  • 真正的动态，不需要处理固定容量的问题

图解

设计思路

img

  从设计上而言，链表存取数据的方法如上图，和在第一章的数组中基本一致，只是内部实现的代码，由于链表的结构特殊性，需要进行额外处理。

  链表的核心在于理解下其节点的概念和为什么需要使用虚拟头节点即可。

代码实现

  如何通过代码实现一个链表，并提供数据的存储和访问功能？

  下面就我们进行代码实现。

节点

  操作链表的前提是理解链表的节点（重点是如何理解指针），下面就定义了一个叫做节点的内部类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 节点
class Node{
    // 数据域
    private E data;
    // 节点指针
    private Node next;

    // 无参时数据域和节点域都为空
    public Node(){}

    // 数据域为 data，节点域为 next
    public Node(E data,Node next){
        this.data = data;
        this.next = next;
    }
}

  初看代码好像挺难理解，为什么节点 Node 里面又有一个名为 next 的 Node？这个节点到底该如何理解呢？
  其实答案很简单，这两个 Node 不同，第一个 Node 是真正形态，第二个名为 next Node 是一个代指，有名无实。

1
2
3
Node nullNode = new Node();
// new Node() 是 Node 的真正形态，而 nullNode 是一个代指
Node head = new Node("1", nullNode);

  举个例子，这就和老式的火车厢一样，一个火车厢包括两部分：

  • 车厢：存放真正的数据
  • 挂钩：用于连接下一节火车厢

  即火车厢 = 车厢+挂钩 –> Node = 数据域 + 指针域。

初版代码实现链表的插入

  若我们想在链表中添加一个节点，代码需要这么编写：

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
// 节点代码与上文相同，省略
private Node head;
    private int size;

    public LinkedList() {
        head = null;
        size = 0;
    }
//      在表头插入数据
       public void addFirst(E data) {
        head = new Node(data, head);
//       上一行代码相当于下面代码的缩写
//        Node prev = new Node(data);
//        prev.next = head;
//        head = prev;
        size++;
    }

    public void add(int index, E data) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        if (index == 0) {
            addFirst(data);
        } else {
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            //缩写和前一个方法类似
            prev.next = new Node(data, prev.next);
            size++;
        }
    }
    }
    
    // 后续代码省略

初版代码的缺陷

  初版代码存在了一些缺陷性问题，什么问题呢？下面我们分析一下：

链表头插入数据

  对于在链表头部插入数据的过程是这样的：

  • ① 创建一个新节点并进行数据域赋值
  • ② 让新节点的节点域指向原先的头节点 (在火车头加一个车厢，把挂钩连到火车头上)：

  • ③ 将头指针指向新创建的节点使其成为头节点 (告诉火车你车头换了，用新的别用旧的啦)：

链表中插入数据

  在链表中其他节点插入数据需要这样：

  • ① 创建一个新节点并进行数据域赋值
  • ② 让新节点的节点域指向需要插入的节点位置（把新的车厢挂钩连到插入位置车厢的挂钩上）：

  • ③ 将插入节点的前一节点的节点指针指向新节点（把插入位置车厢的挂钩连到新的车厢挂钩上）：

不同位置插入数据的差异性

  经过上述分析，可以发现一个结论：在链表中，对于不同部位的插入操作，代码实现起来却并不一样。

注：不仅仅是插入操作这么麻烦，删除操作同样如此。

  那么能不能不这么麻烦，在头节点插入数据时，能否和其他节点插入数据时，代码实现保持一致统一，减少阅读难度呢？

  当然是可以的，此时我们就不得不需要借助到虚拟头节点了。

虚拟头节点

  链表的增加和删除操作，一定要通过待处理节点的前一个节点来实现，为了解决头节点没有前继节点引起的特殊性操作，可以给链表添加一个虚拟头节点。

  因此，我们可以新建一个用于索引的指针dummyHead，指向待处理节点的前继节点，则待处理节点为dummyHead.next，初始化dummyHead则指向链表的虚拟头节点。

注意：虚拟头节点不存储任何数据，只作为一个标识。

  其中，虚拟头节点的图示：

img

  进行添加操作时：先新建一个节点指针prev，令其指向dummyHead节点，prev指针经循环操作后到要添加的节点的前一个位置，然后进行如下操作：

  • 令添加节点（node）的节点域（node.next）指向前一个节点（prev）的节点域（prev.next）
  • 令前一个节点的节点域指向添加的节点

img

  进行删除操作时：先新建一个节点指针prev，令其指向dummyHead节点，prev指针经循环操作后到要删除的节点的前一个位置，然后进行如下操作：

  • 获取要删除的节点（delNode）:为前一个节点（prev）的节点域（prev.next）
  • 让前一个节点的节点域指向要删除节点的节点域
  • 将要删除的节点节点域置为空

img

  问：为什么在链表表尾添加数据和删除数据传入的参数不同？

  因为添加和删除操作均要操作待处理节点的前一个节点来实现，在表尾添加数据时依托于链表中存在的最后一个节点 (将其作为前继节点)，而表尾删除数据时删除的是最后一个节点，此时依托倒数于第二个节点（将其作为前继节点）。

代码实现

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
public class LinkedList<E> {
    // 节点
    class Node {
        private E data;    // 数据域
        private Node next; // 节点指针

        // 无参时数据域和节点域都为空
        public Node() {}

        // 数据域为 data，节点域为 next
        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node dummyhead;  // 虚拟头节点，此节点不存储数据 (dummyhead 可以理解为指针)
    private int size;        // 链表数据个数

    public LinkedList() {
        dummyhead = new Node();
        size = 0;
    }

    // 当前元素个数
    public int size() {
        return size;
    }

    // 链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }


    // 在链表的 index 位置添加新数据，在链表中不是一个常用的操作
    public void add(int index, E data) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        Node pre = dummyhead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = new Node(data, pre.next);
        size++;
    }

    // 在链表首 (虚拟头节点后) 位置添加数据
    public void addFirst(E data) {
        add(0, data);
    }

    // 在链表尾添加数据
    public void addLast(E data) {
        add(size, data);
    }

    // 获取链表指定索引处的数据
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        Node current = dummyhead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    // 获取链表 0 索引处的数据
    public E getFirst() {
        return get(0);
    }

    // 获取链表表尾处的数据
    public E getLast() {
        return get(size - 1);
    }

    // 修改链表指定索引处的数据
    public void set(int index, E data) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        Node current = dummyhead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.data = data;
    }

    // 查看链表是否包含某数据
    public boolean contains(E data) {
        Node current = dummyhead.next;
        while (current != null) {
            if (current.data == data) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 删除链表指定索引的数据
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        Node pre = dummyhead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node ret = pre.next;
        pre.next = ret.next;
        ret.next = null;
        size--;
        return ret.data;
    }

    // 删除 0 索引的数据
    public E removeFirst() {
        return remove(0);
    }

    // 删除最后一个数据
    public E removeLast() {
        return remove(size - 1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("LinkedList:");
        for (Node current = dummyhead.next; current != null; current = current.next) {
            res.append(current.data + "-->");
        }
        res.append("NULL");
        return res.toString();
    }
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Test
public void test(){
    LinkedList<Integer> linkedList = new LinkedList<>();
    for (int i = 0; i < 5; i++) {
        linkedList.addLast(i);
        System.out.println(linkedList);
    }
    linkedList.add(2,666);
    System.out.println(linkedList);

    linkedList.remove(2);
    System.out.println(linkedList);

    linkedList.removeFirst();
    System.out.println(linkedList);

    linkedList.removeLast();
    System.out.println(linkedList);
}

测试结果

1
2
3
4
5
6
7
8
9
linkedlist:0-->NULL
linkedlist:0-->1-->NULL
linkedlist:0-->1-->2-->NULL
linkedlist:0-->1-->2-->3-->NULL
linkedlist:0-->1-->2-->3-->4-->NULL
linkedlist:0-->1-->666-->2-->3-->4-->NULL
linkedlist:0-->1-->2-->3-->4-->NULL
linkedlist:1-->2-->3-->4-->NULL
linkedlist:1-->2-->3-->NULL

时间复杂度

  • 添加操作：O(n)
操作 时间复杂度
addLast(e) O(n)
addFirst(e) O(1)
add(index,e) O(n/2) = O(n)
  • 删除操作：O(n)
操作 时间复杂度
removeLast(e) O(n)
removeFirst(e) O(1)
remove(index,e) O(n/2) = O(n)
  • 修改操作：
操作 时间复杂度
set(index,e) O(n)
  • 查询操作：
操作 时间复杂度
get(index) O(n)
contains(e) O(n)

  总结：

  • 对于添加和删除操作，如果只队链表头进行操作，则时间复杂度为 O(1)
  • 对于查询操作，如果只查链表头的元素，则时间复杂度为 O(1)

数组 VS 链表

  • 数组优点：支持快速查询
  • 数组最好用于索引有语义的情况
  • 链表优点：动态
  • 链表不适合用于索引有语义的情况

文章信息

时间 说明
2018-12-04 初稿
0%