Skip to main content

/

Docs

Nightly

v24.6

Log in

Mojo struct

LinkedList

struct LinkedList[ElementType: CollectionElement]

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 (CollectionElement): The type of elements stored in the list. Must implement CollectionElement.

Implemented traits​

AnyType, Sized, UnknownDestructibility

Methods​

__init__​

__init__(out self)

Initialize an empty linked list.

Time Complexity: O(1)

__init__(out self, owned *elements: ElementType)

Initialize a linked list with the given elements.

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

Args:

  • ​*elements (ElementType): Variable number of elements to initialize the list with.

__init__(out self, *, owned elements: VariadicListMem[ElementType, origin])

Construct a list from a VariadicListMem.

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

Args:

  • ​elements (VariadicListMem[ElementType, origin]): The elements to add to the list.

__copyinit__​

__copyinit__(out self, other: Self)

Initialize this list as a copy of another list.

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

Args:

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

__moveinit__​

__moveinit__(out self, owned other: Self)

Initialize this list by moving elements from another list.

Time Complexity: O(1)

Args:

  • ​other (Self): The list to move elements from.

__del__​

__del__(owned self)

Clean up the list by freeing all nodes.

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

__bool__​

__bool__(self) -> Bool

Check if the list is non-empty.

Time Complexity: O(1)

Returns:

True if the list has elements, False otherwise.

__getitem__​

__getitem__(ref self, index: Int) -> ref [self] ElementType

Get the element at the specified index.

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

Args:

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

Returns:

The element at the specified index.

__setitem__​

__setitem__(mut self, index: Int, owned value: ElementType)

Set the element at the specified index.

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

Args:

  • ​index (Int): The index of the element to set.
  • ​value (ElementType): The new value to set.

__eq__​

__eq__[ElementType: EqualityComparableCollectionElement, //](self: LinkedList[ElementType], other: LinkedList[ElementType]) -> Bool

Checks if the two lists are equal.

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

Parameters:

  • ​ElementType (EqualityComparableCollectionElement): The list element type, used to conditionally enable the function.

Args:

  • ​other (LinkedList[ElementType]): The list to compare to.

Returns:

Whether the lists are equal.

__ne__​

__ne__[ElementType: EqualityComparableCollectionElement, //](self: LinkedList[ElementType], other: LinkedList[ElementType]) -> Bool

Checks if the two lists are not equal.

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

Parameters:

  • ​ElementType (EqualityComparableCollectionElement): The list element type, used to conditionally enable the function.

Args:

  • ​other (LinkedList[ElementType]): The list to compare to.

Returns:

Whether the lists are not equal.

__contains__​

__contains__[ElementType: EqualityComparableCollectionElement, //](self: LinkedList[ElementType], value: ElementType) -> Bool

Checks if the list contains value.

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

Parameters:

  • ​ElementType (EqualityComparableCollectionElement): The list element type, used to conditionally enable the function.

Args:

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

Returns:

Whether the list contains value.

append​

append(mut self, owned value: ElementType)

Add an element to the end of the list.

Time Complexity: O(1)

Args:

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

prepend​

prepend(mut self, owned value: ElementType)

Add an element to the beginning of the list.

Time Complexity: O(1)

Args:

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

reverse​

reverse(mut self)

Reverse the order of elements in the list.

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

pop​

pop(mut self) -> ElementType

Remove and return the last element of the list.

Time Complexity: O(1)

Returns:

The last element in the list.

pop[I: Indexer](mut self, owned i: I) -> ElementType

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

Time Complexity: O(1)

Parameters:

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

Args:

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

Returns:

Ownership of the indicated element.

maybe_pop​

maybe_pop(mut self) -> Optional[ElementType]

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

Time Complexity: O(1)

Returns:

The head of the list, if it was present.

maybe_pop[I: Indexer](mut self, owned i: I) -> Optional[ElementType]

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

Time Complexity: O(1)

Parameters:

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

Args:

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

Returns:

The element, if it was found.

clear​

clear(mut self)

Removes all elements from the list.

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

copy​

copy(self) -> Self

Create a deep copy of the list.

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

Returns:

A new list containing copies of all elements.

insert​

insert(mut self, owned idx: Int, owned elem: ElementType)

Insert an element elem into the list at index idx.

Time Complexity: O(1)

Args:

  • ​idx (Int): 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, owned other: Self)

Extends the list with another.

Time Complexity: O(1)

Args:

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

count​

count[ElementType: EqualityComparableCollectionElement](self: LinkedList[ElementType], elem: ElementType) -> UInt

Count the occurrences of elem in the list.

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

Parameters:

  • ​ElementType (EqualityComparableCollectionElement): The list element type, used to conditionally enable the function.

Args:

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

Returns:

The number of occurrences of elem in the list.

__len__​

__len__(self) -> Int

Get the number of elements in the list.

Time Complexity: O(1)

Returns:

The number of elements in the list.

__str__​

__str__[ElementType: WritableCollectionElement](self: LinkedList[ElementType]) -> String

Convert the list to its string representation.

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

Parameters:

  • ​ElementType (WritableCollectionElement): Used to conditionally enable this function when ElementType is Writable.

Returns:

String representation of the list.

__repr__​

__repr__[ElementType: WritableCollectionElement](self: LinkedList[ElementType]) -> String

Convert the list to its string representation.

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

Parameters:

  • ​ElementType (WritableCollectionElement): Used to conditionally enable this function when ElementType is Writable.

Returns:

String representation of the list.

write_to​

write_to[W: Writer, ElementType: WritableCollectionElement](self: LinkedList[ElementType], mut writer: W)

Write the list to the given writer.

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

Parameters:

  • ​W (Writer): The type of writer to write the list to.
  • ​ElementType (WritableCollectionElement): Used to conditionally enable this function when ElementType is Writable.

Args:

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