数据结构：手撕链表_手撕链表什么意思

1. 简介

链表也是最基础的数据结构，属于线性表。链表就像火车一样，每一个车厢互相连接，这些车厢就是一个个结点（Node）。链表就是通过这些结点的连接形成的。

对比于数组，链表不支持随机访问，所以数组的访问速度非常快，而链表就慢了。但是链表的长度是动态的，这一点比数组好，不会浪费空间。

2. 创建链表

把结点Node封装在类中，因为用户是不需要知道有Node结点这些概念。

public class LinkedList<E> {
    // 结点
    private class Node{
        public E data;
        public Node next;

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

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

        public Node() {
            this(null, null);
        }
        
        @Override
        public String toString() {
            return data.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

3. 链表的添加

在添加之前，我们需要去访问，因为链表中没有索引这种概念，那访问就需要一个头结点head，从头结点开始访问。

public class LinkedList<E> {
   
    // 结点
    private class Node{
   
        ...
    }
    // 新增
    private Node head;
    // 链表长度
    private int size;
    
    public LinkedList() {
   
        head = null;
        size = 0;
    }
    
    /**
     * 获取链表中的元素个数
     * @return
     */
    public int getSize() {
   
        return size;
    }

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


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

如图：主要有三步：

• 第一步先创建一个node结点并把值传进去；
• 第二步把新创建的结点的next指针指向head；
• 第三步把head指向node结点。

    /**
     * 添加操作
     * @param data
     */
    public void addFirst(E data){
   
        // Node node = new Node(data);
        // node.next = head;
        // head = node;
        // 前面三条语句可以结合成一条
        head = new Node(data, head);
        size++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

有些书上的头结点不存储值。其实头结点可以存储值也可不存储，无论如何就是一个标记，根据该标记方便我们可以操作链表。当然头结点不存值的情况代码需要修改，下面会说。

4. 链表的插入操作

现在假设链表从头结点到尾，可用索引0，1，2…表示，那么假如要把一个结点node插入到索引2，则需要怎么操作。

注意：链表中没有索引的，这里只是为了演示插入操作，因为该操作是一个非常重要的思维。

首先能想到的是，先去查询该位置，查询是利用头结点head，但必须创建一个头结点head的副本来查询，因为头结点head只能一直标记头结点。我们需要查询出该索引的前一个位置的结点，记为prev。

然后将node的next指向prev：

最后将prev的next指向node，就成功插入了：

这两条顺序的顺序不可换，可以试试换了两条语句顺序后的结果，就是错误的：

需要注意，当如果要从索引0插入时，要怎么办，头结点可没有前一个结点。这可以调用addFirst方法。

    /**
     * 插入操作
     * index 范围为0到size
     * 链表中是没有索引的概念，该操作只能理解思维
     * @param index
     * @param data
     */
    public void insert(int index, E data){
   
        if(index < 0 || index > size){
   
            throw new IllegalArgumentException("Insert failed. Illegal index.");
        }

        if(index == 0){
   
            addFirst(data);
        } else {
   
            Node prev = head;
            for(int i = 0; i < index - 1; i++){
   
                prev = prev.next;
            }

            // Node node = new Node(data);
            // node.next = prev.next;
            // prev.next = node;
            // 另一种写法，就是上面三句的结合
            prev.next = new Node(data, prev.next);

            size++;
        }
    }
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

上面的代码还可以修改，比如如果超出size，那么可以把插入的结点添加到链表尾。

现在写个末尾添加结点的方法：

    /**
     * 添加到尾部
     * @param data
     */
    public void addLast(E data){
   
        insert(size, data);
    }
1
2
3
4
5
6
7
8

---

这些东西都是涉及到引用的知识，比如查询：

    // 创建一个head副本
    Node prev = head;
    for(int i = 0; i < index - 1; i++){
   
        // 此时改变引用指向，并不会影响到head
        prev = prev.next;
    }
1
2
3
4
5
6
7

如果这样写：

    // 不创建head副本
    for(int i = 0; i < index - 1; i++){
   
        // 此时改变引用指向，那就影响到了head的指向，即前面的结点会丢失，永远找不回来。
        head = head.next;
    }
1
2
3
4
5
6

5. 链表改为使用虚拟头结点

有些书用的头结点不放任何东西时，每次添加结点是添加到头节点后面的，该头结点称为虚拟头结点，记为dummyHead，比如：

思路都是一样的，其实这是一个插入操作。因为每次都知道要插入的位置的前一个结点，所以完全不需要索引的概念，现在可以来写下，另一种添加操作：（把刚刚的head改成dummyHead）

    // 把 head名称改为 dummyHead
    private Node dummyHead;
    // 修改构造函数
    public LinkedList() {
   
        // 创建虚拟头结点
        dummyHead = new Node(null);
        size = 0;
    }
    
      /**
     * 插入操作
     * index 范围为0到size
     * 链表中是没有索引的概念，该操作只能理解思维
     * 插入操作的关键点在于：找到目标位置的前一个位置
     * @param index
     * @param data
     */
    public void insert(int index, E data){
   
        if(index < 0 || index > size){
   
            throw new IllegalArgumentException("Insert failed. Illegal index.");
        }
        // 此时head是虚拟头结点
        Node prev = dummyHead;
        // 注意边界
        for(int i = 0; i < index; i++){
   
            prev = prev.next;
        }

        // Node node = new Node(data);
        // node.next = prev.next;
        // prev.next = node;
        // 另一种写法
        prev.next = new Node(data, prev.next);

        size++;

    }
    
    /**
     * 添加头结点操作
     * @param data
     */
    public void addFirst(E data){
   
        insert(0, data);
    }
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

跟前面的添加操作对比看看：

• 前面的添加操作，每次添加的结点都当成头结点head。
• 这里的添加操作，每次添加的结点都放在头结点head后面。

两种方法都可以使用任意一种。现在我们把前面的代码换成使用虚拟头结点来做。

5. 链表的查询

为了练习还是引入索引。

注意查询是要查询哪个结点，像前面的插入操作是为了查询某位置的前一个结点。下面的查询是为了查询某位置的结点。

查询有两种方式，一种使用while，一种使用for。

    /**
     * 获取链表第index个元素（0~size）
     * @param index
     * @return
     */
    public E get(int index) {
   
        if(index < 0 || index >= size) {
   
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }
        // 查找第index位置的结点
        Node cur = dummyHead.next;
        for(int i = 0; i < index; i++) {
   
            cur = cur.next;
        }

        return cur.data;
    }

    /**
     * 获取首结点的值
     * @return
     */
    public E getFirst() {
   
        return get(0);
    }

    /**
     * 获取尾结点的值
     * @return
     */
    public E getLast() {
   
        return get(size - 1);
    }
    
    /**
     * 查询链表中是否包含元素data
     * @param data
     * @return
     */
    public boolean contains(E data) {
   
        Node cur = dummyHead.next;
        while(cur != null) {
   
            if(cur.data.equals(data)) {
   
                return true;
            }
            cur = cur.next;
        }
        
        return false;
    }

    @Override
    public String toString() {
   
        StringBuilder sb = new StringBuilder();
        
        // 第一种，使用while
        // Node cur = dummyHead.next;
        // while(cur != null) {
   
        //     sb.append(cur + "->");
        //     cur = cur.next;
        // }

        // 第二种，使用for
        for(Node cur = dummyHead.next; cur != null; cur = cur.next) {
   
            sb.append(cur + "->");
        }

        sb.append("NULL");
        
        return sb.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
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

最好测试一下：

    public static void main(String[] args) {
   
        LinkedList<Integer> linkedList = new LinkedList<>();
1
2