6.3 基本操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        Self {
            front: None,
            back: None,
            len: 0,
            _boo: PhantomData,
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

pub fn push_front(&mut self, elem: T) {
    // SAFETY: 这是链表，你还想怎样？
    unsafe {
        let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node {
            front: None,
            back: None,
            elem,
        })));
        if let Some(old) = self.front {
            // 把新 front 插到旧的前面
            (*old).front = Some(new);
            (*new).back = Some(old);
        } else {
            // 没有 front，说明是空链表，也要设置 back。
            // 还有一些完整性检查，以防我们搞砸。
            debug_assert!(self.back.is_none());
            debug_assert!(self.front.is_none());
            debug_assert!(self.len == 0);
            self.back = Some(new);
        }
        self.front = Some(new);
        self.len += 1;
    }
}

1
2
3
4
5

error[E0614]: type `NonNull<Node<T>>` cannot be dereferenced
  --> src\lib.rs:39:17
   |
39 |                 (*old).front = Some(new);
   |                 ^^^^^^

1
2

            (*old.as_ptr()).front = Some(new);
            (*new.as_ptr()).back = Some(old);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

   Compiling linked-list v0.0.3
warning: field is never read: `elem`
  --> src\lib.rs:16:5
   |
16 |     elem: T,
   |     ^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: `linked-list` (lib) generated 1 warning (1 duplicate)
warning: `linked-list` (lib test) generated 1 warning
    Finished test [unoptimized + debuginfo] target(s) in 0.33s

 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

pub fn pop_front(&mut self) -> Option<T> {
    unsafe {
        // 只有存在 front 节点时才需要操作。
        // 注意我们不再需要折腾 `take`，
        // 因为一切都是 Copy，搞砸了也没有析构函数会跑……对吧？:) 对吧？:)))
        self.front.map(|node| {
            // 让 Box 复活，以便移出值并 Drop 它
            // （Box 继续神奇地帮我们处理）。
            let boxed_node = Box::from_raw(node.as_ptr());
            let result = boxed_node.elem;

            // 让下一个节点成为新 front。
            self.front = boxed_node.back;
            if let Some(new) = self.front {
                // 清理它对已移除节点的引用
                (*new.as_ptr()).front = None;
            } else {
                // front 现在是 null，链表空了！
                debug_assert!(self.len == 1);
                self.back = None;
            }

            self.len -= 1;
            result
            // Box 在这里隐式释放，知道里面没有 T。
        })
    }
}

pub fn len(&self) -> usize {
    self.len
}

1
2

   Compiling linked-list v0.0.3
    Finished dev [unoptimized + debuginfo] target(s) in 0.37s

 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

#[cfg(test)]
mod test {
    use super::LinkedList;

    #[test]
    fn test_basic_front() {
        let mut list = LinkedList::new();

        // 试着搞坏空链表
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);

        // 试着搞坏单元素链表
        list.push_front(10);
        assert_eq!(list.len(), 1);
        assert_eq!(list.pop_front(), Some(10));
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);

        // 随便折腾
        list.push_front(10);
        assert_eq!(list.len(), 1);
        list.push_front(20);
        assert_eq!(list.len(), 2);
        list.push_front(30);
        assert_eq!(list.len(), 3);
        assert_eq!(list.pop_front(), Some(30));
        assert_eq!(list.len(), 2);
        list.push_front(40);
        assert_eq!(list.len(), 3);
        assert_eq!(list.pop_front(), Some(40));
        assert_eq!(list.len(), 2);
        assert_eq!(list.pop_front(), Some(20));
        assert_eq!(list.len(), 1);
        assert_eq!(list.pop_front(), Some(10));
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);
    }
}

1
2
3
4
5
6
7
8

   Compiling linked-list v0.0.3
    Finished test [unoptimized + debuginfo] target(s) in 0.40s
     Running unittests src\lib.rs

running 1 test
test test::test_basic_front ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s