Функция возвращает значение элемента с номером index в односвязном списке. Определите время выполнения в худшем случае, где n — длина списка.
Чтение по индексу из связанного списка
Код
class Node:
def __init__(self, value: int, next: "Node | None" = None) -> None:
self.value = value
self.next = next
def get(head: Node, index: int) -> int:
node = head
for _ in range(index):
node = node.next
return node.valueКакое время выполнения?
Ответ: O(n)
В связанном списке узел знает только адрес следующего, поэтому к элементу с номером index приходится идти от головы шаг за шагом. В худшем случае (последний элемент) это n − 1 шагов — O(n). У массива элементы лежат в памяти подряд, и чтение по индексу занимает O(1).
- Подсказка 1
Можно ли сразу «прыгнуть» к узлу с номером index, как в массиве?
- Подсказка 2
Худший случай — последний элемент списка.