线性数据结构

image-20210317134905787

为什么链表很重要

  • 真正的动态数据结构
  • 最简单的动态数据结构
  • 更深入的理解引用（或者指针）
  • 更深入的理解递归
  • 辅助组成其他数据结构

链表 Linked List

  • 数据存储在”节点“（Node）中

    1
    2
    3
    4
    class Node {
      E e;
      Node next;
    }

    image-20210317135624177

  • 优点：真正的动态，不需要处理固定容量的问题

  • 缺点：丧失了随机访问的能力（不能使用索引访问数据）

数组和链表的对比

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

链表实现

节点的实现

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
/**
  * 节点设置为私有的内部类，对于用户不需要知道节点的实现细节
  */
 private class Node {
     /**
      * 数据域
      */
     public E e;
     /**
      * 指针（引用）
      */
     public Node next;

     /**
      * 节点构造函数初始化
      *
      * @param e    元素
      * @param next 指针
      */
     public Node(E e, Node next) {
         this.e = e;
         this.next = next;
     }

     /**
      * 节点构造函数初始化
      *
      * @param e 元素
      */
     public Node(E e) {
         this(e, null);
     }

     /**
      * 节点构造函数初始化
      */
     public Node() {
         this(null, null);
     }

     /**
      * 节点元素格式化输出
      *
      * @return String
      */
     @Override
     public String toString() {
         return e.toString();
     }
 }

链表中添加元素

image-20210317140848386

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
package demo.structure.linked;

/**
 * 链表
 *
 * @author jingLv
 * @date 2020/12/07
 */
public class LinkedList<E> {
    /**
     * 节点设置为私有的内部类，对于用户不需要知道节点的实现细节
     */
    private class Node {
        /**
         * 数据域
         */
        public E e;
        /**
         * 指针（引用）
         */
        public Node next;

        /**
         * 节点构造函数初始化
         *
         * @param e    元素
         * @param next 指针
         */
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        /**
         * 节点构造函数初始化
         *
         * @param e 元素
         */
        public Node(E e) {
            this(e, null);
        }

        /**
         * 节点构造函数初始化
         */
        public Node() {
            this(null, null);
        }

        /**
         * 节点元素格式化输出
         *
         * @return String
         */
        @Override
        public String toString() {
            return e.toString();
        }
    }

    /**
     * 链表的头节点
     */
    private Node head;
    /**
     * 链表中元素的个数
     */
    private int size;

    /**
     * 无参构造函数，进行数据初始化
     */
    public LinkedList() {
        head = null;
        size = 0;
    }

    /**
     * 获取列表中的元素个数
     *
     * @return 元素个个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断链表是否为空
     *
     * @return boolean
     */
    public boolean isEmpty() {
        return size == 0;
    }
  
      /**
     * 在链表头添加新的元素e
     *
     * @param e 添加的元素
     */
    public void addFirst(E e) {
//        // 新声明节点
//        Node node = new Node(e);
//        // 将头节点指向下一个节点
//        node.next = head;
//        // 将新节点赋值给原来头节点
//        head = node;
        // 上面的代码，可优化为
        head = new Node(e, head);
        size++;
    }

    /**
     * 在链表的index(0-based)位置添加新的元素e
     * 在链表中不是一个常用的操作
     *
     * @param index 插入的位置
     * @param e     插入的元素
     */
    public void add(int index, E e) {
        // 判断插入位置的合法性
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed.Illegal index.");
        }
        // 如果插入的位置在链表头
        if (index == 0) {
            addFirst(e);
        } else {
            // 从链表的头节点开始，找到位置，将节点元素插入
            Node previous = head;
            for (int i = 0; i < index; i++) {
                previous = previous.next;
            }
//            Node node = new Node(e);
//            node.next = previous.next;
//            previous.next = node;
            // 上面三行代码的优化
            previous.next = new Node(e, previous.next);
            size++;
        }
    }

    /**
     * 在链表末尾添加新的元素e
     *
     * @param e 添加元素
     */
    public void addLast(E e) {
        add(size, e);
    }
}

DummyHead虚拟头节点实现链表

不存在的一个虚拟头节点，这个节点是没有意义的，只是为了实现逻辑方便

image-20210317142542811

image-20210317143815216

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
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
package demo.structure.linked;

/**
 * 链表
 *
 * @author jingLv
 * @date 2020/12/07
 */
public class LinkedList<E> {
    /**
     * 节点设置为私有的内部类，对于用户不需要知道节点的实现细节
     */
    private class Node {
        /**
         * 数据域
         */
        public E e;
        /**
         * 指针（引用）
         */
        public Node next;

        /**
         * 节点构造函数初始化
         *
         * @param e    元素
         * @param next 指针
         */
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        /**
         * 节点构造函数初始化
         *
         * @param e 元素
         */
        public Node(E e) {
            this(e, null);
        }

        /**
         * 节点构造函数初始化
         */
        public Node() {
            this(null, null);
        }

        /**
         * 节点元素格式化输出
         *
         * @return String
         */
        @Override
        public String toString() {
            return e.toString();
        }
    }

    /**
     * 链表的头节点
     */
    private Node dummyHead;
    /**
     * 链表中元素的个数
     */
    private int size;

    /**
     * 无参构造函数，进行数据初始化
     */
    public LinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }

    /**
     * 获取列表中的元素个数
     *
     * @return 元素个个数
     */
    public int getSize() {
        return size;
    }

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

    /**
     * 在链表的index(0-based)位置添加新的元素e
     * 在链表中不是一个常用的操作
     *
     * @param index 插入的位置
     * @param e     插入的元素
     */
    public void add(int index, E e) {
        // 判断插入位置的合法性
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed.Illegal index.");
        }
        // 从虚拟头节点开始遍历链表，找到需要插入的位置进行元素插入
        Node previous = dummyHead;
        for (int i = 0; i < index; i++) {
            previous = previous.next;
        }
        previous.next = new Node(e, previous.next);
        size++;
    }

    /**
     * 在链表头添加新的元素e
     *
     * @param e 添加的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 在链表末尾添加新的元素e
     *
     * @param e 添加元素
     */
    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 获得链表的第index(0-based)个位置的元素
     * 在链表中不是一个常用的操作
     *
     * @param index 节点的位置
     * @return 获取的元素
     */
    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Get failed.Illegal index.");
        }
        // 从链表的头节点开始循环遍历找到需要查找的元素
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.e;
    }

    /**
     * 获得链表的第一个元素
     *
     * @return 获取链表头元素
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 获得链表的最后一个元素
     *
     * @return 获取链表的尾元素
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 修改链表的第index(0-based)个位置的元素为e
     * 在链表中不是一个常用的操作
     *
     * @param index 节点的位置
     * @param e     修改的节点元素
     */
    public void set(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Set failed.Illegal index.");
        }
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.e = e;
    }

    /**
     * 查找链表中是否有元素e
     *
     * @param e 查找的元素
     * @return boolean
     */
    public boolean contains(E e) {
        Node current = dummyHead.next;
        while (current != null) {
            if (current.e.equals(e)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * 从链表中删除index(0-based)位置的元素，返回删除的元素
     * 在链表中不是一个常用的操作
     *
     * @param index 节点元素的位置
     * @return 删除的节点元素
     */
    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Remove failed.Illegal index.");
        }
        Node previous = dummyHead;
        for (int i = 0; i < index; i++) {
            previous = previous.next;
        }
        Node resultNode = previous.next;
        previous.next = resultNode.next;
        resultNode.next = null;
        size--;
        return resultNode.e;
    }

    /**
     * 从链表中删除第一个元素，返回删除的元素
     *
     * @return 删除的节点元素
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 从链表中删除最后一个元素，返回删除的元素
     *
     * @return 删除的节点元素
     */
    public E removeLast() {
        return remove(size - 1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
//        Node current = dummyHead.next;
//        // while循环遍历链表
//        while (current != null) {
//            res.append(current + "->");
//            current = current.next;
//        }
        // for循环遍历链表
        for (Node current = dummyHead.next; current != null; current = current.next) {
            res.append(current).append("->");
        }
        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
20
21
22
23
24
25
26
27
28
29
30
31
package demo.structure.linked;

/**
 * 链表测试
 *
 * @author jingLv
 * @date 2020/12/09
 */
public class LinkedListMain {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        System.out.println("-------------链表添加--------------");
        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }

        linkedList.add(2, 666);
        System.out.println(linkedList);

        System.out.println("-------------链表删除--------------");
        linkedList.remove(2);
        System.out.println(linkedList);

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

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

执行结果

image-20210317144042305

链表的时间复杂度分析

  • 添加操作 – 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)
  • 修改操作 – O(n)
    • set(index, e) – O(n)
  • 查找操作 – O(n)
    • get(index) – O(n)
    • contains(e) – O(n)
    • 只查链表头的元素：O(1)
  • 如果只对链表头进行操作：O(1)

链表实现栈

Interface Stack<E> <—–implement—– LinkedListStack<E>

  • void push(E)
  • E pop()
  • E peek()
  • int getSize()
  • boolean isEmpty()
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
package demo.structure.stack;

import demo.structure.linked.LinkedList;

/**
 * 链表实现栈
 *
 * @author jingLv
 * @date 2020/12/10
 */
public class LinkedListStack<E> implements Stack<E> {
    /**
     * 电仪列表
     */
    private LinkedList<E> list;

    /**
     * 构造函数--初始化链表
     */
    public LinkedListStack() {
        list = new LinkedList<>();
    }

    /**
     * 获取列表中元素个数
     *
     * @return 元素个数
     */
    @Override
    public int getSize() {
        return list.getSize();
    }

    /**
     * 判断链表是否为空
     *
     * @return Boolean
     */
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 入栈
     *
     * @param e 入栈的元素
     */
    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    /**
     * 出栈
     *
     * @return 出栈的元素
     */
    @Override
    public E pop() {
        return list.removeFirst();
    }

    /**
     * 获取栈顶的元素
     *
     * @return 栈顶元素
     */
    @Override
    public E peek() {
        return list.getFirst();
    }

    /**
     * 格式化输出栈
     *
     * @return string
     */
    @Override
    public String toString() {
        return "Stack: top " + list;
    }
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package demo.structure.stack;

/**
 * 链表实现栈
 *
 * @author jingLv
 * @date 2020/11/30
 */
public class LinkedListStackMain {

    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
        System.out.println("------pop------");
        stack.pop();
        System.out.println(stack);
    }
}

执行结果

image-20210320145307991

数组实现的栈与链表实现的栈性能比较

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
package demo.structure.stack;

import java.util.Random;

/**
 * 数组实现的栈与链表实现的栈测试比较
 *
 * @author jinglv
 * @date 2021/03/14
 */
public class Main {
    /**
     * 测试使用stack运行opCount个push和pop操作所需要的时间，单位：秒
     *
     * @param stack   栈
     * @param opCount 栈中元素的个数
     * @return 时间（秒）
     */
    private static double testStack(Stack<Integer> stack, int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++) {
            stack.push(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            stack.pop();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {
        int opCount = 1000000;

        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        double time1 = testStack(arrayStack, opCount);
        System.out.println("ArrayStack,time:" + time1 + " s");

        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        double time2 = testStack(linkedListStack, opCount);
        System.out.println("LinkedListStack,time:" + time2 + " s");

        // 其实这个时间比较很复杂，因为LinkedListStack中包含更多的new操作
    }
}

十万元素的执行结果

image-20210320145543738

一百万元素的执行结果

image-20210320145510491

从上面的对比看到，元素越多，链表栈耗时则非常多，因为LinkedListStack中包含更多的new操作，元素越多，则结果差异越大。

链表实现队列

image-20210320150549188

  • 改进列表
    • head：头节点
    • tail：尾节点
    • 从两端出插入元素都是容易的
    • 从tail删除元素不容易
    • 从head端删除元素，从tail端插入元素，删除的这一端是队首，插入的这一端是队尾
    • 只对链表两侧进行操作，不对链表中间进行操作
    • 由于没有dummyHead，要注意链表为空的情况
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
package demo.structure.queue;

/**
 * 链表实现队列
 *
 * @author jingLv
 * @date 2020/12/10
 */
public class LinkedListQueue<E> implements Queue<E> {
    /**
     * 节点设置为私有的内部类，对于用户不需要知道节点的实现细节
     */
    private class Node {
        /**
         * 数据域
         */
        public E e;
        /**
         * 指针（引用）
         */
        public Node next;

        /**
         * Node构造函数
         *
         * @param e    数据
         * @param next 指针
         */
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        /**
         * Node构造函数
         *
         * @param e 数据
         */
        public Node(E e) {
            this(e, null);
        }

        /**
         * Node构造函数
         */
        public Node() {
            this(null, null);
        }

        /**
         * 链表格式化输出
         *
         * @return string
         */
        @Override
        public String toString() {
            return e.toString();
        }
    }

    /**
     * head 头节点
     * tail 尾节点
     */
    private Node head, tail;
    /**
     * 链表队列中元素的个数
     */
    private int size;

    /**
     * 构造函数--初始化链表队列
     */
    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 获取列表中元素的个数
     *
     * @return 元素的个数
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断列表是否为空
     *
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 队列中添加元素从尾进行添加，入队
     *
     * @param e 入队的元素
     */
    @Override
    public void enqueue(E e) {
      	// tail为空则head也为空，如果链表中有元素则tail会指向tail的元素
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    /**
     * 队列中删除数据，出队
     *
     * @return 出队的元素
     */
    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        // 出队的元素指向head
        Node resultNode = head;
        // 则当前head指向到head下一个节点
        head = head.next;
        // 将出队的元素置为null
        resultNode.next = null;
        // head节点可能为空，如果head为空，则tail也为空，链表队列无元素的情况
        if (head == null) {
            tail = null;
        }
        // 元素个数自减
        size--;
        return resultNode.e;
    }

    /**
     * 查看队首的元素
     *
     * @return 队头元素
     */
    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        return head.e;
    }

    /**
     * 链表格式化输出
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");
        Node current = head;
        while (current != null) {
            res.append(current).append("->");
            current = current.next;
        }
        res.append("NULL tail");
        return res.toString();
    }
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package demo.structure.queue;

/**
 * 链表队列测试类
 *
 * @author jingLv
 * @date 2020/12/10
 */
public class LinkedListQueueMain {

    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

执行结果：

image-20210320151640576

数组实现的线性队列和数组实现的循环队列和链表实现的线性队列性能对比

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
package demo.structure.queue;

import java.util.Random;

/**
 * 测试数组队列与循环队列的差别
 *
 * @author jingLv
 * @date 2020/12/03
 */
public class Main {

    public static void main(String[] args) {
        int opCount = 1000000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time:" + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time:" + time2 + " s");

        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue, opCount);
        System.out.println("LinkedListQueue, time:" + time3 + " s");
    }

    /**
     * 测试使用q运行OpCount个enqueue和dequeue操作所需要的时间，单位秒
     *
     * @param q       队列
     * @param opCount 队列的元素
     * @return 时间（秒）
     */
    private static double testQueue(Queue<Integer> q, int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        // 入队
        for (int i = 0; i < opCount; i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        // 出队
        for (int i = 0; i < opCount; i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
}

一万元素的执行结果

image-20210320151945531

十万元素的执行结果

image-20210320152014322

链表性能问题

我们在学习Java基础集合中，在我们学到数组和链表的差异时，都是如下的结论：

  • 数组是一种查询快、增删慢的模型
  • 链表是一种增删快、查询慢的模型

但是从上介绍的动态数组实现栈和链表实现栈测试的结果来看，分析如下：

虽然猛地看上去，如果我们只在链表头添加元素，时间复杂度是O(1)的。同时，因为使用链表不需要resize，所以凭直觉，链表的性能应该更好。

但实际上，当数据量达到一定程度，链表的性能是更差的。

这是因为，对于链表来说，每天添加一个元素都需要重新创建一个Node类的对象，也就是都需要进行一次new的内存操作。而对内存的操作，是非常慢的。

从在“数组实现的栈与链表实现的栈性能比较”中测试的结果，明显的看出，使用链表慢于动态数组。

那么，为什么即使有resize，对于大规模数据，动态数组还是会快于链表？

因为对于动态数组来说，一方面，每次热size容量倍增，这将使得，对于大规模数据，实际上触发resize的次数是非常少的。更重要的是，resize的过程，试一次申请一大片内存空间。但是对于链表来说，每次只是申请一个空间。

申请一次10万的空间，是远快于申请10万次1个的空间的。而相较于堆内存空间的操作，动态数组的热size过程虽然还需要赋值，把旧数组的元素拷贝给新数组。但这个拷贝过程，是远远快于对内存的操作。

反转链表

LeetCode206题，Reverse Linked List 反转一个链表

image-20210324101314251

节点不动，只需要改变指针的指向

image-20210324101624667

递归的方式实现链表的反转

image-20210324104946691

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
package demo.structure.linked;

/**
 * LeetCode206题，Reverse Linked List 反转一个链表
 *
 * @author jinglv
 * @date 2021/03/24
 */
public class ReverseLinkedList {

    /**
     * 反转链表
     *
     * @param head 链表的头节点
     * @return 链表
     */
    public ListNode reverseList(ListNode head) {
        // 定义反转需要的节点
        // 头节点之前的节点NULL
        ListNode pre = null;
        // 当前的节点为头节点
        ListNode cur = head;
        // 防止空指针异常，如果当前节点为空，则不会有下一个节点
        while (cur != null) {
            // 下一个节点为头节点的下一个节点
            ListNode next = cur.next;
            // 当前节点的反转，将头节点指向头节点之前的节点（NULL）
            cur.next = pre;
            // 更新引用
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 反转链表--递归实现
     *
     * @param head 链表的头节点
     * @return 链表
     */
    public ListNode reverseListR(ListNode head) {
        // 判断链表是否为空，如果为空或者只有一个节点，则不需要反转
        if (head == null || head.next == null) {
            return head;
        }
        ListNode reverseListNode = reverseListR(head.next);
        head.next.next = head;
        head.next = null;
        return reverseListNode;
    }
}