Last active
January 26, 2024 19:52
-
-
Save BlueZeeKing/4e319d794e61e507792c13b816df4dfa to your computer and use it in GitHub Desktop.
A simple doubly linked list in Rust using pointers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::{marker::PhantomPinned, pin::Pin}; | |
pub struct Node<T> { | |
value: T, | |
next: Option<Box<Node<T>>>, | |
prev: Option<*mut Node<T>>, | |
_pantom: PhantomPinned, | |
} | |
pub struct List<T> { | |
first: Option<Box<Node<T>>>, | |
last: Option<*mut Node<T>>, | |
} | |
impl<T> Default for List<T> { | |
fn default() -> Self { | |
Self::empty() | |
} | |
} | |
impl<T> List<T> { | |
pub fn new(value: T) -> Self { | |
let mut node = Box::new(Node::new(value)); | |
let ptr = node.as_mut() as *mut Node<T>; | |
Self { | |
first: Some(node), | |
last: Some(ptr), | |
} | |
} | |
pub fn empty() -> Self { | |
Self { | |
first: None, | |
last: None, | |
} | |
} | |
pub fn first(&self) -> Option<&Node<T>> { | |
self.first.as_deref() | |
} | |
pub fn first_mut(&mut self) -> Option<Pin<&mut Node<T>>> { | |
self.first | |
.as_deref_mut() | |
.map(|val| unsafe { Pin::new_unchecked(val) }) | |
} | |
pub fn last(&self) -> Option<&Node<T>> { | |
self.last.map(|ptr| unsafe { ptr.as_ref().unwrap() }) | |
} | |
pub fn last_mut(&mut self) -> Option<Pin<&mut Node<T>>> { | |
self.last | |
.map(|val| unsafe { Pin::new_unchecked(val.as_mut().unwrap()) }) | |
} | |
pub fn append(&mut self, value: T) { | |
if self.first.is_none() { | |
let mut node = Box::new(Node::new(value)); | |
let ptr = node.as_mut() as *mut Node<T>; | |
self.first = Some(node); | |
self.last = Some(ptr); | |
} else { | |
let mut node = Box::new(Node::new(value)); | |
let ptr = node.as_mut() as *mut Node<T>; | |
let last = unsafe { self.last.replace(ptr).unwrap().as_mut().unwrap() }; | |
node.prev = Some(last); | |
last.next = Some(node); | |
} | |
} | |
pub fn pop(&mut self) -> Option<T> { | |
if self.last == None { | |
None | |
} else if self.first.as_ref().unwrap().next.is_none() { | |
let val = self.first.take().unwrap().value; | |
self.last = None; | |
Some(val) | |
} else { | |
self.last = Some(unsafe { self.last.unwrap().as_ref().unwrap().prev.unwrap() }); | |
let last = unsafe { self.last.unwrap().as_mut().unwrap().next.take() }; | |
Some(last.unwrap().value) | |
} | |
} | |
pub fn prepend(&mut self, value: T) { | |
let mut node = Box::new(Node::new(value)); | |
if self.last.is_none() { | |
self.last = Some(node.as_mut()); | |
} | |
if let Some(mut old_node) = self.first.replace(node) { | |
old_node.prev = Some(self.first.as_deref_mut().unwrap()); | |
self.first.as_mut().unwrap().next = Some(old_node); | |
} | |
} | |
pub fn pop_front(&mut self) -> Option<T> { | |
if self.first.is_none() { | |
None | |
} else if self.first.as_ref().unwrap().next.is_none() { | |
let val = self.first.take().unwrap().value; | |
self.last = None; | |
Some(val) | |
} else { | |
let mut first = self.first.take().unwrap(); | |
self.first = Some(first.next.take().unwrap()); | |
Some(first.value) | |
} | |
} | |
} | |
impl<T> Iterator for List<T> { | |
type Item = T; | |
fn next(&mut self) -> Option<Self::Item> { | |
self.pop_front() | |
} | |
} | |
impl<T> DoubleEndedIterator for List<T> { | |
fn next_back(&mut self) -> Option<Self::Item> { | |
self.pop() | |
} | |
} | |
impl<T> Node<T> { | |
fn new(value: T) -> Self { | |
Self { | |
value, | |
next: None, | |
prev: None, | |
_pantom: PhantomPinned, | |
} | |
} | |
pub fn value(&self) -> &T { | |
&self.value | |
} | |
fn unpin_value_mut(&mut self) -> &mut T { | |
&mut self.value | |
} | |
pub fn value_mut(self: Pin<&mut Self>) -> &mut T { | |
unsafe { Pin::into_inner_unchecked(self) }.unpin_value_mut() | |
} | |
pub fn next(&self) -> Option<&Self> { | |
self.next.as_deref() | |
} | |
fn unpin_next_mut(&mut self) -> Option<Pin<&mut Self>> { | |
self.next | |
.as_deref_mut() | |
.map(|value| unsafe { Pin::new_unchecked(value) }) | |
} | |
pub fn next_mut(self: Pin<&mut Self>) -> Option<Pin<&mut Self>> { | |
unsafe { Pin::into_inner_unchecked(self) }.unpin_next_mut() | |
} | |
pub fn prev(&self) -> Option<&Self> { | |
if let Some(ptr) = self.prev { | |
Some(unsafe { ptr.as_ref() }.unwrap()) | |
} else { | |
None | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment