Linked List

Source code: src/pydsadoc/_linear/linked.py

class LinkedList(*args, **kwargs)

Linear list implemented with linked list.

__str__() → str

Implement built-in function print().

Treaverse the linked list. The time complexity is \(O(n)\).

append(obj: int | None, /) → None

Append object to the end of the list.

Time complexity is \(O(n).\)

index(value: int | None, start: int = 0, stop: int = 9223372036854775807, /) → int

Return first index of the value.

At or after index start and before index stop. Time complexity is \(O(n)\).

insert(index: int, obj: int | None, /) → None

Insert object before index.

Time complexity is \(O(n)\).

pop(index: int = -1, /) → Node

Remove and return node at index (default last).

Time complexity is \(O(n)\).

remove(value: int | None, /) → None

Remove first occurrence of value.

Time complexity is \(O(n)\).

Stack

A stack can be implemented with a linked list LinkedList and its methods LinkedList.insert() and LinkedList.pop() as described above. Specifically, the stack.insert(0, objcet) and stack.pop(0) operations.

Notably, in this case, the time complexity of these two methods is \(O(1)\).

Queue

A queue can be implemented with a linked list LinkedList and its methods LinkedList.append() and LinkedList.pop() as described above. Specifically, the queue.append(object) and queue.pop(0) operations.

Notably, in this case, the time complexity of the method LinkedList.pop() is \(O(1)\), but of the method LinkedList.append() is \(O(n)\).