数据结构之线性结构和链表基础

线性结构简介

数据是散落在内存荒原上的沙砾，人类文明用线性结构在数字世界中铺就了第一条道路。在算法世界的版图里，线性结构是所有复杂架构的基石。它的定义看似朴素：数据元素之间存在着 “一对一” 的关系，除了首尾，每个节点都有且仅有一个前驱和后继。然而，在这种极简的几何关系背后，隐藏着计算机科学中最深刻的博弈——物理连续性与逻辑灵活性之间的较量。这种线性结构的演化，本质上是人类在访问速度与组织成本之间寻找平衡点的过程。无论是栈的内敛、队列的规整，还是哈希表的奔放，其底层逻辑都逃不开数组与链表这两大元思想的纠缠。


物理的刚性：数组（Array）

数组是线性结构的 “守旧派”。它在内存中圈定一块连续的领土，赋予每个元素一个永恒的编号（索引）。这种对物理空间的极致榨取，换来了 $O(1)$ 级别的随机访问速度。它是追求极致读取效率时的首选，但也必须承受 “牵一发而动全身” 的插入成本。


逻辑的韧性：链表 (Linked List)

链表则是线性结构的 “自由派”。它不要求领土的连贯，而是通过指针（Pointer）在散乱的内存间拉起一条若隐若现的纤绳。它放弃了瞬间定位的能力，却换取了在任何位置“随进随出”的潇洒。它是动态内存管理的灵魂，也是实现高级数据结构的原材料。


常见链表

单链表

为了让 addLast 不再遍历链表，我增加了对 tail 指针的维护（用空间换时间），这也是链表优化的必经之路。

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
/**
 * @author KJ
 * @description 单链表
 */
public class MyLinkedList {
    private static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    private Node head; // 头节点
    private Node tail; // 尾节点（始终指向最后一个元素，优化尾部操作）
    private int size;  // 链表长度

    /**
     * 头部插入 - O(1)
     */
    public void addFirst(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head = node;
        }
        size++;
    }

    /**
     * 尾部插入 - 优化后也为 O(1)
     */
    public void addLast(int data) {
        if (head == null){
            addFirst(data);
            return;
        }
        // 直接利用 tail 指针
        Node node = new Node(data);
        tail.next = node;
        tail = node;
        size++;
    }

    /**
     * 删除第一个匹配项 - O(n)
     */
    public void remove(int data) {
        if (head == null) {
            return;
        }

        // 1. 特殊处理头节点：如果要删的是头，直接移动指针
        if (head.data == data) {
            head = head.next;
            if (head == null) tail = null; // 删完后链表空了则同步更新tail
            size--;
            return;
        }

        // 2. 遍历查找后续节点
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.data == data) {
                if (cur.next == tail) tail = cur; // 删的是做后一个节点则也同步更新tail
                cur.next = cur.next.next;
                size--;
                return;
            }
            cur = cur.next;
        }
    }

    /**
     * 删除所有匹配项 - O(n)
     */
    public void removeAll(int data) {
        if (head == null) {
            return;
        }

        // 虚拟头节点遍历法
        Node h = new Node(0);
        h.next = head;
        Node cur = h;
        while (cur.next != null) {
            if (cur.next.data == data) {
                if (cur.next== tail) tail = cur;  // 删的是做后一个节点则也同步更新tail
                cur.next = cur.next.next;  // 发现目标则删除
                size--;
            } else {
                cur = cur.next; // 否则指针向后走
            }
        }

        // 更新 head（因为原 head 也可能被删除）
        head = h.next;
        if (head== null) tail = null; // 删完后链表空了则同步更新tail
    }

    /**
     * 清空全部 - O(1)
     */
    public void clean() {
        head = tail = null;
        size = 0;
    }

    /**
     * 打印链表
     */
    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + "->");
            cur = cur.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addFirst(20);
        list.addFirst(20);
        list.addFirst(10);
        list.addLast(30);
        list.addLast(30);
        list.print();  // 输出: 10->20->20->30->30->null

        list.remove(20);
        list.print();  // 输出: 10->20->30->30->null

        list.removeAll(30);
        list.print();  // 输出: 10->20->null

        list.clean();
        list.print();  // 输出: null
    }
}


双链表

在单链表中，我们最痛苦的莫过于 “无法回头”。即使有了 tail 指针，想删除最后一个节点，由于找不到前驱节点，我们还是得从头跑一遍。双向链表通过多出一个 prev 指针，彻底打破了这个僵局。

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
/**
 * @author KJ
 * @description 双向链表
 */
public class MyDoubleLinkedList {
    private static class Node {
        int data;
        Node prev;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    private Node head;
    private Node tail;
    private int size;

    /**
     * 头插 - O(1)
     */
    public void addFirst(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
        size++;
    }

    /**
     * 尾插 - O(1)
     */
    public void addLast(int data) {
        if (head == null) {
            addFirst(data);
            return;
        }
        Node node = new Node(data);
        tail.next = node;
        node.prev = tail;
        tail = node;
        size++;
    }

    /**
     * 删头 - O(1)
     */
    public void removeFirst() {
        if (head == null) {
            return;
        }
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        size--;
    }

    /**
     * 删尾 - O(1)
     */
    public void removeLast() {
        if (tail == null) return;

        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev; // 核心：直接通过 prev 找到前驱
            tail.next = null; // 切断与旧尾的连接
        }
        size--;
    }

    /**
     * 删除第一个匹配 - O(n)
     */
    public void remove(int data) {
        Node cur = head;
        while (cur != null) {
            if (cur.data == data) {
                unlink(cur); // 抽离核心删除逻辑
                return;
            }
            cur = cur.next;
        }
    }

    /**
     * 删除所有匹配项 - O(n)
     */
    public void removeAll(int data) {
        Node cur = head;
        while (cur != null) {
            if (cur.data == data) {
                Node nextNode = cur.next;
                unlink(cur);
                cur = nextNode;
            } else {
                cur = cur.next;
            }
        }
    }

    /**
     * 核心逻辑：断开指定节点的连接 (Unlink)
     * 这是双向链表最优雅的地方，处理好前后指针即可
     */
    private void unlink(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;

        // 处理前驱
        if (prevNode == null) {
            head = nextNode; // 说明删的是头
        } else {
            prevNode.next = nextNode;
            node.prev = null;
        }

        // 处理后继
        if (nextNode == null) {
            tail = prevNode; // 说明删的是尾
        } else {
            nextNode.prev = prevNode;
            node.next = null;
        }

        // 长度减一
        size--;
    }

    /**
     * 清空链表 - O(n)
     * 在双向链表中，为了帮助 GC，建议遍历断开所有引用
     */
    public void clean() {
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = next;
        }
        head = tail = null;
        size = 0;
    }

    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " <-> ");
            cur = cur.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        MyDoubleLinkedList list = new MyDoubleLinkedList();
        list.addLast(10);
        list.addLast(20);
        list.addLast(20);
        list.addLast(30);
        list.print(); // 10 <-> 20 <-> 20 <-> 30 <-> null

        list.remove(20);
        list.print(); // 10 <-> 20 <-> 30 <-> null

        list.removeAll(20);
        list.addFirst(5);
        list.print(); // 5 <-> 10 <-> 30 <-> null

        list.clean();
        list.print(); // null
    }
}


循环链表

循环链表是将线性表的终点重新连接到起点，使数据流成了一个永无止境的环。在实际开发中，循环链表最著名的应用场景就是操作系统的时间片轮转调度（Round Robin），以及经典的数学问题：约瑟夫环。

假设有 n​ 个人围成一圈，从第一个人开始报数，报到 m 的人出列。 循环链表不需要像数组那样不断地搬运数据，它只需要像时钟拨针一样转动指针，剔除节点即可。

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
/**
 * @author KJ
 * @description 双向循环链表
 */
public class MyCircularLinkedList {
    private static class Node {
        int data;
        Node prev;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    private Node head;
    private int size;

    /**
     * 插入节点 - O(1)
     */
    public void addNode(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            node.next = head;
            node.prev = head;
        } else {
            // 循环链表中，head.prev 永远是尾巴
            Node tail = head.prev;
            // 重新编织四个指针
            node.next = head;
            node.prev = tail;
            head.prev = node;
            tail.next = node;
        }
        size++;
    }

    /**
     * 删除节点
     *
     * @param targetNode 被删除节点
     * @return 返回被删除的节点
     */
    private void removeNode(Node targetNode) {
        if (size == 1) {
            head = null;
        } else {
            targetNode.prev.next = targetNode.next;
            targetNode.next.prev = targetNode.prev;
            // 如果是 head 出了列，要把 head 引用重置，否则程序找不到环
            if (targetNode == head) {
                head = targetNode.next;
            }
        }
        size--;
    }

    /**
     * 打印环（防止死循环，我们只打印一圈）
     */
    public void print() {
        if (head == null) return;
        Node cur = head;
        do {
            System.out.print(cur.data + " <-> ");
            cur = cur.next;
        } while (cur != head); // 回到起点就停止
        System.out.println("(Back to Head: " + head.data + ")");
    }


    /**
     * 构造一个包含 n 个人的环
     */
    public void createCircle(int n) {
        for (int i = 1; i <= n; i++) {
            addNode(i);
        }
    }

    /**
     * 核心逻辑：约瑟夫出列
     *
     * @param k 从第几个人开始报数 (通常为 1)
     * @param m 报数到 m 的人出列
     */
    public void josephusSolve(int k, int m) {
        if (head == null || m < 1) return;

        // 1. 先把指针移到起始报数人 k
        Node cur = head;
        for (int i = 1; i < k; i++) {
            cur = cur.next;
        }
        System.out.println("--- 约瑟夫环出列顺序 ---");

        // 2. 循环直到只剩一个人
        while (size > 1) {
            // 报数：移动 m-1 次到达目标
            for (int i = 1; i < m; i++) {
                cur = cur.next;
            }

            // 3. 出列逻辑
            System.out.print(cur.data + " -> ");
            removeNode(cur);

            // 从下一个人开始重新报数
            cur = cur.next;
        }
        System.out.println("\n最后留下的幸运儿是: " + cur.data);
    }

    public static void main(String[] args) {
        MyCircularLinkedList cl = new MyCircularLinkedList();
        cl.createCircle(5);
        cl.josephusSolve(1,4); // 4 -> 3 -> 5 -> 2 ->  最后留下的幸运儿是: 1
    }
}


标题：
数据结构之线性结构和链表基础
作者：
kinglyjn
声明：
引用 本文 请务必注明出处，原创不易，感谢尊重。