LinkedList

struct LinkedList[ElementType: Movable & ImplicitlyDestructible]

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 & ImplicitlyDestructible): The type of elements stored in the list. Must implement the Movable trait.

Implemented traits

AnyType, Boolable, Copyable, Defaultable, Equatable, Hashable, ImplicitlyDestructible, Iterable, IterableOwned, Movable, Sized, Writable

comptime members

IteratorOwnedType

comptime IteratorOwnedType = _LinkedListIterOwned[ElementType(ImplicitlyDestructible & Copyable & Movable)]

The owned iterator type for this linked list.

IteratorType

comptime IteratorType[iterable_mut: Bool, //, iterable_origin: Origin[mut=iterable_mut]] = _LinkedListIter[ElementType(ImplicitlyDestructible & Copyable & Movable), 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, AnyType & Copyable & Movable)

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.

__del__

def __del__(deinit self)

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, AnyType & 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, AnyType & 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.

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 & ImplicitlyDestructible, //](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 & ImplicitlyDestructible): 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 & ImplicitlyDestructible, //](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 & ImplicitlyDestructible): 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)

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 -len(self) <= idx <= len(self).
• ​elem (ElementType): The item to insert into the list.

Raises:

When given an out of bounds index.

extend

def extend(mut self, var 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) -> UInt where conforms_to(ElementType, AnyType & 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:

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

index

def index(self, value: ElementType) -> Int where conforms_to(ElementType, AnyType & 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, AnyType & 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] 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] ElementType: 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) -> Self.IteratorOwnedType

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:

Self.IteratorOwnedType: An iterator that owns the linked list's elements.

def __iter__(ref self) -> _LinkedListIter[ElementType(ImplicitlyDestructible & Copyable & Movable), 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(ImplicitlyDestructible & Copyable & Movable), origin_of(self)]: An iterator of immutable references to the list elements.

__reversed__

def __reversed__(ref self) -> _LinkedListIter[ElementType(ImplicitlyDestructible & Copyable & Movable), origin_of(self), False]

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(ImplicitlyDestructible & Copyable & Movable), 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, AnyType & 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, AnyType & Writable)

Write the repr representation of this LinkedList to a Writer.

Args:

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