Double Linked List with Box and without Box Difference

1

Hello, im currently trying to write a double linked list algorithm in rust and hit a roadblock, which is the difference of using Box::into_raw() and straight up use raw pointer when creating a node.

this is my code:

use std::ptr;
#[derive(Debug)]
struct Node{
    prev:*mut Node,
    val:i32,
    next:*mut Node,
}

impl Node{
    fn new(val:i32)-> Self{
        Self{
            prev:ptr::null_mut(),
            val:val,
            next:ptr::null_mut(),
        }
    }
}

#[derive(Debug)]
struct DoubleLinkedList {
    head:*mut Node,
    tail:*mut Node,
    length:i32,
}

impl DoubleLinkedList {

    fn new() -> Self {
        Self{
            head:ptr::null_mut(),
            tail:ptr::null_mut(),
            length:0,
        }
    }
    
    fn add_at_head(&mut self, val: i32) {
        let mut newnode:*mut Node=&mut  Node::new(val);
        //let mut newnode:*mut Node=Box::into_raw(Box::new(Node::new(val)));
        unsafe{
            if self.length==0{
                self.head=newnode;
                self.tail=newnode;
            }else{
                (*self.head).prev=newnode;
                (*newnode).next=self.head;
                self.head=newnode;
            }
            println!("{:?}",(*self.head));
            
        }
        self.length+=1;
    } 
}
    
let mut mylist:DoubleLinkedList=DoubleLinkedList::new();
mylist.add_at_head(1);
mylist.add_at_head(2);
unsafe{
 
 println!("{:?}",(*mylist.head));
    
}

result with normal raw pointer:

Node { prev: 0x0, val: 1, next: 0x0 } //printing inside function add_to_head;
Node { prev: 0x7ffc006b7450, val: 2, next: 0x7ffc006b7450 } //printing inside function add_to_head;
Node { prev: 0x7ffbffeb8000, val: 7042288, next: 0x714a95a796e0 } //printing after insert

result with Box pointer:

Node { prev: 0x0, val: 1, next: 0x0 } //printing inside function add_to_head;
Node { prev: 0x0, val: 2, next: 0x616dbfd9bb10 } //printing inside function add_to_head;
Node { prev: 0x0, val: 2, next: 0x616dbfd9bb10 }  //printing after insert

my question is :

1.when using normal raw pointer why is prev got set with a raw pointer? i dont even touch it. and in the box pointer its work as expected. is it a memory corruption or something?

  1. when accesing next inside the function why the code return the same node? for example when i access next for node with value 2 it should return "Node { prev: 0x0, val: 1, next: 0x0 }" instead it return "{ prev: 0x7ffc006b7450, val: 2, next: 0x7ffc006b7450 }"

3.after inserting, why is the whole pointer value changes? self.head should have the head of Node { prev: 0x7ffc006b7450, val: 2, next: 0x7ffc006b7450 } instead it become Node { prev: 0x7ffbffeb8000, val: 7042288, next: 0x714a95a796e0 }.make 0 sense

4.why box pointer work and normal raw pointer doesnt

i couldnt find anything regarding this problem, can anyone help me explain what happening here?

thank you

2

This is creating a new Node on the stack, and then storing its address inside newnode. When add_at_head returns, everything in its stack frame is cleaned up which means that your pointer is now dangling.

When you use Box::into_raw(Box::new(…)), the new() call allocates space on the heap for the value and into_raw prevents Box’s destructor from running, which would ordinarily free that allocation.

1 Like
3

thanks for the explanation. i didnt know that raw pointer can be stored in the stack. can you give me a reference to a docs that state raw pointer can be stored in the stack? or is it just a programming thing?

4

Well, raw pointers don't really store anything; they just refer to some place in memory that's managed another way. In your examples, that's either a local variable (via let ...) or the heap allocator (via Box).

The best explanation of this stuff that I know of is: Introduction - Learning Rust With Entirely Too Many Linked Lists

2 Likes
5

Thanks for the reference, really helpful, but i want to ask about performance, which one is faster safe(Rc,Refcell and Weak pointer method) or unsafe(raw pointer method)?.

6

I'd say, if you are doing something with linking lists, you are either not worried about performance at all (in which case it's definitely better to be safe) or are squeezing every bit of it (in which case you will be profiling extensively and probably reading assembly output).

3 Likes
7

The safe methods do require runtime checks, so they’re slower in theory.

In practice, though, you’ll probably get the same performance in most circumstances— Traversing a linked list involves lots of random memory access, which will result in delays from cache misses and otherwise prevent some low-level processor optimizations from happening. A few increments and zero checks are blazing fast in comparison and might even happen in parallel with the memory fetches, adding literally no time cost.

2 Likes
8

hello, thanks for your insight its really help me understand double linked list and other confusing concept in rust. but i have one more question about raw pointer in rust.

when i deallocate a linked list head, does all its next node get deallocated or i have to traverse one by one and call mem::drop()?

9

If you use raw pointers, it won't do anything with them by default. But you can write a Drop implementation that traverses the nodes and drops them.

10

Isnt Drop trait only clean when the struct get out of scope? when i delete a node i want to delete everynode next to it? will Drop trait work in this scenario?

example :
Double Linked List:
1 2 3 4 5

i want to delete node 2, when i delete node 2 i want to remove 3 ,4 and 5 from memory

11

Drop also gets called if you call mem::drop() or pointer::drop_in_place().
But if you work with raw pointers and Box you probably use Box::from_raw to drop your elements and then again it gets called when that box goes out of scope.
Dropping the next Node is definetly something that drop could do.

12

hum interesting, but can you explain about Drop trait more because im confuse.

1.when i call mem::drop(Box::from_raw(raw_pointer)) rust deallocate memory in heap; but how do i reference the next node if its already being dropped?

2.if i apply Drop trait to DoubleLinkedList struct how do i pass the next node as parameter?

my current solution is to traverse from tail to target node and run mem::drop() for each node;

13

...but before that it calls Drop::drop for the value inside the Box (i.e. for the next node). Which will call Box::frow_raw for its next node, initiate its drop, and so on.

2 Likes
14

so its get handled by rust? we don't have to do anything else?

sorry if my question kinda stupid, im new to manual memory deallocation