Last active
September 24, 2023 14:05
-
-
Save davassi/3aaa797d47b17722f1691f1bb212deeb to your computer and use it in GitHub Desktop.
A double linked list
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::{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