Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Are there any differences between these two drop implementations for a singly-linked list

Tags:

rust

I'm working through Learning Rust with Entirely Too Many Linked Lists and had a question about the drop implementation for the initial linked list from that book. The linked list is composed of a stack allocated link, which is either empty or points to a heap allocated Node with some associated data.

struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    data: i32,
    next: Link,
}

The implementation of the drop trait given in the book uses std::mem::replace to take ownership of the nodes in the list.

// Copied from the book, omitting comments
impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
        }
    }
}

I'm confused why the book is using mem::replace to take ownership of the next pointer of the node. It seems like we already have owndership of boxed_node from the while let line and we can just set cur_link to node.next instead of using mem::replace.

I wrote this alternative implementation which compiles just fine. I'm wondering if there is any difference between the two drop methods.

impl Drop for List {
    fn drop(&mut self) {
        let mut link = mem::replace(&mut self.head, Link::Empty);
        while let Link::More(node) = link {
            link = node.next;
        }
    }
}
like image 1000
Hrishi Dharam Avatar asked Nov 08 '20 19:11

Hrishi Dharam


People also ask

What are the differences between SLL and DLL?

DLL nodes contains 3 fields -data field, a previous link field and a next link field. In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only. In DLL, the traversal can be done using the previous node link or the next node link.

What is two way linked list how it differ from singly linked list?

Singly linked list allows traversal elements only in one way. Doubly linked list allows element two way traversal. On other hand doubly linked list can be used to implement stacks as well as heaps and binary trees.

Is implementation of doubly linked list is easier than the singly linked list?

Every insertion and deletion requires manipulation of two pointers, hence it takes a bit longer time. Implementing doubly linked list involves setting both left and right pointers to correct nodes and takes more time than singly linked list.

Why is a two way linked list more efficient than a singly linked list?

Doubly Linked list is more effective than the Singly linked list when the location of the element to be deleted is given. Because it is required to operate on "4" pointers only & "2" when the element to be deleted is at the first node or at the last node.


Video Answer


1 Answers

Yes, you are absolutely right. The whole point of implementing Drop in that tutorial is to avoid a recursive call, and your implementation achieves the same thing using less code (and with less assembly at the end).

Having said that, the implementation in the tutorial is a lot more explicit, and it could be argued that it is easier to see what is going on. The mem::replace ensures that the Link is replaced with an Empty, making it clear that all of the boxes are dropped too. This might have been a conscious decision by the tutorial authors, or it could have been an oversight.

The bonus section might also give a clue as to what the author was thinking. Their idea of simplifying the Drop implementation was to add a method which is useful for simplifying other methods too, and therefore would still need to maintain the integrity of the structure. The fact that this isn't necessary in a Drop implementation may have passed them by while looking at the bigger picture, or else they may have specifically wanted that implementation so that the bonus section makes sense.

Your version is probably more efficient, but might take a second glance to understand what it is really doing. I'd still go with yours though, since it is shorter and is doing less work.

like image 84
Peter Hall Avatar answered Oct 19 '22 03:10

Peter Hall