链表

收录于

学习数据结构与算法

2021-05-17 14:29 · 阅读时长13分钟

链表也是多个元素的集合，但是这些元素在内存中并不是连续存储，而是通过额外存储的下一个节点指针来实现逻辑上的顺序连接。链表的节点一般由两个部分组成，一是数据，二是指向下一个节点的指针。链表有以下特点。

链表中的元素在内存上是不连续存储。
无需提前申请空间，链表长度自由扩展。

链表的优点有，删除和插入元素效率高，时间复杂度是O(1)，但是访问特定节点效率低，需要逐个节点遍历。

例如，链表[1,2,3,4,5,6,7,8,9,10]的存储结构如下：

链表

123

0x18

0x12

存储的值

下一个节点的内存地址

内存地址

Head
1
0x01
0x00
Head
2
0x07
0x01
Head
3
0x02
0x07
Head
4
0x03
0x02
Head
5
0x09
0x03
Head
6
0x04
0x09
Head
7
0x05
0x04
Head
8
0x08
0x05
Head
9
0x06
0x08
Head
10
null
0x06

链表也是非常基础的数据结构，很多其它数据结构的底层数据存储方式都可以用链表来实现。比如说List、Stack、Queue等等。

常见的链表有以下这些。

单链表，没有特殊说明，一般指的就是单链表。
双向链表，相比单链表，在每个节点多加一个指向上一个节点的指针，这样就能够更灵活的操作链表。
循环链表，将非循环链表的最后一个节点的next指针指向第一个节点，形成一个环路，就是循环链表，从循环链表的任何一个节点出发都能遍历整个链表。

1/**
2 * 自定义链表，实现增删改查
3 */
4class ZXLinkedList<T> {
5    /**
6     * 方便测试，初始容量设置小一点
7     */
8    private static final int DEFAULT_CAPACITY = 2;
9    private int size;
10    private Node head;
11
12    class Node {
13        T val;
14        Node next;
15
16        Node(T val) {
17            this.val = val;
18        }
19    }
20
21    public int size() {
22        return size;
23    }
24
25    public void add(T value) {
26        if (head == null) {
27            head = new Node(value);
28        } else {
29            Node n = head;
30            while (n.next != null) {
31                n = n.next;
32            }
33            n.next = new Node(value);
34        }
35        size++;
36    }
37
38    public void remove(int index) {
39        if (index >= size || index < 0) {
40            throw new ArrayIndexOutOfBoundsException(index);
41        }
42        if (index == 0) {
43            head = head.next;
44        } else {
45            Node n = head;
46            while (--index > 0) {
47                n = n.next;
48            }
49            n.next = n.next.next;
50        }
51        size--;
52    }
53
54    public void set(int index, T value) {
55        if (index >= size || index < 0) {
56            throw new ArrayIndexOutOfBoundsException(index);
57        }
58        Node n = head;
59        while (index-- > 0) {
60            n = n.next;
61        }
62        n.val = value;
63    }
64
65    @SuppressWarnings("unchecked")
66    public T get(int index) {
67        if (index >= size || index < 0) {
68            throw new ArrayIndexOutOfBoundsException(index);
69        }
70        Node n = head;
71        while (index-- > 0) {
72            n = n.next;
73        }
74        return (T) n.val;
75    }
76
77    @Override
78    public String toString() {
79        StringBuilder sb = new StringBuilder("[");
80        Node n = head;
81        for (int i = 0; i < size; i++) {
82            sb.append(n.val);
83            if (i != size - 1) {
84                sb.append(",");
85            } else {
86                sb.append("]");
87            }
88            n = n.next;
89        }
90        return sb.toString();
91    }
92}
93
94public class Main {
95
96    public static void main(String[] args) {
97        ZXLinkedList<Integer> list = new ZXLinkedList<>();
98        for (int i = 0; i < 20; i++) {
99            list.add(i);
100        }
101        assert list.size() == 20;
102        list.remove(list.size() - 1);
103        assert list.size() == 19;
104        list.set(0, 99);
105        assert list.get(0) == 99;
106
107        System.out.println(list);
108    }
109}
110

/**
 * 自定义链表，实现增删改查
 */
class ZXLinkedList<T> {
    /**
     * 方便测试，初始容量设置小一点
     */
    private static final int DEFAULT_CAPACITY = 2;
    private int size;
    private Node head;

class Node {
        T val;
        Node next;

Node(T val) {
            this.val = val;
        }
    }

public int size() {
        return size;
    }

public void add(T value) {
        if (head == null) {
            head = new Node(value);
        } else {
            Node n = head;
            while (n.next != null) {
                n = n.next;
            }
            n.next = new Node(value);
        }
        size++;
    }

public void remove(int index) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        if (index == 0) {
            head = head.next;
        } else {
            Node n = head;
            while (--index > 0) {
                n = n.next;
            }
            n.next = n.next.next;
        }
        size--;
    }

public void set(int index, T value) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        Node n = head;
        while (index-- > 0) {
            n = n.next;
        }
        n.val = value;
    }

@SuppressWarnings("unchecked")
    public T get(int index) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        Node n = head;
        while (index-- > 0) {
            n = n.next;
        }
        return (T) n.val;
    }

@Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node n = head;
        for (int i = 0; i < size; i++) {
            sb.append(n.val);
            if (i != size - 1) {
                sb.append(",");
            } else {
                sb.append("]");
            }
            n = n.next;
        }
        return sb.toString();
    }
}

public class Main {

public static void main(String[] args) {
        ZXLinkedList<Integer> list = new ZXLinkedList<>();
        for (int i = 0; i < 20; i++) {
            list.add(i);
        }
        assert list.size() == 20;
        list.remove(list.size() - 1);
        assert list.size() == 19;
        list.set(0, 99);
        assert list.get(0) == 99;

System.out.println(list);
    }
}

注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main

跟链表相关的题目，最经典的应该就是下面这道链表反转的题目。

反转链表

给你单链表的头节点head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题目链接：https://leetcode-cn.com/problems/reverse-linked-list

注释

链表可以选用迭代或递归方式完成反转。

另外一道经典的题目，检测链表是否有环。

环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true

3→2→0→-4
↑_____↓

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true

1→2
↑_↓

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false

解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个有效索引。

题目链接：https://leetcode-cn.com/problems/linked-list-cycle

注释

判断是否有环，实际上也可以理解为链表节点是否会重复，所以最容易想到的是遍历链表，然后用哈希表来判断节点是否有重复，这种解法空间复杂度为O(N)。下面介绍一种O(1)的解法，还是用之前提到的双指针的技巧，准确来讲应该叫快慢指针，因为每一轮循环第一个指针（快指针）会走两步，而慢指针只走一步，这样如果链表有环的话，两个指针最终会在同一个节点相遇。

链表LinkedList单链表反转链表

链表

学习数据结构与算法

反转链表

环形链表

数组

栈