rust_algo/
linked_list.rs

1/*
2ArenaList，相当于对象池
3删除时节点置 None，常数复杂度
4
5用 nodes: Vec<Option<T>> + nexts: Vec<Option<usize>> 来管理节点数据，以及节点指向的下一个序号
6也可以用 nodes: Vec<NodeInfo<T>> 来管理，其中 NodeInfo{data, next_idx}
7
8holes 用来存放孔洞，出现孔洞后，后续的插入优先使用孔洞。孔洞的使用是用 栈 的方式
9*/
10
11
12pub struct ArenaList<T> {
13    pub nodes: Vec<Option<T>>,
14    // 存放数据本身
15    pub nexts: Vec<Option<usize>>,
16    // 存放节点指向的下一个节点。若为 None，表示没有下一个节点
17    pub holes: Vec<usize>,
18    // 存放孔洞对应的 index
19}
20
21impl<T> ArenaList<T> {
22    fn new() -> Self {
23        Self {
24            nodes: Vec::new(),
25            nexts: Vec::new(),
26            holes: Vec::new(),
27        }
28    }
29
30    //     新增一个节点，并返回其索引号
31    fn make_node(&mut self, data: Option<T>) -> usize {
32        match self.holes.pop() {
33            // 如果有空洞，新数据放到空洞上
34            Some(new_idx) => {
35                self.nodes[new_idx] = data;
36                self.nexts[new_idx] = None;
37                new_idx
38            }
39            // 如果没有空洞
40            None => {
41                self.nodes.push(data);
42                self.nexts.push(None);
43                self.nexts.len() - 1
44            }
45        }
46    }
47}
48
49pub struct LinkedList<'a, T> {
50    root: usize,
51    //根节点id
52    owner: &'a mut ArenaList<T>,
53}
54
55impl<'a, T> LinkedList<'a, T> {
56    fn from_vec(arena_list: &'a mut ArenaList<T>, vec1: Vec<T>) -> Self {
57        let dummy = arena_list.make_node(None);
58        let mut prev = dummy;
59        for data in vec1 {
60            let curr = arena_list.make_node(Some(data));
61            arena_list.nexts[prev] = Some(curr);
62            prev = curr;
63        }
64
65        Self {
66            root: dummy,
67            owner: arena_list,
68        }
69    }
70
71    fn clear() {}
72
73
74    fn to_vec(&self) -> Vec<&T> {
75        let mut res = Vec::new();
76        let mut curr_idx = self.root;
77        loop {
78            match self.owner.nexts[curr_idx] {
79                Some(next_idx) => {
80                    // 应该不会出现对应 next 不为 None，但 nodes 为 None 的情况
81                    match &self.owner.nodes[next_idx] {
82                        Some(node_data) => res.push(node_data),
83                        None => break
84                    }
85                    curr_idx = next_idx;
86                }
87                None => break
88            }
89        }
90        res
91    }
92
93    fn get(&self, mut num: usize) -> &Option<T> {
94        let mut curr_idx = self.root;
95        loop {
96            match self.owner.nexts[curr_idx] {
97                Some(next_idx) => {
98                    if num == 0 {
99                        return &self.owner.nodes[next_idx];
100                    }
101                    curr_idx = next_idx;
102                    num -= 1;
103                }
104                None => { return &None; }
105            }
106        }
107    }
108
109    fn insert(&mut self, mut num: usize, data: T) {
110        let new_idx = self.owner.make_node(Some(data));
111        let mut curr_idx = self.root;
112        loop {
113            match self.owner.nexts[curr_idx] {
114                Some(next_idx) => {
115                    if num == 0 {
116                        self.owner.nexts[new_idx] = Some(next_idx);
117                        self.owner.nexts[curr_idx] = Some(new_idx);
118                        curr_idx = new_idx;
119                        break;
120                    }
121                    curr_idx = next_idx;
122                    num -= 1;
123                }
124                None => break
125            }
126        }
127    }
128
129
130    fn del(&mut self, mut num: usize) -> bool {
131        let mut curr_idx = self.root;
132        loop {
133            match self.owner.nexts[curr_idx] {
134                Some(next_idx) => {
135                    if num == 0 {
136                        self.owner.nexts[curr_idx] = self.owner.nexts[next_idx];
137                        self.owner.nexts[next_idx] = None;
138                        self.owner.nodes[next_idx] = None;
139                        self.owner.holes.push(next_idx);
140                        return true;
141                    }
142                    curr_idx = next_idx;
143                    num -= 1;
144                }
145                None => {
146                    return false;
147                }
148            }
149        }
150    }
151}
152
153impl<'a, T> LinkedList<'a, T> {
154    // 示例：如何操作多个 Linked List
155    // 多个 Linked List 的节点存放在同一个 arena_list。只是不同的 LinkedList 对象的 root 节点不一样
156    fn split(&mut self, mut num: usize) -> LinkedList<T> {
157        let dummy = self.owner.make_node(None);
158        let mut curr_idx = self.root;
159        loop {
160            match self.owner.nexts[curr_idx] {
161                Some(next_idx) => {
162                    if num == 0 {
163                        self.owner.nexts[dummy] = Some(next_idx);
164                        self.owner.nexts[curr_idx] = None;
165                        break;
166                    }
167                    curr_idx = next_idx;
168                    num -= 1;
169                }
170                None => { break; }
171            }
172        }
173        LinkedList { root: dummy, owner: self.owner }
174    }
175}
176
177#[cfg(test)]
178mod tests {
179    use crate::linked_list::{ArenaList, LinkedList};
180
181    #[test]
182    fn test1() {
183        let mut arena_list = ArenaList::new();
184        let vec1 = vec![1, 2, 3, 4, 5, 6];
185        let mut linked_list = LinkedList::from_vec(&mut arena_list, vec1);
186        println!("{:?}", linked_list.to_vec());
187        linked_list.insert(3, 9);
188        linked_list.insert(0, 99);
189        println!("{:?}", linked_list.to_vec());
190        println!("index = {}, val = {:?}", 0, linked_list.get(0));
191        println!("index = {}, val = {:?}", 3, linked_list.get(3));
192        println!("index = {}, val = {:?}", 8, linked_list.get(8));
193        linked_list.del(3);
194        linked_list.del(2);
195        println!("{:?}", linked_list.to_vec());
196    }
197
198    #[test]
199    fn test2() {
200        let mut arena_list = ArenaList::new();
201        let vec1 = vec![1, 2, 3, 4, 5, 6];
202        let mut linked_list1 = LinkedList::from_vec(&mut arena_list, vec1);
203        let mut linked_list2 = linked_list1.split(3);
204        println!("{:?}", linked_list2.to_vec());
205        println!("{:?}", linked_list1.to_vec());
206    //     颠倒过来会发生生命周期冲突，之后解决
207    }
208}
209
210
211
rust_algo/linked_list.rs

rust_algo/
linked_list.rs
