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

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

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

1. Скопируйте данные (не указатель, сами данные) из Node (i + 1) в Node (i), список будет выглядеть так: … -> Node (i-1) -> Node (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. Это не сработает, если какой-либо другой fragment кода содержит указатель на C. Он также не будет работать, если вы пытаетесь удалить узел D. Если вы хотите выполнить такую ​​операцию, вам нужно будет создать список с фиктивным хвостовым узлом, который на самом деле не используется, поэтому вы гарантируете, что ни один из полезных узлов не будет иметь следующий указатель NULL. Это также лучше работает для списков, где количество данных, хранящихся в узле, невелико. Подобная структура

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

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

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

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

Невозможно.

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

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

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

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

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

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

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

a -> b -> c

чтобы:

a ->, c

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

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

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

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

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

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

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

Данный

A -> B -> C -> D

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

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

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

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

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

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

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

Редактировать: Кимбо избил меня к ней менее чем за минуту!

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

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

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

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

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

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

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

Предположим, что на ваш список указана «голова», а узел – «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 затем попросит пользователя указать указатель на удаляемый узел. он будет распечатывать список после удаления. Он делает то же самое, что и при копировании узла после удаляемого узла, над удаляемым узлом, а затем удаляет следующий узел узла, который нужно удалить. т.е.

ABCD

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

ДСА

 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; } в 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; } в 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, disconnect 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; } } 

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

Я прав?

 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, disconect its next*/ list->next=list->next->next; } list=list->next; } } 

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

 #include  #include  #include  #include  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); } 

 Void deleteMidddle(Node* head) { Node* slow_ptr = head; Node* fast_ptr = head; Node* tmp = head; while(slow_ptr->next != NULL && fast_ptr->next != NULL) { tmp = slow_ptr; slow_ptr = slow_ptr->next; fast_ptr = fast_ptr->next->next; } tmp->next = slow_ptr->next; free(slow_ptr); enter code here }