Удаление в связанном списке

Question

Учитывая только указатель на удаляемый узел, как удалить узел в связанном списке ...?

Answer 1

Вопрос слишком неоднозначный, и, вероятно, этот способ по какой-либо причине (например, чтобы развернуть беседу вместо проверки фактического знания структуры данных). Вероятно, они ожидают, что вы спросите: «Является ли это дважды связанным списком или отдельным списком?» Если это вдвойне связанный список, его простой вопрос:

curr->prev->next = curr->next; 
curr->next->prev = curr->prev; 
delete curr; 

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

loop from head to end until test->next == curr 
test->next = curr->next; 
delete curr; 

В качестве альтернативы, если вы можете изменить список (без головного узла):

temp = curr->next; 
curr->data = temp->data; 
curr->next = temp->next; 
delete temp; 

Answer 2

Я думаю, что это почти невозможно в односвязных списках, если у вас нет указателя на список. У вас всегда должен быть указатель на указатель связанного списка.

Answer 3

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

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

Answer 4

Ну, это всего лишь трюк.

curr Предполагая, что это адрес, указанный после будет код псевдо:

to_delete = curr->next 
curr->data = to_delete->data 
curr->next = to_delete->next 
delete to_delete 

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

Answer 5

You have a pointer to that node (say, node N). Meaning, you have access on that node. 
If that node has pointer to it's front node and it's back node, then simply point the back node to the front node. And the front node to the back of your node N. 

To illustrate: 
step 1: 
---> [ node ] ---> [ node ] ---> [ node ] ---> 
<--- [ M ] <--- [ N ] <--- [ O ] <--- etc... 

step 2: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <--- [node N] <--- [ O ] <--- etc... 

step 3: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <----------------- [ O ] <--- etc... 

            [ node ] ---> (still points to node O) 
     (still points to node M) <--- [ N ] 

step 4: 
just point Node N to NULL 
            [ node ] ---> NULL 
          NULL <--- [ N ] 

result: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <----------------- [ O ] <--- etc... 

Answer 6

У меня есть решение, если это не хвост.

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

Предполагая, что у меня есть

struct Node 
{ 
    T value; 
    Node * next; 
}; 

решение было бы что-то вроде:

void freeNode(Node * node) 
{ 
    Node * next = node->next; 
    if(next) 
    { 
     node->value = next->value; 
     node->next = next->next; 
     free(next); 
    } 
    // else I'm stuck! 
} 

выше рода псевдо смеси C и C++.

Если у нас есть хвост и предполагается, что хвост указан узлом-> next == NULL, я не могу сделать предыдущий узел в хвост, поэтому я не могу решить.