每一秒钟的时间都值得铭记

0%

数据结构之什么是链表？

发表于 分类于
本文字数： 12k 阅读时长 ≈ 11 分钟

什么是链表？

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干个节点（node）所组成。

链表分为单向链表和双向链表。

  • 单向链表的每一个节点包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。

  • 双向链表比单向链表复杂一些，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

如果说数组在内存中的存储方式为顺序存储，那么链表在内存在的存储方式则是随机存储。

什么是随机存储？

数组在内存中占用了连续完整的存储空间。而链表则采用见缝插针的方式，链表的每一个节点分布在内存空间中的不同位置，依靠指针关联起来，这样可以灵活有效地利用零散的碎片空间。

链表的组成

本篇文章中的链表均以单链表的Demo，在文章的末尾处会附带双向链表的实现代码。

  • 节点：一个链表是有若干个结点组成的，节点是链表的基础结构。

  • 头节点指针：链表需要一个头节点指针，用于表示链表开始的位置。

  • 尾结点指针：链表可以设置一个尾部节点指针。

    当然，链表的尾部节点指针不是必须的，因为链表最后一个节点的next指针指向空，也可以标识链表的结尾。

  • 链表实际长度：可以设置一个变量记录链表的实际长度。

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
public class LinkedList {

    /**
     * 链表的头指针
     */
    private Node head;

    /**
     * 链表的尾部指针
     */
    private Node last;

    /**
     * 链表的实际长度
     */
    private int size;

    /**
     * 获取链表的头指针
     *
     * @return 链表的头指针
     */
    public Node head() {
        return this.head;
    }

    /**
     * 获取链表的尾部指针
     *
     * @return 链表的尾部指针
     */
    public Node last() {
        return this.last;
    }

    /**
     * 获取链表的实际长度
     *
     * @return 链表的实际长度
     */
    public int size() {
        return this.size;
    }

    /**
     * 将节点点作为链表的一个内部类
     */
    class Node {
        // 节点存储的数据data
        private int data;
        // 该指针指向下一个节点的指针next
        private Node next;

        // 构造函数
        Node(int data) {
            this.data = data;
        }

        /**
         * 返回节点中存储的数据值
         *
         * @return 节点中存储的数据值
         */
        public int data() {
            return this.data;
        }

        /**
         * 返回下一个节点的指针
         *
         * @return 下一个节点的指针
         */
        public Node next() {
            return this.next;
        }
    }
}

链表的基本操作

和数组一样，链表的基本操作也同样是增、删、改、查四种操作。

查

链表查找元素不像数组那样可以通过下标进行随机访问，链表想要查找一个元素，只能从头节点开始，一个一个向后查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 链表的查找操作
 *
 * @param index 需要查找的链表索引
 * @return 索引对应的链表节点
 */
public Node get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("超出链表的实际节点范围");
    }
    // 找到链表的头节点的位置
    Node temp = this.head;
    // 从头节点向后查找，共向后循环index次，即可找到index位置的节点
    for (int i = 0; i < index; i++) {
        temp = temp.next;
    }
    return temp;
}

改

链表的更新操作也比较简单，只需要查找到需要修改的节点，直接将原节点的数据替换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 更新链表节点
 *
 * @param index 需要更新的链表位置
 * @param data  需要更新的节点的值
 */
public void update(int index, int data) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("超出链表的实际节点范围");
    }
    // 找到链表的头节点的位置
    Node temp = this.head;
    // 从头节点向后查找，共向后循环index次，即可找到index位置的节点
    for (int i = 0; i < index; i++) {
        temp = temp.next;
    }
    // 使用需要替换的值，替换原值
    temp.data = data;
}

增

链表的插入操作分为三组：

  • 尾部插入

    链表的尾部操作最为简单，只需要将链表的尾部节点的next指针，指向新结点即可。
    如果有尾部节点指针，则还需要维护链表尾部节点指针，将其指向新节点。

  • 中间插入

    链表的中间插入，分为三步：
    第一步：找到要插入的链表位置。
    第二步：将新结点的next指针指向插入位置的节点。
    第三步：将原插入位置的节点的上一个节点的next指针指向新节点。

  • 头部插入

    链表的头部插入，分为三步：
    第一步：将新节点的next指针指向新节点。
    第二步：维护链表的头部节点指针，将其指向新节点。

链表的插入操作与数组的插入操作有些许不同，就在于链表不会出现容量不足的情况，无需进行扩容操作。

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
/**
 * 直接在尾部插入
 *
 * @param data 需要插入的数据
 */
public void insert(int data) {
    insert(size, data);
}

/**
 * 直接在尾部插入
 *
 * @param index 需要插入的链表位置
 * @param data  需要插入的数据
 */
public void insert(int index, int data) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("超出链表的实际节点范围");
    }
    // 将需要插入的数据封装为一个链表节点
    Node insertNode = new Node(data);
    // 链表节点为空的情况
    if (size == 0) {
        // 维护链表头部节点指针
        this.head = insertNode;
        // 维护链表尾部节点指针
        this.last = insertNode;
    } else if (index == 0) {
        // 头部插入
        // 使用新节点的next指针指向头部节点
        insertNode.next = this.head;
        // 维护链表头部节点的指针
        this.head = insertNode;
    } else if (index == size) {
        // 尾部插入
        // 直接使用尾部节点指针指向新结点
        this.last.next = insertNode;
        // 维护链表尾部节点的指针
        this.last = insertNode;
    } else {
        // 获取插入位置的前一个节点
        Node prevNode = get(index - 1);
        // 将新节点的next指针指向插入位置节点
        insertNode.next = prevNode.next;
        // 插入位置的前一个节点的next指针指向新节点
        prevNode.next = insertNode;
    }
    // 维护链表长度
    size++;
}

删

链表的删除操作和插入操作类似。

  • 删除头部节点

    删除头部节点，只需要将链表的head指针指向原head节点的下一个节点即可。

  • 删除中间节点

    删除中间节点，删除位置的前一个节点的next指针指向删除位置的下一个节点即可。

  • 删除尾部节点

    删除尾部节点，将尾部节点的前一个节点的next指针置空，并维护last指针即可。

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
/**
 * 删除链表的结点
 *
 * @param index 需要删除的位置
 * @return 被删除的节点
 */
public Node remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("超出链表的实际节点范围");
    }
    Node removeNode = null;
    // 头部删除
    if (index == 0) {
        removeNode = this.head;
        // 维护链表的头部指针
        this.head = removeNode.next;
    } else if (index == size - 1) {
        // 尾部删除
        // 获取尾部的前一个节点
        Node prevNode = get(index - 1);
        removeNode = prevNode.next;
        // 置空尾部的前一个节点的next指针
        prevNode.next = null;
        // 维护链表的尾部指针
        this.last = prevNode;
    } else {
        // 获取插入位置的前一个节点
        Node prevNode = get(index - 1);
        // 需要删除的节点
        removeNode = prevNode.next;
        // 将删除位置的上一个节点的next指针指向删除位置的下一个节点
        prevNode.next = removeNode.next;
    }
    // 维护链表长度
    size--;
    return removeNode;
}

链表操作的时间复杂度

链表操作 时间复杂度
查找节点 O(n)
更新节点 O(1)
插入节点 O(1)
删除节点 O(1)

链表的优势和劣势

优势：链表能够灵活地插入，删除节点，所以更适用于插入，更新，删除操作更多场景。

劣势：链表的查找操作，需要从头遍历整个链表，性能低下，不适用与读操作多的场景。

单链表的完整代码（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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
public class LinkedList {

    /**
     * 链表的头指针
     */
    private Node head;

    /**
     * 链表的尾部指针
     */
    private Node last;

    /**
     * 链表的实际长度
     */
    private int size;

    /**
     * 获取链表的头指针
     *
     * @return 链表的头指针
     */
    public Node head() {
        return this.head;
    }

    /**
     * 获取链表的尾部指针
     *
     * @return 链表的尾部指针
     */
    public Node last() {
        return this.last;
    }

    /**
     * 获取链表的实际长度
     *
     * @return 链表的实际长度
     */
    public int size() {
        return this.size;
    }

    /**
     * 链表的查找操作
     *
     * @param index 需要查找的链表索引
     * @return 索引对应的链表节点
     */
    public Node get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 找到链表的头节点的位置
        Node temp = this.head;
        // 从头节点向后查找，共向后循环index次，即可找到index位置的节点
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 更新链表节点
     *
     * @param index 需要更新的链表位置
     * @param data  需要更新的节点的值
     */
    public void update(int index, int data) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 找到链表的头节点的位置
        Node temp = this.head;
        // 从头节点向后查找，共向后循环index次，即可找到index位置的节点
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        // 使用需要替换的值，替换原值
        temp.data = data;
    }

    /**
     * 直接在尾部插入
     *
     * @param data 需要插入的数据
     */
    public void insert(int data) {
        insert(size, data);
    }

    /**
     * 直接在尾部插入
     *
     * @param index 需要插入的链表位置
     * @param data  需要插入的数据
     */
    public void insert(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 将需要插入的数据封装为一个链表节点
        Node insertNode = new Node(data);
        // 链表节点为空的情况
        if (size == 0) {
            // 维护链表头部节点指针
            this.head = insertNode;
            // 维护链表尾部节点指针
            this.last = insertNode;
        } else if (index == 0) {
            // 头部插入
            // 使用新节点的next指针指向头部节点
            insertNode.next = this.head;
            // 维护链表头部节点的指针
            this.head = insertNode;
        } else if (index == size) {
            // 尾部插入
            // 直接使用尾部节点指针指向新结点
            this.last.next = insertNode;
            // 维护链表尾部节点的指针
            this.last = insertNode;
        } else {
            // 获取插入位置的前一个节点
            Node prevNode = get(index - 1);
            // 将新节点的next指针指向插入位置节点
            insertNode.next = prevNode.next;
            // 插入位置的前一个节点的next指针指向新节点
            prevNode.next = insertNode;
        }
        // 维护链表长度
        size++;
    }

    /**
     * 删除链表的结点
     *
     * @param index 需要删除的位置
     * @return 被删除的节点
     */
    public Node remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        Node removeNode = null;
        // 头部删除
        if (index == 0) {
            removeNode = this.head;
            // 维护链表的头部指针
            this.head = removeNode.next;
        } else if (index == size - 1) {
            // 尾部删除
            // 获取尾部的前一个节点
            Node prevNode = get(index - 1);
            removeNode = prevNode.next;
            // 置空尾部的前一个节点的next指针
            prevNode.next = null;
            // 维护链表的尾部指针
            this.last = prevNode;
        } else {
            // 获取插入位置的前一个节点
            Node prevNode = get(index - 1);
            // 需要删除的节点
            removeNode = prevNode.next;
            // 将删除位置的上一个节点的next指针指向删除位置的下一个节点
            prevNode.next = removeNode.next;
        }
        // 维护链表长度
        size--;
        return removeNode;
    }


    /**
     * 将节点点作为链表的一个内部类
     */
    class Node {
        // 节点存储的数据data
        private int data;
        // 该指针指向下一个节点的指针next
        private Node next;

        // 构造函数
        Node(int data) {
            this.data = data;
        }

        /**
         * 返回节点中存储的数据值
         *
         * @return 节点中存储的数据值
         */
        public int data() {
            return this.data;
        }

        /**
         * 返回下一个节点的指针
         *
         * @return 下一个节点的指针
         */
        public Node next() {
            return this.next;
        }
    }
}

双向链表的完整代码（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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
public class DoubleLinkedList {

    /**
     * 链表的头指针
     */
    private Node head;

    /**
     * 链表的尾部指针
     */
    private Node last;

    /**
     * 链表的实际长度
     */
    private int size;

    /**
     * 获取链表的头指针
     *
     * @return 链表的头指针
     */
    public Node head() {
        return this.head;
    }

    /**
     * 获取链表的尾部指针
     *
     * @return 链表的尾部指针
     */
    public Node last() {
        return this.last;
    }

    /**
     * 获取链表的实际长度
     *
     * @return 链表的实际长度
     */
    public int size() {
        return this.size;
    }

    /**
     * 链表的查找操作
     *
     * @param index 需要查找的链表索引
     * @return 索引对应的链表节点
     */
    public Node get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 找到链表的头节点的位置
        Node temp = this.head;
        // 从头节点向后查找，共向后循环index次，即可找到index位置的节点
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 更新链表节点
     *
     * @param index 需要更新的链表位置
     * @param data  需要更新的节点的值
     */
    public void update(int index, int data) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 找到链表的头节点的位置
        Node temp = this.head;
        // 从头节点向后查找，共向后循环index次，即可找到index位置的节点
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        // 使用需要替换的值，替换原值
        temp.data = data;
    }

    /**
     * 直接在尾部插入
     *
     * @param data 需要插入的数据
     */
    public void insert(int data) {
        insert(size, data);
    }

    /**
     * 直接在尾部插入
     *
     * @param index 需要插入的链表位置
     * @param data  需要插入的数据
     */
    public void insert(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 将需要插入的数据封装为一个链表节点
        Node insertNode = new Node(data);
        // 链表节点为空的情况
        if (size == 0) {
            // 维护链表头部节点指针
            this.head = insertNode;
            // 维护链表尾部节点指针
            this.last = insertNode;
        } else if (index == 0) {
            // 头部插入
            Node headNode = this.head;
            // 将原头节点的上一个节点指针指向新节点
            headNode.prev = insertNode;
            // 使用新节点的next指针指向头部节点
            insertNode.next = headNode;
            // 维护链表头部节点的指针
            this.head = insertNode;
        } else if (index == size) {
            // 尾部插入
            // 直接使用尾部节点指针指向新结点
            this.last.next = insertNode;
            // 新节点的上一个节点指向原尾部节点
            insertNode.prev = this.last;
            // 维护链表尾部节点的指针
            this.last = insertNode;
        } else {
            // 获取插入位置的前一个节点
            Node prevNode = get(index - 1);
            // 插入位置的节点
            Node nextNode = prevNode.next;
            nextNode.prev = insertNode;
            // 将新节点的next指针指向插入位置节点,prev指针指向前一个节点
            insertNode.next = nextNode;
            insertNode.prev = prevNode;
            // 插入位置的前一个节点的next指针指向新节点
            prevNode.next = insertNode;
        }
        // 维护链表长度
        size++;
    }

    /**
     * 删除链表的结点
     *
     * @param index 需要删除的位置
     * @return 被删除的节点
     */
    public Node remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        Node removeNode = null;
        // 头部删除
        if (index == 0) {
            removeNode = this.head;
            Node nextHead = removeNode.next;
            // 置空新的头部节点的pre指针
            nextHead.prev = null;
            // 维护链表的头部指针
            this.head = nextHead;
        } else if (index == size - 1) {
            // 尾部删除
            // 获取尾部的前一个节点
            Node prevNode = get(index - 1);
            removeNode = prevNode.next;
            // 置空尾部的前一个节点的next指针
            prevNode.next = null;
            // 维护链表的尾部指针
            this.last = prevNode;
        } else {
            // 获取插入位置的前一个节点
            Node prevNode = get(index - 1);
            // 需要删除的节点
            removeNode = prevNode.next;
            // 删除节点的下一个节点
            Node nextNode = removeNode.next;
            // 将删除位置的上一个节点的next指针指向删除位置的下一个节点
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
        }
        // 维护链表长度
        size--;
        return removeNode;
    }


    /**
     * 将节点点作为链表的一个内部类
     */
    class Node {
        // 节点存储的数据data
        private int data;
        // 该指针指向上一个
        private Node prev;
        // 该指针指向下一个节点的指针next
        private Node next;

        // 构造函数
        Node(int data) {
            this.data = data;
        }

        /**
         * 返回节点中存储的数据值
         *
         * @return 节点中存储的数据值
         */
        public int data() {
            return this.data;
        }

        /**
         * 返回上一个节点的指针
         *
         * @return 上一个节点的指针
         */
        public Node prev() {
            return this.prev;
        }

        /**
         * 返回下一个节点的指针
         *
         * @return 下一个节点的指针
         */
        public Node next() {
            return this.next;
        }
    }
}

最后

本文Github https://github.com/herenpeng/code-learn 已收录，欢迎Star。

坚持原创技术分享，您的支持将鼓励我继续创作！
-------------这是我的底线^_^-------------