Doubly linked list in Rust using raw pointers

Question

I am practicing Rust by writing doubly linked list using raw pointers, Box<node> to allocate data on heap, Box::from_raw to free data from heap. I feel it very silly to use a lot of unsafe blocks.

struct node<T> {
 value: T,
 prev: *mut node<T>,
 next: *mut node<T>
}
impl<T> Drop for node<T> {
 fn drop(self: &mut Self) {
 println!("Dropping anode");
 }
}
impl<T> node<T> {
 fn new(value: T, prev: *mut node<T>, next: *mut node<T>) -> Self {
 return Self{value: value, prev: prev, next: next};
 }
}
struct list<T> {
 root: *mut node<T>
}
impl<T> Drop for list<T> {
 fn drop(self: &mut Self) {
 let mut this: *mut node<T> = self.root;
 let mut drop: *mut node<T> = std::ptr::null_mut();
 while this != std::ptr::null_mut() {
 drop = this;
 unsafe {this = (*this).next;}
 unsafe {let anode = Box::from_raw(drop);}
 }
 }
}
impl std::fmt::Display for list<f64> {
 fn fmt(self: &Self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
 write!(f, "[");
 let mut this: *mut node<f64> = self.root;
 while this != std::ptr::null_mut() {
 unsafe {write!(f, "{} ", (*this).value);}
 unsafe {this = (*this).next;}
 }
 write!(f, "]");
 return Ok(());
 }
}
impl<T> list<T> {
 fn new() -> Self {
 let p : *mut node<T> = std::ptr::null_mut();
 return Self {root: p};
 }
 fn len(self: &Self) -> i32 {
 let mut len: i32 = 0;
 let mut this: *mut node<T> = self.root;
 while this != std::ptr::null_mut()
 {
 len += 1;
 unsafe {
 this = (*this).next;
 }
 }
 return len;
 }
 fn getnode(self: &Self, mut i: i32) -> *mut node<T> {
 let mut this: *mut node<T> = self.root;
 let mut next: *mut node<T> = std::ptr::null_mut();
 while i > 0 {
 unsafe {
 next = (*this).next;
 }
 if next == std::ptr::null_mut() {
 return std::ptr::null_mut();
 } else {
 i -= 1;
 this = next;
 }
 }
 return this;
 }
 fn insert(mut self: &mut Self, mut i: i32, value: T) {
 let mut next: *mut node<T> = self.getnode(i);
 let mut prev: *mut node<T> = std::ptr::null_mut();
 if i != 0 {
 if next == std::ptr::null_mut() {
 let lastindex: i32 = self.len() - 1;
 prev = self.getnode(lastindex);
 } else {
 unsafe {prev = (*next).prev;}
 }
 }
 let mut anode: Box<node<T>> = Box::new(node::new(value, prev, next));
 let mut this = Box::into_raw(anode);
 if i == 0 {
 self.root = this;
 }
 if next != std::ptr::null_mut() {
 unsafe {(*next).prev = this;}
 }
 if prev != std::ptr::null_mut() {
 unsafe {(*prev).next = this;}
 }
 }
 fn erase(mut self: &mut Self, mut i: i32) {
 let mut this: *mut node<T> = self.getnode(i);
 if this == std::ptr::null_mut() {return;}
 let mut prev: *mut node<T> = std::ptr::null_mut();
 let mut next: *mut node<T> = std::ptr::null_mut();
 unsafe {
 prev = (*this).prev;
 next = (*this).next;
 }
 if prev != std::ptr::null_mut() {
 unsafe {(*prev).next = next;}
 }
 if next != std::ptr::null_mut() {
 unsafe {(*next).prev = prev;}
 }
 if i == 0 {
 self.root = next;
 }
 unsafe {let anode: Box<node<T>> = Box::from_raw(this);}
 }
 fn getvalue(self: Self, mut i: i32) -> &'static T {
 let this: *mut node<T> = self.getnode(i);
 unsafe {
 return &(*this).value;
 }
 }
}
pub fn main() {
 let mut l: list<f64> = list::new();
 l.insert(0, 3.0);
 println!("{}", l);
 l.insert(0, 4.0);
 println!("{}", l);
 l.insert(1, 1.0);
 println!("{}", l);
 l.insert(2, 6.0);
 println!("{}", l);
 l.insert(2, 5.4);
 println!("{}", l);
 l.insert(5, 3.3);
 println!("{}", l);
 l.erase(3);
 println!("{}", l);
 l.erase(4);
 println!("{}", l);
 l.erase(0);
 println!("{}", l);
}

• IEatBagels: Hi, please use a title that reflect what your code does, not what you want from the review :)
• sdht0: You may want to read through github.com/rust-unofficial/too-many-lists, which builds quite a few linked lists in Rust.

Answer 1

Note: I will not consider the question whether raw pointers are the best approach to building a linked list, but you could look at smart pointers for alternatives.

Compiler warnings

Running this code gives 21 warnings and suggestions what to change. Many of them refer to unused variables or unnecessary usages of mut. Listen to them and fix them:

• node, list should be Node, List
• remove unnecessary mut
• use ? after the write! calls to return any possible errors
• do not initialize values to null and overwrite them then, just use

let mut variable_name;

instead of

let mut variable_name: *mut node<T> = std::ptr::null_mut();

Style

Use cargo clippy to find many more issues, such as:

• self: &Self -> &self, self: &mut Self -> &mut self
• shorthand initialization:

Self {
 value: value,
 prev: prev,
 next: next,
}

can be just

Self {
 value,
 prev,
 next,
}

• unneeded return at the end of a function
• use ptr.is_null() instead of ptr == std::ptr::null_mut()

Debugging artifact

This implementation seems to be a remaining piece of debugging that shouldn't be kept in production:

impl<T> Drop for Node<T> {
 fn drop(&mut self) {
 println!("Dropping anode");
 }
}

More flexible Display for List

Right now, you only implement it for List<f64>, but you can implement it for any type that implements Display:

use std::fmt;
impl<T: fmt::Display> fmt::Display for List<T> {
 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 write!(f, "[")?;
 let mut this = self.root;
 while !this.is_null() {
 unsafe {
 write!(f, "{} ", (*this).value)?;
 }
 unsafe {
 this = (*this).next;
 }
 }
 write!(f, "]")?;
 Ok(())
 }
}

Likely typo

List::getvalue should probably take &self instead of self as an argument to avoid consuming the entire list.

Final code

I have also used cargo fmt to format the code according to the rust style guidelines.

use std::fmt;
struct Node<T> {
 value: T,
 prev: *mut Node<T>,
 next: *mut Node<T>,
}
impl<T> Node<T> {
 fn new(value: T, prev: *mut Node<T>, next: *mut Node<T>) -> Self {
 Self { value, prev, next }
 }
}
struct List<T> {
 root: *mut Node<T>,
}
impl<T> Drop for List<T> {
 fn drop(&mut self) {
 let mut this = self.root;
 while !this.is_null() {
 let dropped = this;
 unsafe {
 this = (*this).next;
 }
 unsafe {
 drop(Box::from_raw(dropped));
 }
 }
 }
}
impl<T: fmt::Display> fmt::Display for List<T> {
 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 write!(f, "[")?;
 let mut this = self.root;
 while !this.is_null() {
 unsafe {
 write!(f, "{} ", (*this).value)?;
 }
 unsafe {
 this = (*this).next;
 }
 }
 write!(f, "]")?;
 Ok(())
 }
}
impl<T> List<T> {
 fn new() -> Self {
 Self {
 root: std::ptr::null_mut(),
 }
 }
 fn len(&self) -> i32 {
 let mut len = 0;
 let mut this = self.root;
 while !this.is_null() {
 len += 1;
 unsafe {
 this = (*this).next;
 }
 }
 len
 }
 fn getnode(&self, mut i: i32) -> *mut Node<T> {
 let mut this = self.root;
 let mut next;
 while i > 0 {
 unsafe {
 next = (*this).next;
 }
 if next.is_null() {
 return std::ptr::null_mut();
 } else {
 i -= 1;
 this = next;
 }
 }
 this
 }
 fn insert(&mut self, i: i32, value: T) {
 let next = self.getnode(i);
 let mut prev = std::ptr::null_mut();
 if i != 0 {
 if next.is_null() {
 let lastindex = self.len() - 1;
 prev = self.getnode(lastindex);
 } else {
 unsafe {
 prev = (*next).prev;
 }
 }
 }
 let anode = Box::new(Node::new(value, prev, next));
 let this = Box::into_raw(anode);
 if i == 0 {
 self.root = this;
 }
 if !next.is_null() {
 unsafe {
 (*next).prev = this;
 }
 }
 if !prev.is_null() {
 unsafe {
 (*prev).next = this;
 }
 }
 }
 fn erase(&mut self, i: i32) {
 let this = self.getnode(i);
 if this.is_null() {
 return;
 }
 let prev;
 let next;
 unsafe {
 prev = (*this).prev;
 next = (*this).next;
 }
 if !prev.is_null() {
 unsafe {
 (*prev).next = next;
 }
 }
 if !next.is_null() {
 unsafe {
 (*next).prev = prev;
 }
 }
 if i == 0 {
 self.root = next;
 }
 unsafe {
 drop(Box::from_raw(this));
 }
 }
 fn getvalue(&self, i: i32) -> &'static T {
 let this = self.getnode(i);
 unsafe { &(*this).value }
 }
}
pub fn main() {
 let mut l = List::new();
 l.insert(0, 3.0);
 println!("{}", l);
 l.insert(0, 4.0);
 println!("{}", l);
 l.insert(1, 1.0);
 println!("{}", l);
 l.insert(2, 6.0);
 println!("{}", l);
 l.insert(2, 5.4);
 println!("{}", l);
 l.insert(5, 3.3);
 println!("{}", l);
 l.erase(3);
 println!("{}", l);
 l.erase(4);
 println!("{}", l);
 l.erase(0);
 println!("{}", l);
}