Rust实现LinkedList时向空链表追加节点的指针异常问题

问题概述 #

我在Rust中手动实现链表时，有两个测试用例失败，错误均为调用Option::unwrap()时遇到None值。经排查，问题出在链表append方法的实现逻辑上，导致空链表添加节点时head与tail指向独立实例，后续追加节点时head的next字段未正确更新。

原实现代码 #

#![allow(dead_code)]

use std::cell::{RefCell, Ref, RefMut};
use std::rc::Rc;

type WrappedNode<T> = Rc<RefCell<Node<T>>>;

#[derive(Debug, PartialOrd, PartialEq, Clone)]
pub struct Node<T> where
  T: Clone 
  {
    next: Option<WrappedNode<T>>,
    data: T,
}

#[derive(Debug, PartialOrd, PartialEq)]
pub struct LinkedList<T> where
  T: Clone 
  {
    head: Option<WrappedNode<T>>,
    tail: Option<WrappedNode<T>>,
}

impl<T> Iterator for LinkedList<T> where
  T: Clone 
  {
type Item = WrappedNode<T>;
  
  fn next(&mut self) -> Option<Self::Item> {
    unimplemented!()
  }
}

impl<T> Node<T> where
  T: Clone
  {
  pub fn new(data: T) -> Self {
    Self {
      next: None,
      data,
    }
  }

  pub fn borrow_data(self: &Self) -> &T {
    &self.data
  }

  pub fn borrow_next(self: &Self) -> Option<Ref<Node<T>>> {
    match &self.next {
      Some(next_exists) => {
        Some(next_exists.borrow())
      },
      None => {
        None
      }
    }
  }

  pub fn borrow_mut_next(self: &Self) -> Option<RefMut<Node<T>>> {
    match &self.next {
      Some(next_exists) => {
        Some(next_exists.borrow_mut())
      },
      None => {
        None
      }
    }
  }

  pub fn set_next(self: &mut Self, next: Node<T>) {
    let next_node = Rc::new(RefCell::new(next));
    self.next = Some(next_node);
  }
}

impl<T> LinkedList<T> where
  T: Clone
  {
  pub fn new_empty() -> Self {
    Self {
      head: None,
      tail: None,
    }
  }

  pub fn new_with_node(first_node: Node<T>) -> Self {
    let mut new_ll = Self::new_empty();
    Self::append(&mut new_ll, first_node);
    new_ll
  }

  pub fn append(&mut self, node: Node<T>) {
    assert!(node.next.is_none()); // make sure its not joining two linkedlists
    
    match self.tail.take() {
      Some(old_tail) => {
        old_tail
          .borrow_mut()
          .set_next(node.clone());
        },

      None => {
        let mut node_clone = node.clone();
        node_clone.next = self.tail.clone();
        self.head = Some(Rc::new(RefCell::new(node_clone)));
      }
    }
    self.tail = Some(Rc::new(RefCell::new(node)));
  }
  
}

// CRUD -> create new, add to head tail, read head tail, update anywhere, delete anywhere, delete head tail

#[cfg(test)]
mod tests {
  use super:: {Node, LinkedList};
  use std::rc::Rc;
  use std::cell::RefCell;
  
  #[test]
  fn test_node_ref_data() {
    let node = Node::new(5);
    assert_eq!(node.borrow_data(), &5);
  }

  #[test]
  fn test_node_ref_next() {
    let node = Node::new(5);
  assert!(node.borrow_next().is_none());
  }

  #[test]
  fn test_node_set_next() {
    let mut node = Node::new(33);
    let next_node = Node::new(34);
    Node::set_next(&mut node,
                   next_node);
    assert_eq!(node
               .borrow_next()
               .unwrap()
               .borrow_data(), &34);
  }

  #[test]
  fn test_ll_new_empty() {
    #[derive(Debug, PartialEq, PartialOrd, Clone)]
    struct NTH;
    let new_ll = LinkedList::<NTH>::new_empty();
    assert_eq!(new_ll, LinkedList{head: None, tail: None})
  }

  #[test]
  fn test_ll_new_with_node() {
    let new_node = Node::new(45);
    let new_node_two = new_node.clone();
    let new_node_three = new_node.clone();
    let new_ll = LinkedList::new_with_node(new_node);
    let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));
    let new_node_three = Some(Rc::new(RefCell::new(new_node_three)));
    
    assert_eq!(new_ll, LinkedList{head: new_node_two, tail: new_node_three})
  }

  #[test]
  fn test_ll_new_with_node_head_borrow_next_is_tail() {
    let new_node = Node::new(45);
    let new_node_two = new_node.clone();
    let new_ll = LinkedList::new_with_node(new_node);
    let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));
    assert_eq!(new_ll
            .head
            .unwrap()
            .borrow()
            .borrow_next()
            .unwrap()
            .borrow_data(), new_node_two.unwrap().borrow().borrow_data());
  }

  #[test]
  fn test_ll_append_tail() {
    let new_node = Node::new(45);
    let new_node_two = new_node.clone();
    let mut new_ll = LinkedList::new_with_node(new_node);
    let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));

    let append_node = Node::new(77);
    LinkedList::append(&mut new_ll, append_node);
    assert_eq!(new_ll
              .tail
              .unwrap()
              .borrow()
              .borrow_data(), &77)
  }

  #[test]
  fn test_ll_append_first_borrow_next() {
    let new_node = Node::new(45);
    let new_node_two = new_node.clone();
    let mut new_ll = LinkedList::new_with_node(new_node);
    let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));

    let append_node = Node::new(77);
    LinkedList::append(&mut new_ll, append_node);
    assert_eq!(new_ll
              .head
              .unwrap()
              .borrow()
              .borrow_next()
              .unwrap()
              .borrow_data(), &77)
  }

// end of tests
}

测试失败信息 #

running 8 tests
test same_type_linked_list::tests::test_ll_new_empty ... ok
test same_type_linked_list::tests::test_ll_append_tail ... ok
test same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail ... FAILED
test same_type_linked_list::tests::test_ll_append_first_borrow_next ... FAILED
test same_type_linked_list::tests::test_ll_new_with_node ... ok
test same_type_linked_list::tests::test_node_ref_data ... ok
test same_type_linked_list::tests::test_node_set_next ... ok
test same_type_linked_list::tests::test_node_ref_next ... ok

failures:

---- same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail stdout ----
thread 'same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail' panicked at 'called `Option::unwrap()` on a `None` value', src/same_type_linked_list.rs:176:14

---- same_type_linked_list::tests::test_ll_append_first_borrow_next stdout ----
thread 'same_type_linked_list::tests::test_ll_append_first_borrow_next' panicked at 'called `Option::unwrap()` on a `None` value', src/same_type_linked_list.rs:210:16
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    same_type_linked_list::tests::test_ll_append_first_borrow_next
    same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail

问题分析 #

1. 空链表添加第一个节点时的错误：
   在append方法的None分支（处理空链表），代码克隆了输入的node，分别创建两个独立的Rc<RefCell<Node<T>>>实例赋值给head和tail。这导致head和tail指向完全不同的节点实例，而非同一个节点的共享引用。

2. 追加第二个节点时的错误：
   当追加第二个节点时，代码修改的是tail指向的节点的next字段，但head指向的是另一个独立节点，因此head的next字段始终为None，导致测试test_ll_append_first_borrow_next调用unwrap()时panic。

3. 测试逻辑错误：
   test_ll_new_with_node_head_borrow_next_is_tail测试本身逻辑有误——单个节点的链表中，节点的next字段应为None（没有后续节点），但测试期望head的next指向tail（而tail就是head自身），这违背了链表的基本结构。

修复方案 #

1. 修正append方法 #

重构append方法，避免克隆节点，而是将输入节点包装为单个Rc实例，同时共享给head和tail：

impl<T> LinkedList<T> where
  T: Clone
  {
  // ... 其他方法保持不变 ...

  pub fn append(&mut self, node: Node<T>) {
    assert!(node.next.is_none());
    
    let wrapped_node = Rc::new(RefCell::new(node));
    match self.tail.take() {
        Some(old_tail) => {
            // 直接修改旧tail的next为新节点的共享引用
            old_tail.borrow_mut().next = Some(wrapped_node.clone());
        },
        None => {
            // 空链表时，head和tail指向同一个节点
            self.head = Some(wrapped_node.clone());
        }
    }
    self.tail = Some(wrapped_node);
  }
  
}

2. 移除或修改set_next方法 #

原set_next方法会创建新的Rc实例，不符合链表节点共享的需求，建议直接移除该方法，改为直接操作next字段（如上述修复后的append方法所示）。

3. 修正错误的测试用例 #

修改test_ll_new_with_node_head_borrow_next_is_tail测试，使其符合单个节点链表的结构：

#[test]
fn test_ll_new_with_node_head_borrow_next_is_none() {
    let new_node = Node::new(45);
    let new_ll = LinkedList::new_with_node(new_node);
    // 单个节点的next应为None
    assert!(new_ll
            .head
            .unwrap()
            .borrow()
            .borrow_next()
            .is_none());
    // 验证head和tail指向同一个节点
    assert!(Rc::ptr_eq(new_ll.head.as_ref().unwrap(), new_ll.tail.as_ref().unwrap()));
}

修复后效果 #

修正后，所有测试用例均可通过：

• 空链表添加第一个节点时，head和tail指向同一个Rc实例
• 追加后续节点时，旧tail的next字段正确指向新节点的共享引用
• 测试逻辑符合链表的实际结构

内容的提问来源于stack exchange，提问作者Jim