Crate cdl_list_rs

This crate implements a Circular Doubly Linked List in Rust using Rc<T> and RefCell<T>.

Use this crate if you really like interior mutability or dislike the many unsafe blocks used in other implementations! Of course, interior mutability introduces potential runtime panics of its own, but those should not be present currently.

Usage

Create a list using cdl_list::CdlList::new():

use cdl_list_rs::cdl_list::CdlList;
 
let mut list : CdlList<u32> = CdlList::new();

The list must be mutable to add any elements to it. Elements may be added to the head or tail of the list using cdl_list::CdlList::push_front() or cdl_list::CdlList::push_back().

// Where A <══> B = A ⇄ B
list.push_front(1); // list = ╔══> 1 <══╗
                    //        ╚═════════╝
 
list.push_back(2);  // list = ╔══> 1 <══> 2 <══╗
                    //        ╚════════════════╝
 
list.push_front(3); // list = ╔══> 3 <══> 1 <══> 2 <══╗
                    //        ╚═══════════════════════╝

Additionally, you may use cdl_list::CdlList::insert_at() to insert an element into the list at a specific index.

list.insert_at(2, 4); // list = ╔══> 3 <══> 1 <══> 4 <══> 2 <══╗
                      //        ╚══════════════════════════════╝
 
assert_eq!(list.size(), 4);
assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.pop_back(), Some(4));
assert_eq!(list.pop_back(), Some(1));
assert_eq!(list.pop_back(), Some(3));

To see which item is at the head or tail of the list, use cdl_list::CdlList::peek_front() or cdl_list::CdlList::peek_back(). This optionally returns a Ref<T>, which can be dereferenced using * or clone(). This creates a copy of the value and cannot modify the list’s contents!

list.push_front(1);
list.push_back(2);
list.push_front(3);
let head_val = *list.peek_front().unwrap();        // head_val = 3
let tail_val = list.peek_back().unwrap().clone();  // tail_val = 2

To remove an item from the list, you can currently use cdl_list::CdlList::pop_front() or cdl_list::CdlList::pop_back(). This gives you ownership of the value at the head or tail of the list respectively and removes it from the list, adjusting the list’s pointers appropriately. Like peek, this returns None if the list is empty.

let head = list.pop_front(); // head = Some(3)
                             // list = ╔══> 1 <══> 2 <══╗
                             //        ╚════════════════╝
 
let tail = list.pop_back();  // tail = Some(2)
                             // list = ╔══> 1 <══╗
                             //        ╚═════════╝
 
let last = list.pop_front(); // last = Some(1)
                             // list is empty
 
let empty = list.pop_back(); // empty = None

Additionally, you may use cdl_list::CdlList::remove_at() to remove an element from the list at a specific index.

list.push_front(1);
list.push_back(2);
list.push_front(3);
 
// List:  3, 1, 2
// Index: 0, 1, 2
 
assert_eq!(list.remove_at(1), Some(1));

Modules

• cdl_list
  A circular doubly linked list is a series of nodes where each node has a reference to the next and previous node in the list. By being circular, the head and tail of the list point to each other, making the graph cyclic. Below is an example of a small list: