First, I am aware that LinkedLists are not the solution and that they are inherently difficult to implement / use in Rust, and I've also read most of this. This is solely for practicing interview-esque programming challenges, this one being to delete duplicates from a linked list.
Of course it would be possible to go through an immutable pass and record index locations to delete afterwards, but that defeats the point of it being a linked list exercise. Instead, I'm using the nightly experimental "cursor" API. With that out of the way, as in the title, is it possible to iterate across a LinkedList with a cursor in a single pass, and, depending on the value of cursor.current(), either cursor.remove_current() or cursor.move_next()?
The problem for me is that these operations, i.e.
Look at the current value (immutable borrow)
Depending on (1), either cursor.remove_current() or cursor.move_next() (mutable borrow)
of course causes the borrow checker to barf. I've also tried to insert {} blocks and explicitly drop(current) once I'm done using it, but still the borrow checker disallows the later mutable borrows. For reference, some code is attached.
use std::collections::HashSet;
use std::collections::LinkedList;
use std::hash::Hash;
pub fn remove_dups<T: Eq + Hash>(list: &mut LinkedList<T>) {
let mut seen = HashSet::new();
let mut cursor = list.cursor_front_mut();
while let Some(current) = cursor.as_cursor().current() {
if seen.contains(current) {
cursor.remove_current();
} else {
seen.insert(current);
cursor.move_next();
}
}
}
The compiler can't let you access the CursorMut while references to list elements are still alive, because you could navigate the CursorMut back to those elements and remove them. Then the HashSet would contain dangling references.
Of course, your function does not actually do this. Because it only moves forward, it will never revisit one of the elements that is referenced by the Hashset. However, the compiler can only see the types of the cursor methods, not their semantics, so it has no way of knowing that this particular usage is safe.
To allow this in safe Rust would require an API that can only move through the list in one direction. The experimental LinkedList::drain_filter method provides such an API. (EDIT: Unfortunately, I think it still won't work for this use case because it only allows each item to be borrowed temporarily, so you can't store a reference to it outside the closure.)
Ah, thank you for the tip about the HashSet. While I understand why the code posted above doesn't work, I was confused as to why my code with drop(current) didn't work; I see now, there would be dangling references in the HashSet.
Also, your answer demonstrates something that wasn't clear to me. At first, I thought that my post implied that I couldn't traverse a linked list and delete nodes depending on their values, which seemed so limiting. But this is not the case; I just can't delete nodes depending on other nodes' values.
This also let me realize that one solution, although slightly more limiting, is to restrict to types which can be cloned or copied, so as to compare previous nodes by value rather than by reference. So, the below code compiles and works as expected:
pub fn remove_dups<T: Eq + Hash + Copy>(list: &mut LinkedList<T>) {
let mut seen = HashSet::new();
let mut cursor = list.cursor_front_mut();
while let Some(current) = cursor.current() {
if seen.contains(current) {
cursor.remove_current();
} else {
seen.insert(*current);
cursor.move_next();
}
}
}