求教链表删除结点

< 返回我的博客

Deen 发表于 2019-01-18 11:48

Tags：linedlist

实现一个方法fn remove(head: Option<Box<LinkedList>>, val: i32) -> Option<Box<LinkedList>> 即，删除链表中值为val的结点，返回删除后的链表。

我现在有两个问题：

此函数签名中，head是获得了ownership的，但是似乎不是mutable的，这个怎么解呢？如果一个对象在声明时没有带mut，是不是之后都不能改了（refcell除外）。
怎样删除链表中间的结点呢？我看了learn rust with too many linkedlist上，知道怎么删除表头，但是如果要删除表中的元素，需要通过ref遍历到该结点，此时链表处于被引用状态是不可变的，如何实现删除呢？我发现标准库的链表也没有提供删除中间结点的API？有没有哪位大佬能帮忙解惑一下，谢谢

评论区

写评论

Military-axe 2021-06-25 12:29

我用的是类似二叉树的定义结构体

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

type LinkNode<K> = Option<Rc<RefCell<Node<K>>>>;

#[derive(Debug)]
struct Node<K> {
    data: K,
    next: LinkNode<K>,
}

然后删除的写法是

impl Node{
pub fn delete(head: &LinkNode<K>, position: usize){
        let mut count = 0;
        if let Some(mut root) = head.clone() {
            loop {
                if count != position {
                    let tmp = root.borrow().next.clone();
                    if let Some(next) = tmp {
                        count += 1;
                        root = next.clone();
                    } else {
                       panic!("LinkNode no too long");
                    }
                } else {
                    let tmp = root.borrow().next.clone();
                    if let Some(next) = tmp{
                        if let Some(nextt) = next.borrow().next.clone(){
                            root.borrow_mut().next = Some(nextt.clone());
                        }else{
                            root.borrow_mut().next = None;
                        }
                    }
                    break;
                }
            }
        }
    }
}

因为box不可以两个指针指向同一个，我又不想用递归的写法，于是就这么写，但是我也不知道怎么删除节点把那块内存删除掉

xcaptain 2019-04-02 10:30

一般标准的链表都只提供从表头删除功能，如果想删除一个节点可以参考官方的实现https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/linked_list.rs#L217 这个方法使用了unsafe关键字，但是很容易理解

在官方的链表实现中还有一个drain_filter的方法 https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/linked_list.rs#L767 看起来又更复杂了

可以试试能不能把这个unlink_node的方法改造成safe的

kaigedong 2019-03-25 13:42

前几天的Rust日报里，推送了链表的实现，不知道你还用不用得到。 https://github.com/rust-unofficial/too-many-lists

1 共 3 条评论, 1 页