Удаление среднего узла из одного связанного списка, когда указатель на предыдущий узел недоступен

Question

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

Answer 1

Это определенно больше тест, чем реальная проблема. Однако, если нам позволят сделать некоторое предположение, оно может быть решено за O (1) раз. Чтобы сделать это, ограничения, на которые указывает список, должны быть копируемыми. Алгоритм выглядит следующим образом:

У нас есть список, похожий на: ... -> Узел (i-1) -> Узел (i) -> Узел (i + 1) -> ... и нам нужно удалить Узел (i).

1. Скопируйте данные (не указатель, а сами данные) из Узла (i + 1) в Узел (i), список будет выглядеть так: ) -> Узел (i + 1) -> ...
2. Скопируйте СЛЕДУЮЩИЙ второй Узел (i + 1) во временную переменную.
3. Теперь удалите второй узел (i + 1), для него не требуется указатель на предыдущий узел.

псевдокод:

void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}

Mike.

Answer 2

Предположим список со структурой

A -> B -> C -> D

Если у вас есть только указатель на B и вы хотите удалить его, вы можете сделать что-то вроде

tempList = B->next;
*B = *tempList;
free(tempList);

Список будет выглядеть как

A -> B -> D

но B будет хранить старое содержимое C, эффективно удаляя то, что было в B. Это не будет работать, если какой-то другой фрагмент кода содержит указатель на C. Это также не будет работать, если вы пытаетесь удалить узел D. Если вы хотите выполнить операцию такого типа, вам нужно построить список с фиктивным хвостовым узлом, который на самом деле не используется, так что вы гарантируете, что ни один полезный узел не будет иметь нулевого следующего указателя. Это также работает лучше для списков, где объем данных, хранящихся в узле, невелик. Структура типа

struct List { struct List *next; MyData *data; };

было бы хорошо, но тот, где это

struct HeavyList { struct HeavyList *next; char data[8192]; };

было бы немного обременительно.

Answer 3

Не возможно.

Есть хаки, имитирующие удаление.

Но ни один из них фактически не удалит узел, на который указывает указатель.

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

Answer 4

Я ценю изобретательность этого решения (удаление следующего узла), но оно не отвечает на вопрос проблемы. Если это реальное решение, правильный вопрос должен быть «удалить из связанного списка ЗНАЧЕНИЕ, содержащееся в узле, на котором указан указатель». Но, конечно же, правильный вопрос подсказывает вам решение. Задача, как она сформулирована, предназначена для того, чтобы сбить человека с толку (что на самом деле произошло со мной, особенно потому, что интервьюер даже не упомянул, что узел находится посередине).

Answer 5

Наилучшим подходом по-прежнему является копирование данных следующего узла в удаляемый узел, установка следующего указателя узла на следующий указатель следующего узла и удаление следующего узла.

Проблемы с внешними указателями, указывающими на удаляемый узел, в то время как значение true также будет сохраняться для следующего узла. Рассмотрим следующие связанные списки:

A-> B-> C-> D-> E-> F и G-> H-> I-> D-> E-> F

В случае, если вам необходимо удалить узел C (в первом связанном списке), в соответствии с упомянутым подходом вы удалите узел D после копирования содержимого в узел C. Это приведет к следующим спискам:

A-> B-> D-> E-> F и G-> H-> I-> висячий указатель.

В случае, если вы полностью удалите NODE C, результирующие списки будут:

A-> B-> D-> E-> F и G-> H-> I-> D-> E-> F.

Однако, если вы хотите удалить узел D и используете более ранний подход, проблема внешних указателей все еще остается.

Answer 6

Одним из подходов было бы вставить нуль для данных. Всякий раз, когда вы просматриваете список, вы отслеживаете предыдущий узел. Если вы найдете нулевые данные, вы исправите список и перейдете к следующему узлу.

Answer 7

Первоначальное предложение было преобразовать:

a -> b -> c

до:

a ->, c

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

Стандартным решением является рассмотрение других структур данных, например, списка пропусков.

Answer 8

Может быть, сделать мягкое удаление? (т.е. установите флажок «удален» на узле). При необходимости вы можете очистить список позже.

Answer 9

С учетом

A -> B -> C -> D

и указатель, скажем, на элемент B, вы удалили бы его на
1. освободить любую память, принадлежащую членам B
2. скопировать содержимое C в B (включая указатель «next»)
3. удалить весь элемент C

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

Теперь там, где был B, у вас есть C, и хранилище, которое раньше было C, освобождается.

Answer 10

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