I have to delete the k-th element from the end of a linked-list, say:
k=2
before:
1->2->3->4
after:
1->2->4
I use two pointers to solve this problem:
A fast pointer goes first, it stops at the k-th node from the head. And then, the slow pointer goes together with the fast pointer until the fast pointer approaches the tail of the linked-list. Because the fast pointer is k-th ahead of the slower pointer, which also means the slow pointer is pointing the k-th node from the end, and this is what I want to delete.
But when using two pointers, the linked-list can only be borrowed immutable, and when I find the node to delete, it's immutable borrowed, and I don't know how to delete it. Here's the code:
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
impl Solution {
pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
if head.is_none() {
return None;
}
let mut fast = head.as_ref();
// fast pointer go first
for _ in 0..n {
if let Some(node) = fast.take() {
fast = node.next.as_ref();
} else {
return head.unwrap().next;
}
}
let mut slow = &head;
// slow pointer goes together with the fast pointer
while let Some(fast_node) = fast.take() {
if fast_node.next.is_some() {
fast = fast_node.next.as_ref();
slow = &slow.unwrap().next;
} else {
// here, fast approaches the tail, and the node the slow pointer pointing to should be deleted, but how to do it?
break;
}
}
}
}
std::collections::VecDeque is an example. Actually, for a singly linked list, just using Vec is probably still faster than pointer-following. Benchmark it if you don't believe me.
Even if your intended linked-list operations are O(1), their impact on cache hit rate due to non-locality of consecutive elements will be devastating. Most Rust compilers target hardware that employs a multi-level memory hierarchy. On those systems you will suffer a major performance hit from long, varying-duration cache-miss delays on virtually every successive reference as you walk the list.
I would bet that if you kept all your elements in an array and just moved elements down to overwrite/delete the k-th element it would be easier and faster than a linked list.
I know about cache misses, but I'm thinking of use cases were 90% of operations are additions or deletions. Even in that case doubly linked list will have worse performance than any other alternative?
What about the memory usage if doubly linked list can have between 100 to 1,000,000 items?
In these use cases, doubly linked list is better choice or is there another better alternative?
How moving items on vec or array will be faster if items list can be > 100 items?
Perhaps the point you are missing is the existence of cache memory in modern computers.
Today we have giga bytes of memory on dynamic RAM chips on our computers mother boards.
We also have many kilo/mega byes of memory actually inside the processor chips.
That memory inside the processor chips, cache memory, is hundreds even thousands of times faster for the processor to access than if it has to get the data from from our big RAM chips outside.
Elements of a linked list are individually allocated in memory and may be spread around a lot. Elements of a vector are allocated in one go and live next to each other.
So, when updating a vector everything can be in that fast cache RAM at the same time. Where as elements of a linked list, being spread all over memory, are not.
Also a linked list of small items is much bigger than it need be tanks to all those pointers in each element. Worse for a doubly linked list. Being bigger it has even less chance of being in that fast cache memory of our processors.
I think you will have to try hard to find a case where a linked list will beat an array when deleting/inserting an element in the middle.
You should convince yourself of this cache phenomena with a simpler example:
Create a large two dimensional array of integers. Some number of megabytes. Now iterate over all the elements of that array and do some simple operation on them.
You will find that if you traverse the array row first then column that can happen a huge amount faster than column first then row. (Or is that the other way around).
Anyway, it turns out that the impact of that cache memory in modern processors can totally dominate over whatever O() for whatever algorithm they teach in school.
You cannot retain a mutable reference of slow node because fast node is reachable from this reference and it is a violation of the Rust guarantee to have such two references with at least one is mutable.
All codes below uses
type List = Option<Box<ListNode>>;
and the functions are of type fn(&mut List, usize) instead of the OP's definition to get a simpler code. Also the codes panic on the error condition n == 0 || len < n for simplicity.
A solution is using a raw pointer to detour the borrow checker. Using unsafe and is not generally recommended. I don't ensure the code below is correct.
fn using_raw_ptr(head: &mut List, n: usize) {
unsafe {
let mut fast: *const List = head;
for _ in 0..n {
fast = &(*fast).as_ref().expect("remove index too large").next;
}
let mut slow: *mut List = head;
while let Some(next) = (*fast).as_ref() {
fast = &next.next;
slow = &mut (*slow).as_mut().unwrap().next;
}
*slow = (*slow).take().expect("remove index cannot be zero").next;
}
}
An alternative solution is to give up the pointer chasing algorithm and using a counter. It has the same "scan count" (two scans each node in the worst case) as the algorithm above.
fn list_len(mut head: &List) -> usize {
let mut len = 0;
while let Some(node) = head.as_ref() {
head = &node.next;
len += 1;
}
len
}
fn using_counter(mut head: &mut List, n: usize) {
let index = list_len(head)
.checked_sub(n)
.expect("remove index too large");
for _ in 0..index {
head = &mut head.as_mut().unwrap().next;
}
*head = head.take().expect("remove index cannot be zero").next;
}
By the way, you defined the function as a method of Solution but in Rust, you don't have to define every function in classes (types) unlike Java, and defining the function as a top-level function is more idiomatic.
So, in the case of u8 roughly 2x extra memory usage. For u32, roughly 0.5x extra memory usage. As for 1,000,000, lazy to do that, the number is just too huge, can s/100/1000000/.
Memory wastage is one thing, cache missing is another.
Yes, for those it won't be significant but why the extra pointers and indirection? IIRC vector does allocation lesser and more efficiently (less calls), that is already a winning point.
I am interested to see any valid use case of a linked list that out-performs vector.
Perhaps I'm mistaken but aren't bigger thing generally allocated on the heap. Like the content of String.
At which point one is back to having only a pointer or two in the list elements that point to the content and then another pointer or two to make that a list element. Back to lots of list overhead.
Benefit is fast insertion or removal of items O(1). If item size is small then vector is better. But if list length can be in millions then d-linked should out perform vector imo. I don't know where and at what size of item d-linked list will start to outperform vector, but in theory it should as the list size grows.
Yes items will be heap allocated. But if item size is large then having 2 pointers for faster operations should be insignificant imo.
If the size of an object is a concern, then you could store a Vec<Box<T>>, which is more cache friendly than a linked list, but this will still suffer from cache misses to access the data, like a linked list. It's better because accessing the next element doesn't depend on the previous element, which makes it easier for processors to parallelize.
As often noted, that O(1) is only true and perhaps of benefit if you already have a pointer to the element. The head, the tail or some element you are working on in the middle. Otherwise you have to scan the list, O(n), to get to the element, which involves cache unfriendly jumping around memory.
Perhaps a linked list wins at some size. I guess someone will have to step up to the plate and make the comparison so that we finally put this debate to rest.
I'm putting my money on a hash table at that point
the cache arguments against linked lists seem to assume seperate allocations for each node. But what if each node was an entry in a vec and the "pointers" were indexes into the vec. Then insertions and deletions in the middle of the list could be done in O(1) (assuming you already have a reference to the node) but the nodes will all be close together.
By pre-allocating a vec and using that as memory space for your elements, but using array indices for access rather than raw pointers, you are essentially creating your own memory allocator. You will have to keep track of which elements are occupied and which can be used for new elements.
This will all depend on your use case but consider that elements are added and removed from your linked_list_in_array at random. Over time your links will become a tangled chain of interconnections running up and down your array randomly.
Now when you do your scan you will have to fetch elements from all kinds of random elements of the array to find the position you want. Which will be scattered all over memory. For a large array this is as cache unfriendly as what we started with. Once again the insertion/deletion is O(1). Finding the place to do it is O(n) and you have all that cache miss overhead.
