Временная сложность в отдельном списке ссылок

Question

Я изучаю структуру данных: список ссылок по отдельности.

Веб-сайт говорит, что список, связанный по отдельности, имеет сложность вложения и удаления по времени O(1). Я что-то упускаю?

website link

Я делаю это в C++, и у меня есть только root pointer. Если я хочу вставить в конец, то мне нужно пройти весь путь назад, что означает O(n).

Answer 1

Объяснение этому состоит в том, что большая нотация O в связанной таблице относится к самой реализации функции, не включая обход списка, чтобы найти предыдущий ссылочный узел в списке.

Если вы по ссылке на статью в википедии на Singly-LinkedList implementation становится более ясным:

function insertAfter(Node node, Node newNode) 
function removeAfter(Node node)  

Вышеуказанные сигнатуры функции уже принимают узел предшественника в качестве аргумента (то же для других вариантов неявно).

Поиск предшественника - это другая операция и может быть O (n) или другой временной сложностью.

Answer 2

Вы пропустили интерфейс в двух местах:

1. станд :: список :: вставка()/STD: список :: УДАЛИТЬ() нужен итератор на элемент, где вставить или удалить. Это означает, что у вас нет поиска, но только изменить два указателя в элементах в списке, что является постоянной сложностью.

2. Вставка в конце списка может быть выполнена с помощью push_back. Стандарт требует, чтобы это также было O (1). Это означает, что если у вас есть std :: list, он будет хранить первый и последний элемент.

EDIT: Извините, вы встретите std :: forward_list. Точка 1 выполняется также для этого, даже если имена вставляются вставки и стираются после. Точки 2 нет, вам нужно перебирать до конца списка.

Answer 3

Я делаю это на C++, и у меня есть только указатель корня. Если я хочу вставить в конец, то мне нужно пройти весь путь назад, что означает O (n).

Это две операции, вы первый поиск O (N) списка для данной позиции, то вставки O (1) элемента в список.

В одном связанном списке, то операция вставки состоит из:

• переменного указатель предыдущего элемента

• объект обертывание в структуру данных, и установив его указатель на следующий элемент

Оба являются неизменными по размеру списка.

С другой стороны, возьмите, например, куча структура. Для вставки каждого элемента требуются операции O (log (n)) для сохранения его структуры. Структуры деревьев имеют аналогичные механизмы, которые будут выполняться при вставке и зависят от текущего размера дерева.