Intrusive data structure benefits over normal ones

help
1

hello, I am trying to understand intrusive data structure with this linked list example. I understand that for T to be an element of a single linked list it must store a pointer to next inside of T, and thus containing a list embedded inside T itself. But how does this help? How is this better as compared to a normal singly linked list and how does this reduce the overall allocation?


use std::cell::Cell;
use std::marker::PhantomData;
use std::ptr::NonNull;

struct Foo {
    value: i32,
    next: Cell<Option<NonNull<Foo>>>,
}

struct SingleLinkedIntrusiveList<'b, T>
where
    T: SingleLinkedIntrusiveListItem,
{
    first: Cell<Option<NonNull<T>>>,
    last: Cell<Option<NonNull<T>>>,
    _marker: core::marker::PhantomData<&'b ()>,
}

trait SingleLinkedIntrusiveListItem {
    fn next(&self) -> Option<NonNull<Self>>;
    fn set_next(&self, new_next: Option<NonNull<Self>>);
}

impl SingleLinkedIntrusiveListItem for Foo {
    fn next(&self) -> Option<NonNull<Self>> {
        self.next.get()
    }

    fn set_next(&self, new_next: Option<NonNull<Self>>) {
        self.next.set(new_next)
    }
}
2

An intrusive linked list can be used in a more versatile way, for example:

  • you can make a node part of more than one intrusive linked list
  • you can store the nodes somewhere else instead of having them be managed by the linked list
  • not all values need to have the same "shape"
3

in the code example did we just create a simple linked list? or does it have any different properties when compared to a simple linked list?

could you please elaborate on this, thank you!