rust_algo/
double_linked_list.rs

1pub struct Node<T> {
2    data: Option<T>,
3    pub next_idx: Option<usize>,
4    pub prev_idx: Option<usize>,
5}
6
7pub struct ArenaList<T> {
8    pub nodes: Vec<Node<T>>,
9    pub len: usize,
10}
11
12
13pub struct DoubleLinkedList<'a, T> {
14    pub root_idx: usize,
15    owner: &'a mut ArenaList<T>,
16}
17
18
19impl<T> ArenaList<T> {
20    pub fn new() -> Self {
21        Self {
22            nodes: Vec::new(),
23            len: 0,
24        }
25    }
26
27    fn clear(&mut self) {
28        self.nodes.clear();
29    }
30
31    // 新增一个节点
32    fn add_node(&mut self, data: Option<T>) -> usize {
33        self.nodes.push(
34            Node { data, next_idx: None, prev_idx: None }
35        );
36        self.len += 1;
37        self.len - 1
38    }
39
40    // 连接两个节点
41    fn add_link(&mut self, src_idx: usize, dst_idx: usize) {
42        self.nodes[src_idx].next_idx = Some(dst_idx);
43        self.nodes[dst_idx].prev_idx = Some(src_idx);
44    }
45
46    //返回节点
47    fn get_node(&self, idx: usize) -> &Node<T> {
48        return &self.nodes[idx];
49    }
50
51
52    // 删除节点,并且把上游节点和下游节点连接起来
53    fn del_node(&mut self, idx: usize) -> bool {
54        if idx >= self.nodes.len() {
55            return false;
56        }
57
58        let last_idx = self.nodes.len() - 1;
59
60        let mut node_to_del = self.nodes.swap_remove(idx);
61
62        // 上游节点和下游节点
63        let src_idx = node_to_del.prev_idx;
64        let dst_idx = node_to_del.next_idx;
65
66
67        // step1: 上游节点不再指向它
68        match node_to_del.prev_idx {
69            None => { panic!("不可能") }
70            Some(prev_idx) => {
71                if prev_idx == last_idx {
72                    // 如果上游节点是最后一个,注意它已经被移动到 idx 位置了
73                    self.nodes[idx].next_idx = dst_idx;
74                } else {
75                    self.nodes[prev_idx].next_idx = dst_idx;
76                }
77            }
78        }
79
80        // step2:下游节点不再指向他
81        match node_to_del.next_idx {
82            None => {}
83            Some(next_idx) => {
84                if next_idx == last_idx {
85                    self.nodes[idx].prev_idx = src_idx;
86                } else {
87                    self.nodes[next_idx].prev_idx = src_idx;
88                }
89            }
90        }
91
92        if idx == last_idx {
93            return true;
94        }
95
96
97        // step3:被移动的节点,其上下游也要调整
98        match self.nodes[idx].prev_idx {
99            None => {}
100            Some(prev_idx) => {
101                if prev_idx == last_idx {
102                    //     上游节点是自己
103                    self.nodes[idx].next_idx = Some(idx);
104                } else { self.nodes[prev_idx].next_idx = Some(idx); }
105            }
106        }
107
108        match self.nodes[idx].next_idx {
109            None => {}
110            Some(next_idx) => {
111                if next_idx == last_idx {
112                    self.nodes[idx].prev_idx = Some(idx)
113                } else { self.nodes[next_idx].prev_idx = Some(idx); }
114            }
115        }
116
117
118        self.len -= 1;
119        true
120    }
121}
122
123impl<'a, T> DoubleLinkedList<'a, T> {
124    pub fn new(arena_list: &'a mut ArenaList<T>) -> Self {
125        let mut res = Self {
126            root_idx: 0,
127            owner: arena_list,
128        };
129        res.owner.add_node(None);
130        res
131    }
132
133    pub fn from_vec(arena_list: &'a mut ArenaList<T>, vec1: Vec<T>) -> DoubleLinkedList<T> {
134        let mut res = Self {
135            root_idx: arena_list.len,
136            owner: arena_list,
137        };
138
139        let mut curr_idx = res.root_idx;
140        res.owner.add_node(None);// dummy
141
142
143        for data in vec1 {
144            let next_idx = res.owner.add_node(Some(data));
145            res.owner.nodes[curr_idx].next_idx = Some(next_idx);
146            res.owner.nodes[next_idx].prev_idx = Some(curr_idx);
147            curr_idx = next_idx
148        }
149        res
150    }
151
152    pub fn to_vec(&self) -> Vec<&T> {
153        let mut curr_idx = self.root_idx;
154
155        let mut res = Vec::new();
156        loop {
157            match self.owner.nodes[curr_idx].next_idx {
158                None => { break; }
159                Some(next_idx) => {
160                    match &self.owner.nodes[next_idx].data {
161                        None => { break; }
162                        Some(data) => { res.push(data); }
163                    }
164                    curr_idx = next_idx;
165                }
166            }
167        }
168        res
169    }
170
171
172    // 增加节点
173    pub fn add_node(&mut self, data: Option<T>) -> usize {
174        self.owner.add_node(data)
175    }
176
177
178    // 获取节点
179    pub fn get_node_by_idx(&self, idx: usize) -> &Node<T> {
180        return self.owner.get_node(idx);
181    }
182
183
184    pub fn insert(&mut self, mut num: usize, data: T) {
185        let mut curr_idx = self.root_idx;
186        let new_idx = self.add_node(Some(data));
187
188        loop {
189            if num <= 0 {
190                match self.owner.nodes[curr_idx].next_idx {
191                    None => {}
192                    Some(next_idx) => {
193                        self.owner.add_link(new_idx, next_idx);
194                    }
195                }
196                self.owner.add_link(curr_idx, new_idx);
197
198                break;
199            }
200
201            match self.owner.nodes[curr_idx].next_idx {
202                None => break,
203                Some(next_idx) => {
204                    curr_idx = next_idx;
205                }
206            }
207
208            num -= 1;
209        }
210    }
211
212    pub fn get(&self, mut num: usize) -> Option<&T> {
213        let mut curr_idx = self.root_idx;
214        loop {
215            if num <= 0 {
216                match self.owner.nodes[curr_idx].next_idx {
217                    None => { return None; }
218                    Some(next_idx) => {
219                        return Option::from(&self.owner.nodes[next_idx].data);
220                    }
221                }
222            }
223            match self.owner.nodes[curr_idx].next_idx {
224                None => { return None; }
225                Some(next_idx) => {
226                    curr_idx = next_idx;
227                }
228            }
229            num -= 1;
230        }
231    }
232
233    pub fn del(&mut self, mut num: usize) {
234        let mut curr_idx = self.root_idx;
235        loop {
236            if num <= 0 {
237                match self.owner.nodes[curr_idx].next_idx {
238                    None => return,
239                    Some(next_idx) => { self.owner.del_node(next_idx); }
240                }
241                return;
242            }
243            match self.owner.nodes[curr_idx].next_idx {
244                None => { return; }
245                Some(next_idx) => curr_idx = next_idx
246            }
247            num -= 1;
248        }
249    }
250}