LinkedList

struct LinkedList[ElementType: Movable]

A doubly-linked list implementation.

A doubly-linked list is a data structure where each element points to both the next and previous elements, allowing for efficient insertion and deletion at any position.

Parameters

• ​ElementType (Movable): The type of elements stored in the list. Must implement the Movable trait.

Implemented traits

AnyType, Boolable, Copyable (where conforms_to(ElementType, Copyable)), Defaultable, Deinitable (where conforms_to(ElementType, Deinitable)), Equatable (where conforms_to(ElementType, Equatable)), Hashable (where conforms_to(ElementType, Hashable)), Iterable, IterableOwned (where conforms_to(ElementType, Deinitable)), Movable, Sized, Writable (where conforms_to(ElementType, Writable))

comptime members

IteratorOwnedType

comptime IteratorOwnedType where conforms_to(ElementType, Deinitable) = _LinkedListIterOwned[ElementType(Deinitable & Movable)]

The owned iterator type for this linked list.

IteratorType

comptime IteratorType[iterable_mut: Bool, //, iterable_origin: Origin[mut=iterable_mut]] = _LinkedListIter[ElementType(Copyable), iterable_origin]

The iterator type for this linked list.

Parameters

• ​iterable_mut (Bool): Whether the iterable is mutable.
• ​iterable_origin (Origin[mut=iterable_mut]): The origin of the iterable.

Methods

__init__

def __init__(out self)

Initialize an empty linked list.

Notes: Time Complexity: O(1).

def __init__(out self, var *elements: ElementType, *, __list_literal__: NoneType = None)

Initialize a linked list with the given elements.

Notes: Time Complexity: O(n) in len(elements).

Args:

• ​*elements (ElementType): Variable number of elements to initialize the list with.
• ​list_literal (NoneType): Tell Mojo to use this method for list literals.

def __init__(out self, *, copy: Self) where conforms_to(ElementType, Copyable)

Initialize this list as a copy of another list.

Notes: Time Complexity: O(n) in len(elements).

Args:

• ​copy (Self): The list to copy from.

__deinit__

def __deinit__(deinit self) where conforms_to(ElementType, Deinitable)

Clean up the list by freeing all nodes.

Notes: Time Complexity: O(n) in len(self).

__bool__

def __bool__(self) -> Bool

Check if the list is non-empty.

Notes: Time Complexity: O(1).

Returns:

Bool: True if the list has elements, False otherwise.

__eq__

def __eq__(self, other: Self) -> Bool where conforms_to(ElementType, Equatable)

Checks if the two lists are equal.

Notes: Time Complexity: O(n) in min(len(self), len(other)) compares.

Args:

• ​other (Self): The list to compare to.

Returns:

Bool: Whether the lists are equal.

__contains__

def __contains__(self, value: ElementType) -> Bool where conforms_to(ElementType, Equatable)

Checks if the list contains value.

Notes: Time Complexity: O(n) in len(self) compares.

Args:

• ​value (ElementType): The value to search for in the list.

Returns:

Bool: Whether the list contains value.

deinit_with

def deinit_with(deinit self, deinit_func: T, /) where identical(T.ElementType, ElementType)

Consume the list, deinitializing each element with a closure.

Use this to tear down a LinkedList whose elements are not Deinitable.

Notes: Time Complexity: O(n) in len(self).

Args:

• ​deinit_func (T): A closure called once per element to deinitialize it.

append

def append(mut self, var value: ElementType)

Add an element to the end of the list.

Notes: Time Complexity: O(1).

Args:

• ​value (ElementType): The value to append.

prepend

def prepend(mut self, var value: ElementType)

Add an element to the beginning of the list.

Notes: Time Complexity: O(1).

Args:

• ​value (ElementType): The value to prepend.

reverse

def reverse(mut self)

Reverse the order of elements in the list.

Notes: Time Complexity: O(n) in len(self).

pop

def pop(mut self) -> ElementType

Remove and return the last element of the list.

Notes: Time Complexity: O(1).

Returns:

ElementType: The last element in the list.

Raises:

If the operation fails.

def pop[I: Indexer & Deinitable, //](mut self, var i: I) -> ElementType

Remove the ith element of the list, counting from the tail if given a negative index.

Notes: Time Complexity: O(n) in len(self).

Parameters:

• ​I (Indexer & Deinitable): The type of index to use.

Args:

• ​i (I): The index of the element to get.

Returns:

ElementType: Ownership of the indicated element.

Raises:

If the operation fails.

maybe_pop

def maybe_pop(mut self) -> Optional[ElementType]

Removes the tail of the list and returns it, if it exists.

Notes: Time Complexity: O(1).

Returns:

Optional[ElementType]: The tail of the list, if it was present.

def maybe_pop[I: Indexer & Deinitable, //](mut self, var i: I) -> Optional[ElementType]

Remove the ith element of the list, counting from the tail if given a negative index.

Notes: Time Complexity: O(n) in len(self).

Parameters:

• ​I (Indexer & Deinitable): The type of index to use.

Args:

• ​i (I): The index of the element to get.

Returns:

Optional[ElementType]: The element, if it was found.

clear

def clear(mut self) where conforms_to(ElementType, Deinitable)

Removes all elements from the list.

Notes: Time Complexity: O(n) in len(self).

insert

def insert[I: Indexer](mut self, idx: I, var elem: ElementType)

Insert an element elem into the list at index idx.

Notes: Time Complexity: O(n) in len(self).

Parameters:

• ​I (Indexer): The type of index to use.

Args:

• ​idx (I): The index to insert elem at. Must be in the range [0, len(self)].
• ​elem (ElementType): The item to insert into the list.

extend

def extend(mut self, deinit other: Self)

Extends the list with another.

Notes: Time Complexity: O(1).

Args:

• ​other (Self): The list to append to this one.

count

def count(self, elem: ElementType) -> Int where conforms_to(ElementType, Equatable)

Count the occurrences of elem in the list.

Notes: Time Complexity: O(n) in len(self) compares.

Args:

• ​elem (ElementType): The element to search for.

Returns:

Int: The number of occurrences of elem in the list.

index

def index(self, value: ElementType) -> Int where conforms_to(ElementType, Equatable)

Returns the index of the first occurrence of a value in the list.

Notes: Unlike Python's list.index(), this method does not accept start/stop parameters.

Time Complexity: O(n) in len(self).

Args:

• ​value (ElementType): The value to search for.

Returns:

Int: The index of the first occurrence of the value in the list.

Raises:

ValueError: If the value is not found in the list.

__hash__

def __hash__(self, mut hasher: T) where conforms_to(ElementType, Hashable)

Hash the elements of this list.

Args:

• ​hasher (T): The hasher instance.

get_nth

def get_nth[I: Indexer](ref self, idx: I) -> ref[self_is_mut["element"]] ElementType

Get the element at the specified index.

Notes: Time Complexity: O(n/2) in len(self).

Parameters:

• ​I (Indexer): The type of index to use.

Args:

• ​idx (I): The index of the element to get.

Returns:

ref[self_is_mut["element"]] ElementType: A reference to the element at the specified index.

__len__

def __len__(self) -> Int

Get the number of elements in the list.

Notes: Time Complexity: O(1).

Returns:

Int: The number of elements in the list.

__iter__

def __iter__(var self) -> _LinkedListIterOwned[ElementType(Deinitable & Movable)] where conforms_to(ElementType, Deinitable)

Consume the linked list and return an iterator over its elements.

Notes: Time Complexity:

• O(1) for iterator construction.
• O(n) in len(self) for a complete iteration of the list.

Returns:

_LinkedListIterOwned[ElementType(Deinitable & Movable)]: An iterator that owns the linked list's elements.

def __iter__(ref self) -> _LinkedListIter[ElementType(Copyable), origin_of(self)]

Iterate over elements of the list, returning immutable references.

Notes: Time Complexity:

• O(1) for iterator construction.
• O(n) in len(self) for a complete iteration of the list.

Returns:

_LinkedListIter[ElementType(Copyable), origin_of(self)]: An iterator of immutable references to the list elements.

__reversed__

def __reversed__(ref self) -> _LinkedListIter[ElementType(Copyable), origin_of(self), False] where conforms_to(ElementType, Copyable)

Iterate backwards over the list, returning immutable references.

Notes: Time Complexity:

• O(1) for iterator construction.
• O(n) in len(self) for a complete iteration of the list.

Returns:

_LinkedListIter[ElementType(Copyable), origin_of(self), False]: A reversed iterator of immutable references to the list elements.

write_to

def write_to(self, mut writer: T) where conforms_to(ElementType, Writable)

Write the list to the given writer.

Args:

• ​writer (T): The writer to write the list to.

write_repr_to

def write_repr_to(self, mut writer: T) where conforms_to(ElementType, Writable)

Write the repr representation of this LinkedList to a Writer.

Args:

• ​writer (T): The writer to write to.