LinkedList

ferum_std::linked_list

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
Insertion of value to tail	O(D)
Deletion of value	O(1)
Deletion of value at head	O(D)
Deletion of value at tail	O(D)
Contains value	O(1)

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>)