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

Проблема предполагает, что удаляемый узел известен и доступен указатель на этот узел.

Чтобы удалить узел и соединить предыдущий и следующий узлы вместе, вам нужно знать их указатели. В двусвязном списке оба указателя доступны в удаляемом узле. Временная сложность в этом случае постоянна, т. Е. O (1).

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

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

На самом деле удаление в односвязных списках также может быть реализовано в O (1).

Дан односвязный список со следующим состоянием:

SinglyLinkedList:
   Node 1 -> Node 2
   Node 2 -> Node 3
   Node 3 -> Node 4
   Node 4 -> None

   Head = Node 1

Мы можем реализовать delete Node 2 таким образом:

Node 2 Value <- Node 3 Value
Node 2 -> Node 4

Здесь мы заменяем значение Node 2 значением его следующего узла (Node 3) и устанавливаем его указатель следующего значения на следующий указатель значения Node 3 (Node 4), пропуская теперь фактически "дубликат" Node 3. Таким образом, обход не требуется.

Потому что ты не можешь оглянуться назад...

Это связано со сложностью исправления следующего указателя в узле, предшествующем удаляемому.

Вставка и удаление в известной позиции — O(1). Однако найти эту позицию можно за O(n), если только она не находится в начале или в конце списка.

Когда мы говорим о сложности вставки и удаления, мы обычно предполагаем, что уже знаем, где это произойдет.

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

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

Это O (1), если у вас есть адрес узла, который необходимо удалить, потому что у вас есть ссылка на предыдущий узел и ссылка на следующий узел. Поскольку у вас есть все необходимые ссылки, просто удалите «интересующий узел» из списка, переупорядочив ссылки, а затем освободив его.

Но в одном связанном списке вам нужно пройти от головы, чтобы получить его предыдущий и следующий адрес, не имеет значения, есть ли у вас адрес узла, который нужно удалить, или положение узла (например, 1-й, 2-й, 10-й и т. д., .) Быть удаленным .

Предположим, есть связанный список от 1 до 10, и вам нужно удалить узел 5, расположение которого вам дано.

1 -> 2 -> 3 -> 4 -> 5-> 6-> 7-> 8 -> 9 -> 10

Вам нужно будет соединить следующий указатель 4 с 6, чтобы удалить 5.

1. Двусвязный список. Вы можете использовать предыдущий указатель на 5, чтобы перейти к 4. Затем вы можете сделать

4->next = 5->next;

or

Node* temp = givenNode->prev;
temp->next = givenNode->next;

Временная сложность = O(1)

2. односвязный список Поскольку у вас нет предыдущего указателя в односвязном списке, вы не можете вернуться назад, поэтому вам придется пройти по списку с головы

Node* temp = head;
while(temp->next != givenNode)
{
  temp = temp->next;
}
temp->next = givenNode->next;

Временная сложность = O (N)