remove_from_indexメソッドを実装する。
成果物
間にあるノードを削除する
リストのノードが以下の状態だったとする。このとき、secondを削除したい。list.remove_from_index(1);で実行する。
first second third +-----------+-----------+ +-----------+-----------+ +-----------+-----------+ |item |next | |item |next | |item |next | +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |00|00|00|01|00|00|00|08| |00|00|00|02|00|00|00|10| |00|00|00|03|FF|FF|FF|FF| +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17
期待する状態は以下。
first third +-----------+-----------+ +-----------+-----------+ |item |next | |item |next | +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |00|00|00|01|00|00|00|10| |00|00|00|03|FF|FF|FF|FF| +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17
first.nextがthirdの先頭アドレスになる。つまり、削除対象ノードの一つ前のノードがもつnextに、削除対象ノードがもつnextの値をセットする。first.next = second.nextのように。
ただし、インデックス値次第では、先頭にも末尾にもなりうる。それぞれnextの付替に異なる操作が必要なため、条件分岐すべき。
| 削除対象の位置 | nextの付替 |
|---|---|
| 先頭 | LinkedList.headを2番目ノードにする |
| 末尾 | 末尾から2番目ノードのnextをNoneにする |
| 中間 | 削除対象ノードの一つ前のノードがもつnextに、削除対象ノードがもつnextの値をセットする |
ところで、先頭と末尾のときは既存のremove_head, remove_tailを呼び出したほうが早いのではないか？ remove_headに関してはその通り。だが、remove_tailを呼び出すと、末尾ノード検索処理が2回走ることになってしまう。なので、コードが重複してしまうが、仕方なく同じように実装する。
コード
先述の通り、中間にあるノードを削除するときは、それより一つ前のノードが必要になる。prevフィールドは未だ凍結中のため、nextフィールドだけでやる必要があるからだ。
まずは「一つ前のノードを取得する」内部メソッドを作る。
// 指定インデックスの一つ前のノードへの可変参照を返す。 // * インデックスは1以上の想定 // * インデックスが1でノードがひとつしかなければそれを返す fn search_from_pre_index_ptr(&mut self, index: u32) -> &mut Option<Box<Node<T>>> { fn node_of_index<T>(node: &mut Option<Box<Node<T>>>, index: u32, count: u32) -> &mut Option<Box<Node<T>>> { if let None = node { node } else { if index-1 == count { node } else { node_of_index(&mut node.as_mut().unwrap().next, index, count+1) } } } node_of_index(&mut self.head, index, 0) }
あとは中間ノードの前後にあるノードを紐付ければいい。
pub fn remove_from_index(&mut self, index: u32) { if 0 == index { self.remove_head(); } // 先頭なら else { let pre_index_ptr = self.search_from_pre_index_ptr(index); // インデックスの一つ前を取得する if pre_index_ptr.is_none() { return } let mut target = std::mem::replace(&mut pre_index_ptr.as_mut().unwrap().next, None); if target.is_none() { return } if target.as_ref().unwrap().next.is_some() { // 末尾でなく中間なら let target_next = std::mem::replace(&mut target.as_mut().unwrap().next, None); std::mem::replace(&mut pre_index_ptr.as_mut().unwrap().next, target_next); } } }
非常に苦労した。
テストコード
コメントにある通り、存在しないインデックスを指定したときはパニックさせずにスルーする仕様とした。
// remove_headはheadに要素がないとき、エラーにならず何もせずにスルーする。 // これと同じように、remove_from_indexは指定したインデックスにノードが存在しないとき、エラーにならず何もせずにスルーする。 #[test] fn LinkedList_remove_from_index_out_of_index_blank_0() { let mut list: LinkedList<i32> = LinkedList::new(); list.remove_from_index(0); // エラーにならずスルー assert_eq!(list.head, None); }
それぞれの状態でパニックしないことを確認。
#[test] fn LinkedList_remove_from_index_out_of_index_blank_1() { let mut list: LinkedList<i32> = LinkedList::new(); list.remove_from_index(1); // エラーにならずスルー assert_eq!(list.head, None); } #[test] fn LinkedList_remove_from_index_out_of_index_blank_2() { let mut list: LinkedList<i32> = LinkedList::new(); list.remove_from_index(2); // エラーにならずスルー assert_eq!(list.head, None); } #[test] fn LinkedList_remove_from_index_out_of_index_one_1() { let mut list: LinkedList<i32> = LinkedList::new(); list.push(0); list.remove_from_index(1); // エラーにならずスルー assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None, prev: None }))); } #[test] fn LinkedList_remove_from_index_out_of_index_two_2() { let mut list: LinkedList<i32> = LinkedList::new(); list.push(0); list.push(1); list.remove_from_index(2); // エラーにならずスルー assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: None, prev: None })) , prev: None }))); }
先頭から削除されることを確認。
#[test] fn LinkedList_remove_from_index_head() { let mut list: LinkedList<i32> = LinkedList::new(); list.push(0); list.push(1); list.push(2); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: Some(Box::new(Node { item: 2, next: None, prev: None })) , prev: None })) , prev: None }))); list.remove_from_index(0); assert_eq!(list.head, Some(Box::new(Node { item: 1, next: Some(Box::new(Node { item: 2, next: None, prev: None })) , prev: None }))); list.remove_from_index(0); assert_eq!(list.head, Some(Box::new(Node { item: 2, next: None, prev: None }))); list.remove_from_index(0); assert_eq!(list.head, None); }
末尾から削除されることを確認。
#[test] fn LinkedList_remove_from_index_tail() { let mut list: LinkedList<i32> = LinkedList::new(); list.push(0); list.push(1); list.push(2); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: Some(Box::new(Node { item: 2, next: None, prev: None })) , prev: None })) , prev: None }))); list.remove_from_index(2); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: None, prev: None })) , prev: None }))); list.remove_from_index(1); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None, prev: None }))); list.remove_from_index(0); assert_eq!(list.head, None); }
間にあるノードが削除されることを確認。これがキモ。
#[test] fn LinkedList_remove_from_index_middle() { let mut list: LinkedList<i32> = LinkedList::new(); list.push(0); list.push(1); list.push(2); list.push(3); list.push(4); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item: 3, next: Some(Box::new(Node { item: 4, next: None, prev: None })) , prev: None })) , prev: None })) , prev: None })) , prev: None }))); list.remove_from_index(1); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item: 3, next: Some(Box::new(Node { item: 4, next: None, prev: None })) , prev: None })) , prev: None })) , prev: None }))); list.remove_from_index(2); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item: 4, next: None, prev: None })) , prev: None })) , prev: None }))); }
対象環境
- Raspbierry pi 3 Model B+
- Raspbian stretch 9.0 2018-11-13
- bash 4.4.12(1)-release
- rustc 1.34.2 (6c2484dc3 2019-05-13)
- cargo 1.34.0 (6789d8a0a 2019-04-01)
$ uname -a Linux raspberrypi 4.19.42-v7+ #1219 SMP Tue May 14 21:20:58 BST 2019 armv7l GNU/Linux
