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

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

у Нас есть сходство со списка:...-> Узел (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;
}

Mike.

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

Скажем, что на Ваш список указывают "голова" и узел для удаления его "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;

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

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

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

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

В целом, необходимо знать указатель на объект, из которого Вы просто произошли, и необходимо раздавать это.

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

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

редактирование: Kimbo побеждают меня к нему меньше чем на минуту!

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

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

Учитывая

А-> B-> C-> D

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

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

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

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

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

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

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

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

-> b-> c

к:

->, c

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

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

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

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

Давайте примем список со структурой

А-> B-> C-> D

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

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

, список будет тогда похож

А-> B-> D

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

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

была бы в порядке, но тот, где это

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

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

Рассмотрение ниже связанного списка

1-> 2-> 3-> ПУСТОЙ УКАЗАТЕЛЬ

Подсказка на узел 2 дана, говорят "ptr".

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

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

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

abcd

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

acd

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;
}

void delself(list *list)
{
   /*if we got a pointer to itself how to remove it...*/
   int n;

   printf("Enter the num:");

   scanf("%d",&n);

   while(list->next!=NULL)
   {
       if(list->number==n) /*now pointer in node itself*/
       {
           list->number=list->next->number;
           /*copy all(name,rollnum,mark..) data of next to current, disconect its next*/
           list->next=list->next->next;
       }
       list=list->next;
   }
}

void delself(list *list)
{
   /*if we got a pointer to itself how to remove it...*/
   int n;

   printf("Enter the num:");
   scanf("%d",&n);

   while(list->next!=NULL)
   {
      if(list->number==n) /*now pointer in node itself*/
      {
         list->number=list->next->number;   /*copy all(name,rollnum,mark..)
                             data of next to current, disconnect its next*/
         list->next=list->next->next;
      }
      list=list->next;
   }
}