数据结构-链表

发表于 | 分类于 | | 阅读次数: |
字数统计: 3,774 字 | 阅读时长 ≈ 18 分钟

这节我们学习最基础的动态数据结构—链表。

前两篇我们学的线性数据结构动态数组, 栈, 队列的底层都是依托于静态数组，靠我们写的resize`解决固定容量问题。

链表则是真正的动态数据结构。

链表是最简单的动态数据结构

对链表的理解能更深入的理解引用（或者指针）

能够更深入的理解递归

链表能够辅助组成其他数据结构

链表 Linked List

什么是链表呢？维基百科解释 – 链表

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

链表把数据存储在节点（Node）中，节点主要有两部分内容

1
2
3
4
class Node {
    E e; // 一部分存储真正数据
    Node next;	// 另一部分指向下一个节点的位置
}

image-20181229134219500

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

缺点：丧失了随机访问的能力（数组分配的空间在内存中是连续分配的，可以直接通过索引的偏移获得数据存储数据的内存地址获得数据）

数组和链表的对比：

数组最好用于索引有语义的情况。scores[2]

最大的优点：支持快速查询

链表不适合用于索引有语义的情况。

最大的优点：动态

在链表中添加元素

在链表中如果我们想访问所有的元素，我们需要将链表的头存储起来。

之前我们在往数组中新增元素的时候一般都是直接在尾部直接追加元素，那是因为我们有维护一个size变量来指向下一个元素存放位置。在往链表中新增元素的时候一般是将元素存放到链表的头部。

image-20181229142622185

如上图所示，我们往链表中新增数据节点为66的node，直接将node设置为链表的头部即可。

如何在链表中间添加元素呢？

image-20181229143832082

我们如果想将666插入到位置为2的索引，则先找到插入位置的前一个node，然后将前一个node的next设置为666的node，接着将666的node.next设置为之前node的next。

image-20181229144212089

问题的关键是如何查找到对应的prev即插入前的那个node。

注意： node.next = prev.next prev.next = 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
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
public class LinkedList<E> {

    private class Node {
        // 组成链表的 Node
        public E e;
        public Node next;


        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }

    }

    private Node head; // 类型为Node 的变量 来指向链表的头
    int size;

    public LinkedList() {
        head = null;
        size = 0;
    }

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

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

    // 在链表头添加新的元素
    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
    // 在链表中不是一个常用操作
    public void add(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("illegal index");

        // 如果是插入到链表头 则需要特殊处理
        if (index == 0)
            addFirst(e);
        else {
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;

//                Node node = new Node(e);
//                node.next = prev.next;
//                prev.next = node;
                prev.next = new Node(e, prev.next);

                size++;
            }
        }
    }

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


}
为链表设立虚拟头结点

在上面添加元素到链表的时候，会遇到一种情况就是对添加到第一个位置做特殊处理。原因就是head之前没有node了。

我们可以给head新增一个虚拟的头（dummyHead）来当做第一个node，但是第一个元素实际是dummyHead.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
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
public class LinkedList<E> {

    private class Node {
        // 组成链表的 Node
        public E e;
        public Node next;


        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }

    }

    private Node dummyHead; // 类型为Node 的变量 虚拟头节点
    private int size;

    public LinkedList() {
        dummyHead = new Node(null, null);  // 初始化虚拟头节点 其中设置 e 和 next 都为 空  也就是说 空的链表存在一个虚拟的头结点
        size = 0;
    }

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

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

    // 在链表的index（0-based）位置添加新的元素 e
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        prev.next = new Node(e, prev.next);
        size ++;
    }

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

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

    // 获得链表的index（0-based）位置元素 e
    // 在链表中不是一个常用操作
    public E get(int index) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("illegal index");

        Node cur = dummyHead.next;
        // 获得指定index的元素 从第一个开始
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur.e;
    }

    // 获得第一个元素
    public E getFirst() {
        return get(0);
    }

    // 获得最后一个元素
    public E getLast() {
        return get(size - 1);
    }

    // 修改链表的index（0-based）位置元素 为 e
    // 在链表中不是一个常用操作
    public void set(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("illegal index");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        cur.e = e;
    }

    // 查找链表中是否有元素 e
    public boolean contains(E e) {

        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();

//        Node cur = dummyHead.next;
//        while(cur != null){
//            res.append(cur + "->");
//            cur = cur.next;
//        }
        for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
            res.append(cur + "->");
        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
public class Main {

    public static void main(String[] args) {
	// write your code here

        LinkedList<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);

        }

        linkedList.add(2, 666);
        System.out.println(linkedList);
    }
}
// 输出
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
4->3->666->2->1->0->NULL
列表元素的删除

因为删除涉及到第一个节点，因此我们同样新增虚拟头节点。

image-20181229165631702

和新增的逻辑类似，我们要找到要删除节点的前一个节点prev，然后将要删除节点delNode的next赋值给prev.next。为了方便垃圾回收，我们需要将delNode的next设置为NULL。

新增以下删除方法

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
// 从链表中删除index(o-based)位置的元素 返回删除的元素
// 在链表中不是一个常用的操作
public E remove(int index){

    if(index < 0 || index > size)
        throw new IllegalArgumentException("Remove failed. Illegal index.");

    Node prev = dummyHead;
    for(int i = 0 ; i < index ; i ++)
        prev = prev.next;

    Node delNode = prev.next;

    prev.next = delNode.next;

    delNode.next = null;

    size --;

    return delNode.e;

}

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

// 从链表中删除最后一个元素
public E removeLast(){
    return remove(size - 1);
}

链表的时间复杂度分析

添加操作：O(n)

1
2
3
addLast(e)	O(n)
addFirst(e) O(1)
add(index, e)  O(n/2) = O(n)

删除操作: O(n)

1
2
3
removeLast(e)  O(n)
removeFirst(e) O(1)
remove(index, e) O(n/2) = O(n)

修改操作：O(n)

1
set(index, e) O(n)

查找操作：O(n)

1
2
get(indeex)  O(n)
contains(e)  O(n)

列表中不再实现 find方法 返回对应索引 因为即使有索引 也不能通过索引直接取值

image-20181229173747101

我们看到整体的时间复杂度都是O(n)。

但是如果我们只对链表头进行操作则是O(1)

只查链表头的元素则是O(1)

使用链表实现栈

我们知道如果只对链表的头进行新增和删除，时间复杂度都是O(1)的。这样的操作很符合栈数据结构。

我们可以将链表的头作为栈的栈顶进行操作，从而生成一个栈的数据结构。

image-20190102165303623

我们按照之前Array实现栈的接口来实现按照链表实现的栈。

image-20190102170439592

在之前学习栈的项目新增

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
public class LinkedListStack<E> implements Stack<E> {

    private LinkedList<E> list;

    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }

    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);
        }

        stack.pop();
        System.out.println(stack);
    }
}

比较使用Array实现的栈和链表实现的栈：

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
import java.util.Random;

public class Main {

    // 测试使用stack运行opCount个push和pop操作所需要的时间，单位：秒
    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 = 100000;

        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操作
    }
}
// 输出结果
ArrayStack, time: 0.052957809 s
LinkedListStack, time: 0.031525471 s

// 当把opCount 设置为 1000000 的输出结果
ArrayStack, time: 0.076252863 s
LinkedListStack, time: 0.190566754 s

对于时间复杂度都是O(1)的情况下，两种方式的差别不是很大。

在数组栈中扩容的时候需要将数据拷入到新的数组中，这一步是耗时。

但是当数据量大的时候链表栈就会因为多次创建node节点需要开辟更多的空间。这个开辟新的空间是比较耗时的。

带有尾指针的链表：使用链表实现队列

我们前面分析过，向链表的尾部插入数据的时间复杂度是O(n)。当我们直接使用上面的链表生成队列就会出现入队和出队的时间复杂度不一致问题。

为什么在链表的头部是O(1)呢？

这是因为在链表的头部我们有一个标识head，如果我们想在链表的尾部同样达到O(1)，同理也需要一个标识tail。

当我们在链表的尾部新增了标识tail之后，这样在两端新增元素都是非常容易的，但是从尾部删除数据则还是需要遍历查找到tail之前的节点，这样的时间复杂度是O(n)。但是从链表的头部删除节点却是很容易的。

image-20190102231123668

因此我们将head端作为队首进行出队操作，tail端作为队尾进行入队操作。

注意：链表为空的情况

我们在之前的项目工程中进行操作

image-20190102232539814

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
public class LinkedListQueue<E> implements Queue<E> {

    // 本质是一个链表 需要节点
    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    // 构造函数
    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void enqueue(E e) {
        // 在链表为空的时候
        if (tail == null) {
            tail = new Node(e);
            // 长度为一的时候 head tail 指向同一个节点
            head = tail;

        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }

        size++;

    }

    @Override
    public E dequeue() {

        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        Node retNode = head;
        head = head.next;
        retNode.next = null; // 断链 垃圾回收

        // 如果只有一个节点 删除之后 head 和 tail 应该都为 null
        if (head == null) {
            tail = null;
        }
        size--;

        return retNode.e;
    }

    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return res.toString();
    }

    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);
            }
        }
    }
}

我们将数组队列，循环队列，和链表队列进行一下比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void main(String[] args) {

    int opCount = 100000;

    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");
}

// 输出
ArrayQueue, time: 3.91344695 s
LoopQueue, time: 0.017387918 s
LinkedListQueue, time: 0.015248667 s

// 扩大数字到 1000000

我们看到不同时间复杂度的差别还是很大的。

链表本身具有天然的递归性质，一起来学习链表与递归吧。😊

知识就是财富
如果您觉得文章对您有帮助, 欢迎请我喝杯水！