how to modify a linked list by using pointers only
I have a linked list of Option<Box<ListNode>> type, a node of this list contains two properties: value (i32) and next (Option<Box<ListNode>>). I've created a vector of pointers (Vec<&Box<ListNode>>) with the purpose of serving to modify the original list as showed in the following picture:
Note: the resulting list should be: L: 1 -> 2 -> n-1 -> n
This is my code, it needs some fixes but at the moment I need to know if I can modify my linked list by using pointers.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
impl ListNode {
#[inline]
pub fn new(val: i32) -> Self {
ListNode {
next: None,
val
}
}
}
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
head.as_ref()?;
type NodeRef<'a> = &'a Box<ListNode>;
type OptNodeRef<'a> = Option<NodeRef<'a>>;
const MAX_NODES: u16 = 300;
// let mut head = head;
let mut current: OptNodeRef = head.as_ref();
let mut node_ref: OptNodeRef = None;
let mut vec_ref: Vec<NodeRef> = Vec::with_capacity(MAX_NODES as usize);
let mut counter: u16 = 0;
while let Some(node) = current {
if node_ref.is_none() || node_ref.unwrap().val != node.val {
node_ref = Some(node);
if counter > 0 {
vec_ref.push(node);
}
counter = 0;
} else {
counter += 1;
}
current = node.next.as_ref();
}
if counter > 0 {
vec_ref.push(node_ref.unwrap());
}
// vec_ref.into_iter().map(|t| t.val).for_each(|e| println!("{:?}", e));
// my problem starts from here...
for i in 0..vec_ref.len() - 1 {
vec_ref[i].next = Some(*vec_ref[i + 1]);
}
if let Some(last_node) = vec_ref.last() {
last_node.next = None;
}
if let Some(first_node) = vec_ref.first() {
Some(**first_node)
} else {
None
}
}
how to get it? I've tried some things but I always get an error related to borrow, move, mismatch errors. It seems simple to modify "next" property but I'm out of ideas.
Solution
Here is my thought, first, basically avoid using linked list in Rust, rust is just not a good language for using linked list because the ownershipe model.
second, if you want a link list I think you should tried to avoid messing with reference too much. Pointer is already hard to think about, let alone pointer comply with ownership rule.
think about who own the piece of data.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
impl ListNode {
#[inline]
pub fn new(val: i32) -> Self {
ListNode { next: None, val }
}
/// Functions I added for testing
///
/// Push an element to the end of the list
pub fn push(&mut self, val: i32) {
let mut current: &mut ListNode = self;
while current.next.is_some() {
current = current.next.as_mut().unwrap();
}
current.next = Some(Box::new(ListNode { val, next: None }));
}
/// Print Out the list
pub fn print(&self) {
print!("[{:>3?}]", self.val);
let mut current: &ListNode = self;
while current.next.is_some() {
current = current.next.as_ref().unwrap();
print!(" -> [{:>3?}]", current.val);
}
println!("");
}
}
/// I refactored the whole function
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
// The head of the list, if there aren't a list, return None
let mut head: Box<ListNode> = head?;
let mut current: Option<Box<ListNode>> = head.next.take();
let mut tail: &mut Box<ListNode> = &mut head;
// we TAKE the second element as the current node
//
// you can think of it as
//
// |- tail
// v
// head : () -> [first val]
//
// current: () -> [second val] -> [thrid val] -> ...
//
// Then we keep dequeuing the current
// when current is None, we know the list ended
while let Some(mut c) = current {
//
// | tail
// v
// head : () -> [1] -> [2] -> ... -> [4]
// c : () -> [5] -> [6]-> ...
//
// TAKE out the next node as the next current
current = c.next.take();
//
// | tail
// v
// head : () -> [1] -> [2] -> ... -> [4]
// c : () -> [5]
// current : () -> [6] -> [7]-> ...
//
// if the c.val is not equal to the last list, we push it to the end of the list
if c.val != tail.val {
tail.next = Some(c);
tail = tail.next.as_mut().unwrap();
//
// | tail
// v
// head : () -> [1] -> [2] -> ... -> [4] -> [5]
}
}
Some(head)
}
fn main() {
let mut list: ListNode = ListNode::new(1);
list.push(2);
list.push(2);
list.push(3);
list.push(4);
list.print();
let new_list: Box<ListNode> = delete_duplicates(Some(Box::new(list))).unwrap();
new_list.print();
}
output
[ 1] -> [ 2] -> [ 2] -> [ 3] -> [ 4]
[ 1] -> [ 2] -> [ 3] -> [ 4]
that way, head own the whole list, and tail handle the mutation of the list. which comply with the ownership rule, one owner, and only one mutable reference.
Performance
performance is way faster if the function take reference instead of the the whole list like Andrea Corbellini's solution
use std::io::Write;
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
impl ListNode {
#[inline]
pub fn new(val: i32) -> Self {
ListNode { next: None, val }
}
/// Functions I added for testing
///
/// Push an element to the end of the list
pub fn push(&mut self, val: i32) {
let mut current: &mut ListNode = self;
while current.next.is_some() {
current = current.next.as_mut().unwrap();
}
current.next = Some(Box::new(ListNode { val, next: None }));
}
/// Print Out the list
pub fn print(&self) {
print!("[{:>3?}]", self.val);
let mut current: &ListNode = self;
while current.next.is_some() {
current = current.next.as_ref().unwrap();
print!(" -> [{:>3?}]", current.val);
}
println!("");
}
}
/// I refactored the whole function
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
// The head of the list, if there aren't a list, return None
let mut head: Box<ListNode> = head?;
let mut current: Option<Box<ListNode>> = head.next.take();
let mut tail: &mut Box<ListNode> = &mut head;
// we TAKE the second element as the current node
//
// you can think of it as
//
// |- tail
// v
// head : () -> [first val]
//
// current: () -> [second val] -> [thrid val] -> ...
//
// Then we keep dequeuing the current
// when current is None, we know the list ended
while let Some(mut c) = current {
//
// | tail
// v
// head : () -> [1] -> [2] -> ... -> [4]
// c : () -> [5] -> [6]-> ...
//
// TAKE out the next node as the next current
current = c.next.take();
//
// | tail
// v
// head : () -> [1] -> [2] -> ... -> [4]
// c : () -> [5]
// current : () -> [6] -> [7]-> ...
//
// if the c.val is not equal to the last list, we push it to the end of the list
if c.val != tail.val {
tail.next = Some(c);
tail = tail.next.as_mut().unwrap();
//
// | tail
// v
// head : () -> [1] -> [2] -> ... -> [4] -> [5]
}
}
Some(head)
}
pub fn delete_duplicates_2(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
// take ownership of the head, and we will manipulate this directly.
let mut current = head;
// Mutable reference to 'current' node. We use 'as_mut' and 'and_then' to traverse and modify the list in place
let mut current_ref = current.as_mut();
while let Some(curr_node) = current_ref {
// check if the next node is a duplicate
while curr_node
.next
.as_ref()
.map_or(false, |next_node| next_node.val == curr_node.val)
{
//skip the duplicate
curr_node.next = curr_node.next.as_mut().unwrap().next.take();
}
// Move to the next node
current_ref = curr_node.next.as_mut();
}
current
}
pub fn delete_duplicates_3(head: &mut Option<Box<ListNode>>) {
// Make sure that `node` is `Option<&mut Box<ListNode>>`, to
// avoid taking ownership of nodes after the head (which would
// not be allowed by Rust)
let mut node = head.as_mut();
while let Some(this) = node {
// Loop through every node that shares the same value as `this`
loop {
if let Some(ref mut next) = this.next {
if this.val == next.val {
// `this` and `next` have the same value.
// Connect `this` to `next.next`, so that the
// list changes from:
//
// ... -> this -> next -> next.next -> ...
//
// to:
//
// ... -> this -> next.next -> ...
//
// The use of `take()` ensures that `next.next`
// is replaced with `None` (this avoids taking
// multiple ownerships).
this.next = next.next.take();
continue;
}
}
// Either there's no next node, or the next node has a
// different value than `this`
break;
}
node = this.next.as_mut();
}
}
fn delete_duplicates_4(head: &mut Option<Box<ListNode>>) {
if head.is_none() {
return;
}
let mut head = head.as_mut().unwrap();
while let Some(ref n) = head.next {
if head.val == n.val {
head.next = head.next.take().unwrap().next;
} else {
head = head.next.as_mut().unwrap();
}
}
}
fn make_list(len: usize) -> ListNode {
let mut a = 1;
let mut b = 1;
let mut list = ListNode::new(a);
for _ in 0..len {
let t = b;
b = (a + b) % 10;
a = t;
list.push(a);
}
list
}
fn bench(len: usize) {
let list = make_list(len);
let N = 2048;
println!("Bench Testing n = {}", len);
{
print!(" running delete_duplicates . . . ");
std::io::stdout().flush().unwrap();
let mut dt = 0;
for _ in 0..N {
let list = Some(Box::new(list.clone()));
let t0 = std::time::Instant::now();
let _ = delete_duplicates(list).unwrap();
dt += t0.elapsed().as_micros();
}
println!("{:>8}us", (dt as f64) / (N as f64));
}
{
print!(" running delete_duplicates_2 . . . ");
std::io::stdout().flush().unwrap();
let mut dt = 0;
for _ in 0..N {
let list = Some(Box::new(list.clone()));
let t0 = std::time::Instant::now();
let _ = delete_duplicates_2(list).unwrap();
dt += t0.elapsed().as_micros();
}
println!("{:>8}us", (dt as f64) / (N as f64));
}
{
print!(" running delete_duplicates_3 . . . ");
std::io::stdout().flush().unwrap();
let mut dt = 0;
for _ in 0..N {
let mut list = Some(Box::new(list.clone()));
let t0 = std::time::Instant::now();
let _ = delete_duplicates_3(&mut list);
dt += t0.elapsed().as_micros();
}
println!("{:>8}us", (dt as f64) / (N as f64));
}
{
print!(" running delete_duplicates_3 . . . ");
std::io::stdout().flush().unwrap();
let mut dt = 0;
for _ in 0..N {
let mut list = Some(Box::new(list.clone()));
let t0 = std::time::Instant::now();
let _ = delete_duplicates_4(&mut list);
dt += t0.elapsed().as_micros();
}
println!("{:>8}us", (dt as f64) / (N as f64));
}
}
fn main() {
for i in 5..=11 {
bench(1 << i);
}
}
Output
Bench Testing n = 32
running delete_duplicates . . . 2.052734375us
running delete_duplicates_2 . . . 2.16943359375us
running delete_duplicates_3 . . . 0.0556640625us
running delete_duplicates_4 . . . 0.1826171875us
Bench Testing n = 64
running delete_duplicates . . . 4.1171875us
running delete_duplicates_2 . . . 5.03515625us
running delete_duplicates_3 . . . 0.33154296875us
running delete_duplicates_4 . . . 0.06396484375us
Bench Testing n = 128
running delete_duplicates . . . 8.5419921875us
running delete_duplicates_2 . . . 8.87158203125us
running delete_duplicates_3 . . . 1.1669921875us
running delete_duplicates_4 . . . 1.193359375us
Bench Testing n = 256
running delete_duplicates . . . 18.2841796875us
running delete_duplicates_2 . . . 20.169921875us
running delete_duplicates_3 . . . 2.74169921875us
running delete_duplicates_4 . . . 2.35791015625us
Bench Testing n = 512
running delete_duplicates . . . 37.2880859375us
running delete_duplicates_2 . . . 36.0595703125us
running delete_duplicates_3 . . . 5.30224609375us
running delete_duplicates_4 . . . 5.31103515625us
Bench Testing n = 1024
running delete_duplicates . . . 66.796875us
running delete_duplicates_2 . . . 69.91552734375us
running delete_duplicates_3 . . . 9.84814453125us
running delete_duplicates_4 . . . 10.646484375us
Bench Testing n = 2048
running delete_duplicates . . . 133.638671875us
running delete_duplicates_2 . . . 143.2666015625us
running delete_duplicates_3 . . . 20.03955078125us
running delete_duplicates_4 . . . 20.87939453125us
- What is a smart pointer and when should I use one?
- What is int** returnColumnSizes in leetcode problem 46 (language: c)
- Range references instead values
- Simple Cache Implementation in C
- In Delphi/Free Pascal: is ^ an operator or does it simply denote a pointer type?
- Understanding Opaque Pointers
- What is a pointer to class data member "::*" and what is its use?
- What is the correct solution to work with bitmaps in terms of pointer arithmetic and conversion?
- Comparing counters and pointers in string loops in C
- What exactly is meant by "de-referencing a NULL pointer"?
- Using a string in system() (maybe system_() )
- Usefulness of void pointer in C and C++
- How can I cast a char to an unsigned int?
- Transfer the ownership of a already-defined std::unique_ptr to the member of a class object
- Reversing a string in C
- Getting a buffer from a pointer
- How can I restrict array parameters in C (without making them pointers)?
- esp32 c++ pointer to object is lost?
- how to assign array of struct to class variable without memcpy
- error C2064: term does not evaluate to a function taking 0 arguments
- Delete a node in a linked list using only 1 local pointer
- Member of a structure gets assigned a new address after freeing the structure
- Is there a way to determine if the representation of a pointer is 'linear' in C?
- What happens with the Frame Pointer in the Stack, if the Stack Pointer enters a second, nested function?
- What is the nullptr keyword, and why is it better than NULL?
- What does a pointer to an array represent?
- Defined a Set function to copy a variable-sized 2D square matrix but getting garbage
- gsl::not_null<T*> vs. std::reference_wrapper<T> vs. T&
- C++11: Does a move operation change the address?
- Assign a value by ref to a class member by ref