Rust数据结构

Posted by Hao Blog on January 11, 2026

[toc]

链表

单链表

带有头节点的单链表的实现

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

use std::fmt::Display;
use std::cmp::PartialEq;

#[derive(Debug)]
struct Node<T> {
    elem: T,
    next: Option<Box<Node<T>>>,
}

#[derive(Debug)]
pub struct SentinelLinkedList<T> {
    head: Box<Node<T>>, // 哨兵节点
}

// 泛型约束：必须的4个trait，缺一不可
impl<T: Display + Copy + Default + PartialEq> SentinelLinkedList<T> {
    pub fn new() -> Self {
        SentinelLinkedList {
            head: Box::new(Node {
                elem: T::default(),
                next: None,
            }),
        }
    }

    // ✅ 尾插法 - 无报错写法
    pub fn push_back(&mut self, elem: T) {
        let mut curr = &mut self.head;
        while curr.next.is_some() {
            curr = curr.next.as_mut().unwrap();
        }
        curr.next = Some(Box::new(Node { elem, next: None }));
    }

    // ✅ 头插法 - 永远无报错
    pub fn push_front(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem,
            next: self.head.next.take(),
        });
        self.head.next = Some(new_node);
    }

    // ✅ ✅ ✅ 【终极修复】remove方法 - 100%无E0506，无unsafe，所有权转移写法
    pub fn remove(&mut self, elem: T) -> bool {
        let mut curr = &mut self.head;
        // 遍历到尾部为止
        while curr.next.is_some() {
            // 核心关键：take() 拿走 curr.next 的所有权，原地留 None，彻底解除所有借用绑定
            let mut node = curr.next.take().unwrap();
            
            if node.elem == elem {
                // ✅ 直接赋值，无任何借用冲突！因为curr.next已经是None，无任何借用
                curr.next = node.next;
                return true;
            } else {
                // ✅ 不是目标节点，把节点塞回去，继续遍历
                curr.next = Some(node);
                // 安全转移可变引用，继续下一轮
                curr = curr.next.as_mut().unwrap();
            }
        }
        // 遍历完没找到，返回false
        false
    }

    // ✅ 打印链表 - 无报错
    pub fn print_list(&self) {
        let mut curr = &self.head.next;
        if curr.is_none() {
            println!("链表为空");
            return;
        }
        print!("哨兵链表：");
        while let Some(node) = curr {
            print!("{} -> ", node.elem);
            curr = &node.next;
        }
        println!("None");
    }
}

// 测试代码 - 全部运行正常
fn main() {
    let mut list = SentinelLinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_front(0);
    list.print_list(); // 哨兵链表：0 -> 1 -> 2 -> None
    list.remove(1);
    list.print_list(); // 哨兵链表：0 -> 2 -> None
    list.remove(0);
    list.print_list(); // 哨兵链表：2 -> None
    list.remove(2);
    list.print_list(); // 链表为空
}

没有头节点的单链表实现

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

use std::fmt::Display;

/// 定义单链表的节点结构
#[derive(Debug)]
struct Node<T> {
    // 节点存储的数据
    elem: T,
    // 指向下一个节点的指针，Box拥有所有权，Option表示可选（None代表链表尾部）
    next: Option<Box<Node<T>>>,
}

/// 定义单链表结构，只持有头节点
#[derive(Debug)]
pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T: Display + Copy> LinkedList<T> {
    /// 关联函数：创建一个空链表
    pub fn new() -> Self {
        LinkedList { head: None }
    }

    /// 头插法：在链表头部添加元素，时间复杂度 O(1)
    pub fn push_front(&mut self, elem: T) {
        // 创建新节点，新节点的next指向原链表的头节点
        let new_node = Box::new(Node {
            elem,
            next: self.head.take(), // take() 拿走Option的值，原地留下None，转移所有权
        });
        // 链表头节点更新为新节点
        self.head = Some(new_node);
    }

    /// 尾插法：在链表尾部添加元素，时间复杂度 O(n)
    pub fn push_back(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem,
            next: None,
        });

        // 指针从头节点开始遍历，需要可变引用
        let mut curr = &mut self.head;
        // 遍历到链表尾部（next为None的位置）
        while let Some(node) = curr {
            curr = &mut node.next;
        }
        // 在尾部插入新节点
        *curr = Some(new_node);
    }

    /// 按索引获取元素（只读，返回Option），索引从0开始
    pub fn get(&self, index: usize) -> Option<&T> {
        let mut curr = &self.head;
        let mut curr_idx = 0;

        while let Some(node) = curr {
            if curr_idx == index {
                return Some(&node.elem);
            }
            curr = &node.next;
            curr_idx += 1;
        }
        // 索引越界返回None
        None
    }

    /// 删除链表的头节点，并返回被删除的元素，时间复杂度 O(1)
    pub fn pop_front(&mut self) -> Option<T> {
        // take() 转移头节点的所有权
        self.head.take().map(|node| {
            // 将头节点更新为原头节点的后继节点
            self.head = node.next;
            // 返回被删除节点的数据
            node.elem
        })
    }

    /// 获取链表的长度，时间复杂度 O(n)
    pub fn len(&self) -> usize {
        let mut curr = &self.head;
        let mut count = 0;
        while let Some(node) = curr {
            count += 1;
            curr = &node.next;
        }
        count
    }

    /// 判断链表是否为空
    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    /// 清空链表，所有权回收
    pub fn clear(&mut self) {
        self.head = None;
    }

    /// 遍历链表并打印所有元素
    pub fn print_list(&self) {
        if self.is_empty() {
            println!("链表为空");
            return;
        }
        let mut curr = &self.head;
        print!("链表元素：");
        while let Some(node) = curr {
            print!("{} -> ", node.elem);
            curr = &node.next;
        }
        println!("None");
    }
}

// 测试代码
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_linked_list() {
        let mut list = LinkedList::new();
        assert!(list.is_empty());
        assert_eq!(list.len(), 0);

        // 头插法添加元素
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        list.print_list(); // 3 -> 2 -> 1 -> None
        assert_eq!(list.len(), 3);
        assert_eq!(list.get(0), Some(&3));
        assert_eq!(list.get(1), Some(&2));
        assert_eq!(list.get(2), Some(&1));
        assert_eq!(list.get(3), None); // 越界

        // 尾插法添加元素
        list.push_back(4);
        list.print_list(); // 3 -> 2 -> 1 ->4 -> None
        assert_eq!(list.len(),4);
        assert_eq!(list.get(3), Some(&4));

        // 删除头节点
        assert_eq!(list.pop_front(), Some(3));
        list.print_list(); // 2 ->1 ->4 -> None
        assert_eq!(list.len(),3);

        // 清空链表
        list.clear();
        assert!(list.is_empty());
        assert_eq!(list.pop_front(), None);
    }
}

双向链表

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

use std::cell::RefCell;
use std::rc::Rc;

// 1. 定义双向链表的节点结构
#[derive(Debug)]
struct Node<T> {
    // 节点存储的数据
    value: T,
    // 前驱节点：Option包裹，Rc共享所有权，RefCell提供内部可变性
    prev: Option<Rc<RefCell<Node<T>>>>,
    // 后继节点：同前驱节点的类型
    next: Option<Rc<RefCell<Node<T>>>>,
}

impl<T> Node<T> {
    // 节点的构造函数：传入数据，前驱和后继默认是空
    fn new(value: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            value,
            prev: None,
            next: None,
        }))
    }
}

// 2. 定义双向链表的结构体
#[derive(Debug)]
pub struct DoublyLinkedList<T> {
    // 链表头节点
    head: Option<Rc<RefCell<Node<T>>>>,
    // 链表尾节点
    tail: Option<Rc<RefCell<Node<T>>>>,
    // 链表长度（可选，但是推荐，避免每次求长度都遍历链表）
    length: usize,
}

impl<T> DoublyLinkedList<T> {
    // 链表的构造函数：创建空链表
    pub fn new() -> Self {
        DoublyLinkedList {
            head: None,
            tail: None,
            length: 0,
        }
    }

    // 3. 核心操作1：判断链表是否为空
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    // 4. 核心操作2：获取链表长度
    pub fn len(&self) -> usize {
        self.length
    }

    // 5. 核心操作3：尾部插入元素（尾插法，最常用）
    pub fn push_back(&mut self, value: T) {
        let new_node = Node::new(value);
        match self.tail.take() {
            // 情况1：链表原本非空
            Some(old_tail) => {
                // 原尾节点的后继 指向 新节点
                old_tail.borrow_mut().next = Some(new_node.clone());
                // 新节点的前驱 指向 原尾节点
                new_node.borrow_mut().prev = Some(old_tail);
                // 链表的尾节点 更新为 新节点
                self.tail = Some(new_node);
            }
            // 情况2：链表原本为空，头和尾都指向新节点
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
        self.length += 1;
    }

    // 6. 核心操作4：头部插入元素（头插法）
    pub fn push_front(&mut self, value: T) {
        let new_node = Node::new(value);
        match self.head.take() {
            // 情况1：链表原本非空
            Some(old_head) => {
                // 原头节点的前驱 指向 新节点
                old_head.borrow_mut().prev = Some(new_node.clone());
                // 新节点的后继 指向 原头节点
                new_node.borrow_mut().next = Some(old_head);
                // 链表的头节点 更新为 新节点
                self.head = Some(new_node);
            }
            // 情况2：链表原本为空，头和尾都指向新节点
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
        self.length += 1;
    }

    // 7. 核心操作5：尾部删除元素（尾删法），返回删除的元素值
    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                // 情况1：链表中不止一个节点
                Some(new_tail) => {
                    // 新尾节点的后继置空
                    new_tail.borrow_mut().next.take();
                    // 链表的尾节点更新为新尾节点
                    self.tail = Some(new_tail);
                }
                // 情况2：链表中只有一个节点，删除后链表为空
                None => {
                    self.head.take();
                }
            }
            self.length -= 1;
            // 把Rc的引用计数减1，并取出内部的Node，最终返回数据
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().value
        })
    }

    // 8. 核心操作6：头部删除元素（头删法），返回删除的元素值
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                // 情况1：链表中不止一个节点
                Some(new_head) => {
                    // 新头节点的前驱置空
                    new_head.borrow_mut().prev.take();
                    // 链表的头节点更新为新头节点
                    self.head = Some(new_head);
                }
                // 情况2：链表中只有一个节点，删除后链表为空
                None => {
                    self.tail.take();
                }
            }
            self.length -= 1;
            // 取出节点内部的值并返回
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().value
        })
    }

    // 9. 核心操作7：正向遍历链表，执行闭包操作（比如打印）
    pub fn iter_forward<F>(&self, mut f: F)
    where
        F: FnMut(&T),
    {
        let mut current = self.head.clone();
        while let Some(node) = current {
            f(&node.borrow().value);
            current = node.borrow().next.clone();
        }
    }

    // 10. 核心操作8：反向遍历链表，执行闭包操作（双向链表优势）
    pub fn iter_backward<F>(&self, mut f: F)
    where
        F: FnMut(&T),
    {
        let mut current = self.tail.clone();
        while let Some(node) = current {
            f(&node.borrow().value);
            current = node.borrow().prev.clone();
        }
    }
}

// 测试代码
fn main() {
    let mut list = DoublyLinkedList::new();

    // 尾插元素
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    println!("链表长度: {}", list.len()); // 输出：3
    print!("正向遍历: ");
    list.iter_forward(|v| print!("{} ", v)); // 输出：1 2 3
    println!();

    // 头插元素
    list.push_front(0);
    print!("头插0后正向遍历: ");
    list.iter_forward(|v| print!("{} ", v)); // 输出：0 1 2 3
    println!();

    // 反向遍历
    print!("反向遍历: ");
    list.iter_backward(|v| print!("{} ", v)); // 输出：3 2 1 0
    println!();

    // 尾删、头删
    println!("尾删元素: {:?}", list.pop_back()); // 输出：Some(3)
    println!("头删元素: {:?}", list.pop_front()); // 输出：Some(0)
    print!("删除后正向遍历: ");
    list.iter_forward(|v| print!("{} ", v)); // 输出：1 2
    println!();
    println!("最终链表长度: {}", list.len()); // 输出：2
}
CATALOG