What is the idiomatic lifetime for the "next" pointer in a linked list?

Question

I'm trying to make a simple simple linked list type class where I have a pointer to the next node, but am running into some issues. What would be the proper way to do this?

What I currently have is this:

trait Base {
    fn connect<'a, 'b>(&'a self, next: &'b Base);
}

struct MyStruct<'b> {
    next: Option<&'b Base>, // This should be swapped out with a reference to Base for the next node
}

impl<a', b'> Base for MyStruct<'b> {
    pub fn new() -> MyStruct<'b'> {
        MyStruct { next: None, }
    }

    pub fn connect<'a, 'b>(&'a self, layer: &'b Base) {
        self.next = Some(layer);
    }
}

The way I picture this the lifetime for the struct/node that is connected should be the should be the same as the initial node (i.e. when I deallocate a list it should do so entirely) so it should have one lifetime. However, I believe this causes issues when there is a self pointer as in the connect function.

Why should this question not be marked as a duplicate of [this one](http://stackoverflow.com/q/21152429/155423), [this one](http://stackoverflow.com/q/30441456/155423), [this one](http://stackoverflow.com/q/22268861/155423), [this one](http://stackoverflow.com/q/27750985/155423), [this one](http://stackoverflow.com/q/26434364/155423) or [this one](http://stackoverflow.com/q/31423174/155423)? — Shepmaster, Jul 21 '15 at 19:24
- #1: ~ is not a valid rust operator anymore, They use a List backend inside the Node. I want to implement node walking - #2: Is copying the node, not setting a reference - #3: ~ is not a valid rust operator anymore. https://doc.rust-lang.org/collections/linked_list/struct.Rawlink.html is not valid. Is implementing this the best way?#4: Again, value is constructed in the call. #5: Has nothing about adding. It only references going to the next operator. #6: Is about extending a generic trait, has nothing to do with multiple lifetimes — bge0, Jul 21 '15 at 20:44
My question is different in that: the added object(s) are NOT constructed in the connect/add call. They have their own lifetime. — bge0, Jul 21 '15 at 20:44
Your code intent is unclear. `Layer` is not defined and you have numerous typos. Could you please make a reproducible example? Personally, I have several design ideas about this, but I believe what you want to create is not possible in the end, even though I can't prove it. Basically you're messing around with lifetimes in non-compatible ways. Here is an example design: http://is.gd/EjfABd — mdup, Jul 21 '15 at 21:31
I also fail to see how a linked list of references is useful at all (but usefulness is not my call to make, it's up to you!) :) I would be strongly surprised if you couldn't get away with a standard [`LinkedList`](https://doc.rust-lang.org/collections/linked_list/struct.LinkedList.html), whose code is tested and whose intent is clearer. — mdup, Jul 21 '15 at 21:33
Thank you for reviewing those other questions, most people just ignore them, wanting their special question answered! Please [edit] your question to include those details as well as highlighting why your question is different from the normal "I want to make a linked list" question. — Shepmaster, Jul 21 '15 at 23:43
You continue to have numerous typos (`<'b'>` and `a'`). Please try to produce something that compiles (or produces the expected error) on the [Rust Playpen](https://play.rust-lang.org/). — Shepmaster, Jul 21 '15 at 23:47

score 4 · Accepted Answer · edited May 23 '17 at 10:24

4

You say

I have a pointer to the next node

your code shows a reference, not a pointer, so I take it you mean a reference. But you also say

when I deallocate a list it should do so entirely

These two concepts are incompatible. The only thing that can drop an item is the thing that owns the item. This is done by giving up ownership and nothing else taking the ownership. With a reference, you do not own anything, you are simply borrowing it.

Now, you could have an owned pointer to the next item. That's a Box, which represents a heap-allocated item. Then no lifetimes need to come into play, and is covered in this answer.

This type of list would be generic, so you could store an owned item like a String, or a reference to something like a &u32. When the list or list node is dropped, then the String would be dropped too. The references are technically dropped, but dropping a reference does not drop the referred-to item.

Creating a linked list with only references to the next node is... tricky to say the least, and probably not useful.

Your Node would look something like this:

struct Node<'a> {
    next: Option<&'a mut Node<'a>>,
}

You'd have to declare and allocate each and every Node yourself, since there'd be nowhere you could store the Node on the stack from inside a hypothetical "add" method.

You are always going to run into an issue with overlapping lifetimes for the reference to the next node and the lifetime that the next node has (apply induction for a list and it gets really complicated.)

TL;DR It's not clear why want to do this, but basically it's not easy to do (or worth it, in my opinion).

edited May 23 '17 at 10:24

Community

1
1

answered Jul 22 '15 at 00:16

Shepmaster

388,571
95
1,107
1,366

Can you explain the difference between a pointer and a reference? I come from managed languages, where in my head I always thought of references as pointers. – w.brian Jul 22 '15 at 03:21
2

a pointer is just an integer that contains the address of a memory location. a reference additionally has the guarantees about validity and types of the object at the memory location. – oli_obk Jul 22 '15 at 06:20
2

@w.brian: When you say "pointer" it's not clear what you mean. In Rust, we simply call `&T` references and `*T` raw pointers. At the machine level, they are very much the same. But the language treats them differently. For example, a reference is always valid an represents "borrowing". A raw pointer can be null and does not say anything about ownership/borrowing. They are primarily used to implement higher level and safe abstractions. – sellibitze Jul 22 '15 at 13:19
2

@w.brian: In Rust, references and boxes are both variations on pointers. The difference is ownership. A reference refers (points) to data owned by someone else. A box, on the other hand, "owns" its referent: when a Box is moved (changes ownership), the T it points to moves along with it. There are other kinds of pointers, too. Rc points to memory that is not singularly owned, but shared among all the Rc-pointers to it. Raw pointers are like references, but they aren't checked for validity, like ker said. (But they do have types, even in C.) – trent Jul 22 '15 at 15:14
1

@w.brian adding to the wonderful clarifications above, the fact that Rust differentiates between these meanings is a **good thing**. In C, for example, having a `char *` tells you nothing about if you now own the pointer or it's being borrowed. Rust splits the concepts apart, encoding them into types to make things way easier to understand. – Shepmaster Jul 23 '15 at 15:45

What is the idiomatic lifetime for the "next" pointer in a linked list?

1 Answers1