Why does a node in a linked list using raw pointers become corrupted?

Question

I am struggling to learn raw pointers while implementing a linked list. A simple piece of code gives me unintended results for which I struggle to find any explanation whatsoever:

use std::cmp::PartialEq;
use std::default::Default;
use std::ptr;

pub struct LinkedListElement<T> {
    pub data: T,
    pub next: *mut LinkedListElement<T>,
}

pub struct LinkedList<T> {
    head: *mut LinkedListElement<T>,
}

impl<T: PartialEq> LinkedListElement<T> {
    pub fn new(elem: T, next: Option<*mut LinkedListElement<T>>) -> LinkedListElement<T> {
        let mut_ptr = match next {
            Some(t) => t,
            None => ptr::null_mut(),
        };
        let new_elem = LinkedListElement {
            data: elem,
            next: mut_ptr,
        };
        if !mut_ptr.is_null() {
            println!(
                "post create ll mut ptr: {:p}, post create ll mut ptr next {:p}",
                mut_ptr,
                unsafe { (*mut_ptr).next }
            );
        }
        new_elem
    }
}

impl<T: PartialEq + Default> LinkedList<T> {
    pub fn new(elem: T) -> LinkedList<T> {
        LinkedList {
            head: &mut LinkedListElement::new(elem, None),
        }
    }

    pub fn insert(&mut self, elem: T) {
        println!("head: {:p} . next: {:p}", self.head, unsafe {
            (*self.head).next
        });
        let next = Some(self.head);
        let mut ll_elem = LinkedListElement::new(elem, next);
        println!(
            "before pointer head: {:p}. before pointer next {:p}",
            self.head,
            unsafe { (*self.head).next }
        );
        let ll_elem_ptr = &mut ll_elem as *mut LinkedListElement<T>;
        self.head = ll_elem_ptr;
    }
}

fn main() {
    let elem: i32 = 32;
    let second_elem: i32 = 64;
    let third_elem: i32 = 72;
    let mut list = LinkedList::new(elem);
    list.insert(second_elem);
    list.insert(third_elem);
}

(playground)

This code gives me the following output:

head: 0x7ffe163275e8 . next: 0x0
post create ll mut ptr: 0x7ffe163275e8, post create ll mut ptr next 0x0
before pointer head: 0x7ffe163275e8. before pointer next 0x0
head: 0x7ffe16327560 . next: 0x7ffe163275e8
post create ll mut ptr: 0x7ffe16327560, post create ll mut ptr next 0x7ffe163275e8
before pointer head: 0x7ffe16327560. before pointer next 0x7ffe16327560

For the first 2 elements the code behaves as expected: it creates an element with null pointer as its next element. Here is the state of things after adding second element:

{
  head: {
    elem: 64,
    next: {
      elem: 32,
      next: nullptr
    }
  }
}

64 -> 32 -> null

When the third element is added, things become weird and the linked list transforms into something like this:

{
  head: {
    elem: 72,
    next: {
      elem: 72,
      next: {
        elem: 72,
        next: ...
      }
    }
  }
}

72 -> 72 -> 72 -> ...

It seems that the linked list element's next field starts pointing at the element itself.

I have debugged the LinkedListElement::new method and found that the proper element should get returned from it:

{
  elem: 72,
  next: {
    elem: 64,
    next: {
      elem: 32,
      next: nullptr
    }
  }
}

For some reason, immediately after it is returned to LinkedList::insert method, even before self.head is reassigned, the contents of LinkedList self becomes "corrupted".

I know using raw pointers in Rust is not idiomatic but I still want to learn them.

`head: &mut LinkedListElement::new(elem, None)` you are taking stack address here — Stargateur, May 14 '19 at 23:35
Have you taken the time to read [*Learning Rust With Entirely Too Many Linked Lists*](https://cglab.ca/~abeinges/blah/too-many-lists/book/README.html)? — Shepmaster, May 15 '19 at 02:34
There's actually several great walkthroughs over [here](https://rust-unofficial.github.io/too-many-lists/second-option.html), one of which I think goes along with what you're trying to do. Especially [here](https://rust-unofficial.github.io/too-many-lists/fifth-layout.html), you can see that the resultant solution entails `prev` and `next` links being of type `Option>`. — Jesse Lawson, May 15 '19 at 02:39

score 5 · Answer 1 · edited May 15 '19 at 07:58

Congratulations, you have successfully proven why Rust needs to exist in the first place: programmers write memory-unsafe code.

First, please read why this is disallowed when using safe Rust:

Is there any way to return a reference to a variable created in a function?

TL;DR: the memory address of LinkedListElement changes when it's moved. A move occurs when a value is returned from a function (among other times). By using a raw pointer, you've subverted the borrow checker and get no useful feedback from the compiler.

Second, please read Learning Rust With Entirely Too Many Linked Lists. For whatever reason, programmers think that linked lists are "easy" and a good way to learn a language. This is generally not true in Rust, where memory safety is paramount.

TL;DR: you can use a Box to allocate memory on the heap. This memory address will not change when the pointer to it is moved. You will need to ensure that you appropriately free the pointer when your linked list goes out of scope to prevent memory leaks.

Why does a node in a linked list using raw pointers become corrupted?

1 Answers1