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

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

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

1. Скопируйте данные (не указатель, а сами данные) из узла (i + 1) в узел (i), список будет выглядеть так: ... -> Узел (i-1) -> Узел (i + 1) -> Узел (i + 1) -> ...
2. Скопируйте NEXT второго узла (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;
}

Майк.

Допустим, список со структурой

A -> B -> C -> D

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

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

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

A -> B -> D

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

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

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

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

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

Невозможно.

Есть хаки для имитации удаления.

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

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

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

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

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

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

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 и используете более ранний подход, проблема внешних указателей все еще существует.

Первоначально предлагалось преобразовать:

a -> b -> c

to:

a ->, c

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

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

Может сделать софт-удаление? (т.е. установите флаг "удален" на узле). Вы можете очистить список позже, если вам нужно.

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

Как ты вообще оказался в этой ситуации? Что вы пытаетесь сделать, чтобы задать этот вопрос?

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

Данный

A -> B -> C -> D

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

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

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

Учитывая ниже связанный список

1 -> 2 -> 3 -> NULL

Указатель на узел 2 дается, скажем, «ptr».

У нас может быть псевдокод, который выглядит примерно так:

struct node* temp = ptr->next;
ptr->data = temp->data;
ptr->next = temp->next;
free(temp);

да, но вы не можете отсоединить его. Если вас не волнует испорченная память, продолжайте ;-)

Да, но ваш список будет поврежден после того, как вы его удалите.

В этом конкретном случае просмотрите список снова и получите этот указатель! В общем, если вы задаете этот вопрос, вероятно, существует ошибка в том, что вы делаете.

Чтобы перейти к предыдущему элементу списка, вам нужно будет пройти по списку с самого начала, пока вы не найдете запись с указателем next, указывающим на ваш текущий элемент. Тогда у вас будет указатель на каждый из элементов, которые вам нужно будет изменить, чтобы удалить текущий элемент из списка - просто установите previous->next на current->next, затем удалите current.

edit: Кимбо опередил меня меньше чем на минуту!

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

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

В общем, вы должны знать указатель на элемент, из которого вы только что пришли, и передавать его.

(Edit: Ick, за то время, которое мне потребовалось, чтобы напечатать полный ответ, три миллиарда человек охватили почти все моменты, которые я собирался упомянуть. :()

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

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

Вы ведь возглавляете список, верно? Вы просто пересекаете его.

Допустим, на ваш список указывает «голова» и узел, который нужно удалить, «del».

Псевдокод в стиле C (точки будут → в C):

prev = head
next = prev.link

while(next != null)
{
  if(next == del)
  {
    prev.link = next.link;
    free(del);
    del = null;
    return 0;
  }
  prev = next;
  next = next.link;
}

return 1;

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

a-b-c-d

скопируйте c в b и освободите c, чтобы результат был

a-c-d

struct node  
{
    int data;
    struct node *link;
 };

void populate(struct node **,int);

void delete(struct node **);

void printlist(struct node **);

void populate(struct node **n,int num)
{

    struct node *temp,*t;
    if(*n==NULL)
    {
        t=*n;
        t=malloc(sizeof(struct node));
        t->data=num;
        t->link=NULL;
        *n=t;
    }
    else
    {
        t=*n;
        temp=malloc(sizeof(struct node));
        while(t->link!=NULL)
            t=t->link;
        temp->data=num;
        temp->link=NULL;
        t->link=temp;
    }
}

void printlist(struct node **n)
{
    struct node *t;
    t=*n;
    if(t==NULL)
        printf("\nEmpty list");

    while(t!=NULL)
    {
        printf("\n%d",t->data);
        printf("\t%u address=",t);
        t=t->link;
    }
}


void delete(struct node **n)
{
    struct node *temp,*t;
    temp=*n;
    temp->data=temp->link->data;
    t=temp->link;
    temp->link=temp->link->link;
    free(t);
}    

int main()
{
    struct node *ty,*todelete;
    ty=NULL;
    populate(&ty,1);
    populate(&ty,2);
    populate(&ty,13);
    populate(&ty,14);
    populate(&ty,12);
    populate(&ty,19);

    printf("\nlist b4 delete\n");
    printlist(&ty);

    printf("\nEnter node pointer to delete the node====");
    scanf("%u",&todelete);
    delete(&todelete);

    printf("\nlist after delete\n");
    printlist(&ty);

    return 0;
}

Если у вас есть связанный список A -> B -> C -> D и указатель на узел B. Если вам нужно удалить этот узел, вы можете скопировать содержимое узла C в B, узла D в C и удалить D. Но мы не можем удалить узел как таковой в случае односвязного списка, поскольку, если мы это сделаем, узел A также будет потерян. Хотя мы можем вернуться к A в случае двусвязного списка.

Я прав?

Это кусок кода, который я собрал, который выполняет то, что просил OP, и может даже удалить последний элемент в списке (не самым элегантным способом, но он справляется). Написал, пока учился пользоваться связными списками. Надеюсь, это поможет.

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>

using namespace std;


struct node
{
    int nodeID;
    node *next;
};

void printList(node* p_nodeList, int removeID);
void removeNode(node* p_nodeList, int nodeID);
void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode);

node* addNewNode(node* p_nodeList, int id)
{
    node* p_node = new node;
    p_node->nodeID = id;
    p_node->next = p_nodeList;
    return p_node;
}

int main()
{
    node* p_nodeList = NULL;
    int nodeID = 1;
    int removeID;
    int listLength;
    cout << "Pick a list length: ";
    cin >> listLength;
    for (int i = 0; i < listLength; i++)
    {
        p_nodeList = addNewNode(p_nodeList, nodeID);
        nodeID++;
    }
    cout << "Pick a node from 1 to " << listLength << " to remove: ";
    cin >> removeID;
    while (removeID <= 0 || removeID > listLength)
    {
        if (removeID == 0)
        {
            return 0;
        }
        cout << "Please pick a number from 1 to " << listLength << ": ";
        cin >> removeID;
    }
    removeNode(p_nodeList, removeID);
    printList(p_nodeList, removeID);
}

void printList(node* p_nodeList, int removeID)
{
    node* p_currentNode = p_nodeList;
    if (p_currentNode != NULL)
    {
        p_currentNode = p_currentNode->next;
        printList(p_currentNode, removeID);
        if (removeID != 1)
        {
            if (p_nodeList->nodeID != 1)
            {
                cout << ", ";
            }

            cout << p_nodeList->nodeID;
        }
        else
        {
            if (p_nodeList->nodeID !=2)
            {
                cout << ", ";
            }
            cout << p_nodeList->nodeID;
        }
    }
}

void removeNode(node* p_nodeList, int nodeID)
{
    node* p_currentNode = p_nodeList;
    if (p_currentNode->nodeID == nodeID)
    {
        if(p_currentNode->next != NULL)
        {
            p_currentNode->nodeID = p_currentNode->next->nodeID;
            node* p_temp = p_currentNode->next->next;
            delete(p_currentNode->next);
            p_currentNode->next = p_temp;
        }
        else
        {
            delete(p_currentNode);
        }
    }
    else if(p_currentNode->next->next == NULL)
    {
        removeLastNode(p_currentNode->next, nodeID, p_currentNode);
    }
    else
    {
        removeNode(p_currentNode->next, nodeID);
    }
}

void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode)
{
    node* p_currentNode = p_nodeList;
    p_lastNode->next = NULL;
    delete (p_currentNode);
}