Learning rust and looking for help

Hello, I am a newbie and coming from a Java background. My exposure to pointers/address, are not that great. I do understand the concepts but not good enough to solve the issue. I am trying to migrate reversing the linked list from Java. Please note that the logic is working and was tested with Java. I am trying to implement the same logic with the rust code below...

use std::option::Option;

struct ReverseLinkedList;

impl ReverseLinkedList {
    pub fn reverse_list(head: &Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        if head.is_none() {
            return Option::None;
        }
        let mut prev = head;
        let mut current = prev.unwrap().next;
        let mut next = None;
        prev.unwrap().next = None;
        while !current.is_none() {
            next = current.unwrap().next;
            current.unwrap().next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

fn main() {
    let _5 = ListNode { next: None, val: 5 };
    let _4 = ListNode {
        next: Some(Box::new(_5)),
        val: 4,
    };
    let _3 = ListNode {
        next: Some(Box::new(_4)),
        val: 3,
    };
    let _2 = ListNode {
        next: Some(Box::new(_3)),
        val: 2,
    };
    let _1 = ListNode {
        next: Some(Box::new(_2)),
        val: 1,
    };
    let _result = ReverseLinkedList::reverse_list(&Some(Box::new(_1)));
}

and getting compilation error given below

error[E0308]: mismatched types                                                             
  --> projects/rust/puzzles/src/reverse_linked_list.rs:16:37
   |                          
16 |             current.unwrap().next = prev;
   |             ---------------------   ^^^^ expected enum `Option`, found reference
   |             |
   |             expected due to the type of this binding
   |
   = note:   expected enum `Option<Box<ListNode>>`
           found reference `&Option<Box<ListNode>>`

error[E0308]: mismatched types
  --> projects/rust/puzzles/src/reverse_linked_list.rs:17:20
   |
10 |         let mut prev = head;
   |                        ---- expected due to this value
...
17 |             prev = current;
   |                    ^^^^^^^
   |                    |
   |                    expected reference, found enum `Option`
   |                    help: consider borrowing here: `&current`

Please let me know what is going wrong here. Your response is appreciated.

Below is the Java code for reference

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        ListNode prev = head;
        ListNode current = prev.next;
        ListNode next = null;
        System.out.println("Start with prev: " + prev.val + ", and current: " + current.val);
        prev.next = null; // break off the link, after reversing, the head will be null
        while (current != null) {            
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
            if (current != null) next = current.next;
            System.out.println("Current loop status prev: " + prev.val + ", current: " + ((current != null) ?  current.val : "null") + ", next = " + ((next != null) ? next.val : "null"));
        }
        return prev;
    }
    
    public static void main(String[] args) {
        ReverseLinkedList app = new ReverseLinkedList();
        ListNode _1 = new ListNode(1);
        ListNode _2 = new ListNode(2);
        ListNode _3 = new ListNode(3);
        ListNode _4 = new ListNode(4);
        ListNode _5 = new ListNode(5);
        _1.next = _2;
        _2.next = _3;
        _3.next = _4;
        _4.next = _5;
        ListNode reversedHeadNode = app.reverseList(_1);
        while (reversedHeadNode != null) {
            System.out.println("reversedHeadNode: " + reversedHeadNode.val);
            reversedHeadNode = reversedHeadNode.next;
        }
    }
}
1 Like

You probably want to read Learning Rust with Entirely Too Many Linked Lists.

I'm not sure there's anything I could add that wouldn't be said better by that book. Yes, there is a book on how to write linked lists in Rust. Turns out Rust and linked lists really don't get along well. It's among one of the worst possible first learning projects you can undertake, because you immediately hit a bunch of problems particular to Rust that you likely won't have any experience with (certainly not when coming from Java.)

That said, two three quick notes:

  1. You don't need the ReverseLinkedList type in order to define reverse_list. There's no value in doing so. If you really want to contain the function in a namespace, just use a module.

  2. Note that #[inline] is just a suggestion, and has absolutely zero effect except for non-generic code being used by an external crate (i.e. non-generic functions being exported from a library and used elsewhere). In particular, it does nothing in a case like this where all the code is in a single crate.

  3. Edit: The specific error you have is because you're trying to mix references to values with straight values, and you just can't. I had some stuff written up about why this is, but the problems with this code are deep enough that I was starting to just re-explain everything Too Many Linked Lists does, but worse. Seriously, read it.

8 Likes

To temper that a bit, rust and doubly-linked lists don't get along well, but singly linked lists are straightforward in rust because all nodes have very clear/unique ownership (the same reason they work very well in functional programming languages as well).

The code for reversing a linked list is here:

Effectively, you can treat your singly-linked list as a stack and pop the head element and push it into another singly-linked list (which I denoted as rev_head in the solution linked above).

7 Likes

Thank you for the response and pointing to the direction.

1 Like

Thanks for the perfect example.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.