Skip to main content

/

DocsCode

Mojo struct

LinkedList

struct LinkedList[ElementType: Copyable & 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​

Implemented traits​

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

comptime members​

IteratorType​

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

The iterator type for this linked list.

Parameters​

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

Methods​

__init__​

__init__(out self)

Initialize an empty linked list.

Notes: Time Complexity: O(1).

__init__(out self, var *elements: ElementType, *, __list_literal__: Tuple[] = Tuple())

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 (Tuple): Tell Mojo to use this method for list literals.

__init__(out self, *, var elements: VariadicList[ElementType, elements.is_owned])

Construct a list from a VariadicList.

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

Args:

  • ​elements (VariadicList): The elements to add to the list.

__init__(out self, *, copy: Self)

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__​

__del__(deinit self)

Clean up the list by freeing all nodes.

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

__bool__​

__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.

__getitem__​

__getitem__[I: Indexer](ref self, idx: I) -> ref[self_is_mut] ElementType

Get the element at the specified index.

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

Parameters:

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

Args:

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

Returns:

ref: The element at the specified index.

__eq__​

__eq__(self, other: Self) -> Bool where conforms_to(ElementType, AnyType & ImplicitlyDestructible & 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__​

__contains__[_ElementType: Equatable & Copyable, //](self: LinkedList[_ElementType], value: _ElementType) -> Bool

Checks if the list contains value.

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

Parameters:

  • ​_ElementType (Equatable & Copyable): The list element type, used to conditionally enable the function.

Args:

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

Returns:

Bool: Whether the list contains value.

append​

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​

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​

reverse(mut self)

Reverse the order of elements in the list.

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

pop​

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.

pop[I: Indexer, //](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): 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​

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: The tail of the list, if it was present.

maybe_pop[I: Indexer, //](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): The type of index to use.

Args:

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

Returns:

Optional: The element, if it was found.

clear​

clear(mut self)

Removes all elements from the list.

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

insert​

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​

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​

count[_ElementType: Equatable & Copyable, //](self: LinkedList[_ElementType], elem: _ElementType) -> UInt

Count the occurrences of elem in the list.

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

Parameters:

  • ​_ElementType (Equatable & Copyable): The list element type, used to conditionally enable the function.

Args:

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

Returns:

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

__hash__​

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

Hash the elements of this list.

Args:

  • ​hasher (T): The hasher instance.

__len__​

__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__​

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

__reversed__​

__reversed__(self) -> _LinkedListIter[ElementType, 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: A reversed iterator of immutable references to the list elements.

write_to​

write_to(self, mut writer: T) where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Writable)

Write the list to the given writer.

Args:

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

write_repr_to​

write_repr_to(self, mut writer: T) where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Writable)

Write the repr representation of this LinkedList to a Writer.

Args:

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

View source

View source

Was this page helpful?

Models

Cookbook

Puzzles

Blog

Community

Contact