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, ImplicitlyDestructible, Iterable, Movable, Sized

comptime members​

__copyinit__is_trivial​

comptime __copyinit__is_trivial = False

__del__is_trivial​

comptime __del__is_trivial = False

__moveinit__is_trivial​

comptime __moveinit__is_trivial = True

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: VariadicListMem[ElementType, is_owned])

Construct a list from a VariadicListMem.

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

Args:

__copyinit__​

__copyinit__(out self, other: Self)

Initialize this list as a copy of another list.

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

Args:

  • ​other (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] 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__[_ElementType: Equatable & Copyable, //](self: LinkedList[_ElementType], other: LinkedList[_ElementType]) -> Bool

Checks if the two lists are equal.

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

Parameters:

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

Args:

Returns:

Bool: Whether the lists are equal.

__ne__​

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

Checks if the two lists are not equal.

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

Parameters:

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

Args:

Returns:

Bool: Whether the lists are not 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.

__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, self_is_origin]

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

__str__​

__str__[_ElementType: Copyable & ImplicitlyDestructible & Writable](self: LinkedList[_ElementType]) -> String

Convert the list to its string representation.

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

Parameters:

Returns:

String: String representation of the list.

__repr__​

__repr__[_ElementType: Copyable & ImplicitlyDestructible & Writable](self: LinkedList[_ElementType]) -> String

Convert the list to its string representation.

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

Parameters:

Returns:

String: String representation of the list.

write_to​

write_to[_ElementType: Copyable & ImplicitlyDestructible & Writable](self: LinkedList[_ElementType], mut writer: T)

Write the list to the given writer.

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

Parameters:

Args:

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

View source

View source

Was this page helpful?

Models

Cookbook

Puzzles

Blog

Community

Contact