Linked Lists - Doubly Linked List
Alright, we covered singly linked list in the previous article, now it's time for a doubly linked list, which to be honest isn't that different much from a singly linked list. The only difference is we that each node contains a reference to the previous node also allowing us to walk in both forward and backward direction.
So, we will get three items in each node, the stored value, a pointer for next node and a pointer for previous node. Everything else will be the same as in singly linked list.
We will use two pointer technique here marking both head and tail of our list. Every new node will become the head of our list. So, let's start with the structure of our node:
type StrongLink<T> = Option<Rc<RefCell<Node<T>>>>;
type WeakLink<T> = Option<Weak<RefCell<Node<T>>>>;
pub struct Node<T> {
data: T,
next: StrongLink<T>,
prev: WeakLink<T>
}
We have two pointers in each node, next one is strong pointer and previous one is weak. Now the difference between both is that the weak one will not actually own the value. So, there will not be any conflict of recursive ownership issues. Another thing to notice is RefCell inside both, which allows us to mutate the node without any lifetime issues. So, it's simply bypassing the rust borrow checker.
Also, we got a simple function to easily create new nodes:
impl<T> Node<T> {
pub fn new(data: T) -> Self
{
Node {
data,
next: None,
prev: None
}
}
}
Thats all we need for Node struct, let's move on to logic for our list.
pub struct List<T>
{
head: StrongLink<T>,
tail: StrongLink<T>,
length: i32
}
Let's break down this struct. First, we have head field as StrongLink<T> which is simply Option<Rc<RefCell<Node<T>>>>. The reason we made it strong link instead of weak link is that rust will never drop it if there is a strong link to a node. Same goes for the tail field. At the end, we have the length field representing the length of our doubly linked list.
We also got a simple constructor function to help make a list easily:
pub fn new() -> Self
{
List {
head: None,
tail: None,
length: 0
}
}
Now that's covered, it's time to implement our first method push_front which will be used to push a new item in front of the list making it head of the list.
pub fn push_front(&mut self, value: T)
{
if let Some(head) = self.head.take() {
let mut new_node = Node::new(value);
new_node.prev = Some(Rc::downgrade(&head));
let rc = Rc::new(RefCell::new(new_node));
head.borrow_mut().next = Some(Rc::clone(&rc));
self.head = Some(Rc::clone(&rc));
} else {
let new_node = Rc::new(RefCell::new(Node::new(value)));
self.head = Some(Rc::clone(&new_node));
self.tail = Some(new_node);
};
self.length += 1;
}
Let's break down the arguments first. We have the mutable reference to self so we can change the head field to point to the new node that we are about to push. Second argument is the value being pushed.
As we learned in Singly Linked List, the take() method on head option will simply take the value out from inside the option and transfer its ownership and finally set the head as None. So, we will get Rc<RefCell<Node<T>>> as head in the Some branch of if let statement.
Next, we make a new node with provided value using new method Node::new(value). But this node is not attached to the list. It's prev and next fields are None for now.
For prev field we will get the reference to head because after pushing new node it becomes new head, while the old head becomes 2nd last item from front. We achieved this using Some(Rc::downgrade(&head)). The Rc::downgrade method is used to make weak pointer to the node.
Finally, we will make a new node wrapped in RefCell and Rc and mark it as next field for the old head. Now we a successfully linked the new node with the list except one step which is marking this new node as the new head. Which we achieve using the line self.head = Some(Rc::clone(&rc));.
On the other hand, if head is not set yet. We will simply make a new node like above and mark it as both head and tail.
Last thing is increasing the length of our linked list. And with this, we have finished the push_front method.
Now we got the push_back method, which is almost exactly like push_front method but with the replacement of head as tail.
pub fn push_back(&mut self, value: T)
{
if let Some(tail) = self.tail.take() {
let mut new_node = Node::new(value);
new_node.next = Some(Rc::clone(&tail));
let rc = Rc::new(RefCell::new(new_node));
tail.borrow_mut().prev = Some(Rc::downgrade(&rc));
self.tail = Some(Rc::clone(&rc));
} else {
let new_node = Rc::new(RefCell::new(Node::new(value)));
self.head = Some(Rc::clone(&new_node));
self.tail = Some(new_node);
}
self.length += 1;
}
We are basically just adding the new node as the new tail. Everything is almost the same as push_front so we will not go through every line here.
After that, we got pop_front method to remove the head node, making the node next to current head the new head. If there is no node then make it None.
pub fn pop_front(&mut self)
{
if let Some(head) = self.head.take() {
if let Some(weak_node) = &head.borrow().prev {
if let Some(node) = weak_node.upgrade() {
node.borrow_mut().next = None;
self.head = Some(Rc::clone(&node));
self.length -= 1;
}
}
}
}
Alright, first we are simply taking the head using take() method which will provide us the inner head leaving None behind. Now, we will simply take the node next to head if its available. But since prev field gives a weak reference, we need to upgrade it first making sure it's available. We will use the upgrade method to upgrade the weak reference to a strong reference.
Then we will make this node the new head and decrease the length of the list because we have successfully removed the front node.
You might be wondering that we didn't remove the old head. The answer is since there are no references to the old head left anymore, rust will automatically remove it from the memory once it goes out of scope.
We got another method pop_back which works similar to pop_front but it will remove the tail node instead of head node.
pub fn pop_back(&mut self)
{
if let Some(tail) = self.tail.take() {
if let Some(node) = &tail.borrow().next {
node.borrow_mut().prev = None;
self.tail = Some(Rc::clone(&node));
self.length -= 1;
}
}
}
Here is the final code with tests and Display trait implementation:
use std::{cell::RefCell, rc::{Rc, Weak}, fmt::{Display,Formatter, Result}};
type StrongLink<T> = Option<Rc<RefCell<Node<T>>>>;
type WeakLink<T> = Option<Weak<RefCell<Node<T>>>>;
pub struct Node<T> {
data: T,
next: StrongLink<T>,
prev: WeakLink<T>
}
impl<T> Node<T> {
pub fn new(data: T) -> Self
{
Node {
data,
next: None,
prev: None
}
}
}
pub struct List<T>
{
head: StrongLink<T>,
tail: StrongLink<T>,
length: i32
}
impl<T> List<T> {
pub fn new() -> Self
{
List {
head: None,
tail: None,
length: 0
}
}
pub fn push_front(&mut self, value: T)
{
if let Some(head) = self.head.take() {
let mut new_node = Node::new(value);
new_node.prev = Some(Rc::downgrade(&head));
let rc = Rc::new(RefCell::new(new_node));
head.borrow_mut().next = Some(Rc::clone(&rc));
self.head = Some(Rc::clone(&rc));
} else {
let new_node = Rc::new(RefCell::new(Node::new(value)));
self.head = Some(Rc::clone(&new_node));
self.tail = Some(new_node);
};
self.length += 1;
}
pub fn push_back(&mut self, value: T)
{
if let Some(tail) = self.tail.take() {
let mut new_node = Node::new(value);
new_node.next = Some(Rc::clone(&tail));
let rc = Rc::new(RefCell::new(new_node));
tail.borrow_mut().prev = Some(Rc::downgrade(&rc));
self.tail = Some(Rc::clone(&rc));
} else {
let new_node = Rc::new(RefCell::new(Node::new(value)));
self.head = Some(Rc::clone(&new_node));
self.tail = Some(new_node);
}
self.length += 1;
}
pub fn pop_front(&mut self)
{
if let Some(head) = self.head.take() {
if let Some(weak_node) = &head.borrow().prev {
if let Some(node) = weak_node.upgrade() {
node.borrow_mut().next = None;
self.head = Some(Rc::clone(&node));
self.length -= 1;
}
}
}
}
pub fn pop_back(&mut self)
{
if let Some(tail) = self.tail.take() {
if let Some(node) = &tail.borrow().next {
node.borrow_mut().prev = None;
self.tail = Some(Rc::clone(&node));
self.length -= 1;
}
}
}
}
impl<T: Display> Display for List<T> {
fn fmt(&self, f: &mut Formatter) -> Result
{
write!(f, "[")?;
let mut node = self.head.clone();
while let Some(n) = node
{
write!(f, "{}", n.borrow().data)?;
// node = n.borrow().next.clone();
node = match &n.borrow().prev {
Some(p) => p.upgrade(),
None => None
};
if node.is_some()
{
write!(f, ", ")?;
}
};
write!(f, "]")
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn push_working_fine() {
let mut list: List<i32> = List::new();
list.push_front(42);
list.push_back(63);
list.push_front(100);
list.push_front(58);
list.push_back(195);
assert_eq!(5,list.length);
}
#[test]
fn pop_working_fine() {
let mut list: List<i32> = List::new();
list.push_front(45);
list.push_front(76);
list.push_front(12);
list.pop_front();
assert_eq!(2,list.length);
list.pop_back();
assert_eq!(1,list.length);
}
}
We have successfully covered doubly linked list. We can count it as completion of circular linked list also because it's the same except the head and tail point to each other.
Alright, now it's time to move on to Implementing a Stack in Rust!