Ferum's implementation of a doubly linked list. Values stored in the list should be cheap to copy. Duplicate values are supported.
This list should be used for values that are cheap to copy. For a list that stores by moving values, see (ref_linked_list)[/]
Operation
Worst Case Time Complexity
Where D is the number of duplicates of that particular value.
Each value is stored internally in a table with a unique key pointing to that value. The key is generated sequentially using a u128 counter. So the maximum number of values that can be added to the list is MAX_U128 (340282366920938463463374607431768211455).
Quick Example
use ferum_std::linked_list::{Self, List};
// Create a list with u128 values.
let list = linked_list::new<u128>();
// Add values
linked_list::add(&mut list, 100);
linked_list::add(&mut list, 50);
linked_list::add(&mut list, 20);
linked_list::add(&mut list, 200);
linked_list::add(&mut list, 100); // Duplicate
print_list(&list) // 100 <-> 50 <-> 20 <-> 200 <-> 100
// Iterate through the list, left to right.
let iterator = iterator(&list);
while (linked_list::has_next(&iterator)) {
let value = linked_list::get_next(&list, &mut iterator);
};
// Get length of list.
linked_list::length(&list) // == 4
// Check if list contains value.
linked_list::contains(&list, 100) // true
linked_list::contains(&list, 300) // false
// Remove last
linked_list::remove_last(&list);
print_list(&list) // 100 <-> 50 <-> 20 <-> 200
// Remove first
linked_list::remove_first(&list);
print_list(&list) // 50 <-> 20 <-> 200
Resource LinkedList
Struct representing the linked list.
struct LinkedList<V: copy, drop, store> has store, key
Struct ListPosition
Used to represent a position within a doubly linked list during iteration.
struct ListPosition<V: copy, drop, store> has copy, drop, store
Constants
DUPLICATE_KEY
Thrown when a duplicate key is added to the list.
const DUPLICATE_KEY: u64 = 2;
EMPTY_LIST
Thrown when a trying to perform an operation that requires a list to have elements but it doesn't.
const EMPTY_LIST: u64 = 3;
KEY_NOT_FOUND
Thrown when the key for a given node is not found.
const KEY_NOT_FOUND: u64 = 1;
MUST_HAVE_NEXT_VALUE
Thrown when attempting to iterate beyond the limit of the linked list.
const MUST_HAVE_NEXT_VALUE: u64 = 5;
VALUE_NOT_FOUND
Thrown when a value being searched for is not found.
const VALUE_NOT_FOUND: u64 = 4;
Functions
Function new
Initialize a new list.
public fun new<V: copy, drop, store>(): linked_list::LinkedList<V>
Function singleton
Creates a linked list with a single element.
public fun singleton<V: copy, drop, store>(val: V): linked_list::LinkedList<V>
Function add
Add a value to the list.
public fun add<V: copy, drop, store>(list: &mut linked_list::LinkedList<V>, value: V)
Function insert_at
Inserts a value to the given index.
public fun insert_at<V: copy, drop, store>(list: &mut linked_list::LinkedList<V>, value: V, idx: u128)
Function remove
Removes a value from the list. If there are duplicates, a random occurence is removed.
public fun remove<V: copy, drop, store>(list: &mut linked_list::LinkedList<V>, value: V)
Function remove_first
Remove the first element of the list. If the list is empty, will throw an error.
public fun remove_first<V: copy, drop, store>(list: &mut linked_list::LinkedList<V>)
Function remove_last
Remove the last element of the list. If the list is empty, will throw an error.
public fun remove_last<V: copy, drop, store>(list: &mut linked_list::LinkedList<V>)
Function borrow_first
Get a reference to the first element of the list.
public fun borrow_first<V: copy, drop, store>(list: &linked_list::LinkedList<V>): &V
Function borrow_last
Get a reference to the last element of the list.
public fun borrow_last<V: copy, drop, store>(list: &linked_list::LinkedList<V>): &V
Function contains
Returns true is the element is in the list.
public fun contains<V: copy, drop, store>(list: &linked_list::LinkedList<V>, value: V): bool
Function length
Returns the length of the list.
public fun length<V: copy, drop, store>(list: &linked_list::LinkedList<V>): u128
Function is_empty
Returns true if empty.
public fun is_empty<V: copy, drop, store>(list: &linked_list::LinkedList<V>): bool
Function as_vector
Returns the list as a vector.
public fun as_vector<V: copy, drop, store>(list: &linked_list::LinkedList<V>): vector<V>
Function iterator
Returns a left to right iterator. First time you call next(...) will return the first value. Updating the list while iterating will abort.
public fun iterator<V: copy, drop, store>(list: &linked_list::LinkedList<V>): linked_list::ListPosition<V>
Function has_next
Returns true if there is another element left in the iterator.
public fun has_next<V: copy, drop, store>(position: &linked_list::ListPosition<V>): bool
Function get_next
Returns the next value, and updates the current position.
public fun get_next<V: copy, drop, store>(list: &linked_list::LinkedList<V>, position: &mut linked_list::ListPosition<V>): V
Function peek_next
Returns a reference to the next value in the iterator. The iterator position is not updated.
public fun peek_next<V: copy, drop, store>(list: &linked_list::LinkedList<V>, position: &linked_list::ListPosition<V>): &V
Function drop
Empties out the list and drops all values.
public fun drop<V: copy, drop, store>(list: linked_list::LinkedList<V>)