Skip to content

Instantly share code, notes, and snippets.

@davassi
Last active September 24, 2023 14:05
Show Gist options
  • Save davassi/3aaa797d47b17722f1691f1bb212deeb to your computer and use it in GitHub Desktop.
Save davassi/3aaa797d47b17722f1691f1bb212deeb to your computer and use it in GitHub Desktop.
A double linked list
use std::{rc::Rc, cell::RefCell, fmt::Display};
type Pointer<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
data: T,
next : Pointer<T>,
prev : Pointer<T>,
}
impl<T> Node<T> {
pub fn new(data: T, next: Pointer<T>, prev: Pointer<T>) -> Self {
Node { data, next, prev }
}
}
pub struct DoubleLinkedList<T> {
first : Pointer<T>,
last : Pointer<T>,
size : u32,
}
impl<T> DoubleLinkedList<T> {
pub fn new() -> Self {
DoubleLinkedList { first : None, last: None, size : 0 }
}
pub fn push(&mut self, data: T) {
let new_node = Some(Rc::new(RefCell::new(Node::new(data, None, self.last.clone()))));
if self.first.is_none() { // first append
self.first = new_node;
self.last = self.first.clone();
} else {
if let Some(last_node_rc) = self.last.take() {
let mut last_node = last_node_rc.as_ref().borrow_mut();
last_node.next = new_node.clone();
}
self.last = new_node.clone();
}
self.size = self.size + 1;
}
pub fn pop(&mut self) -> Option<T> {
if self.last.is_none() {
return None;
}
if let Some(last_node_rc) = self.last.take() {
let ss = Rc::try_unwrap(last_node_rc.clone()).ok().unwrap().into_inner().data;
return Some(ss);
}
None
}
pub fn empty(&self) -> bool {
self.first.is_none()
}
pub fn len(&self) -> u32 {
self.size
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment