이전 노드에 대한 포인터를 사용할 수 없는 경우 단일 연결 목록에서 중간 노드 삭제
이전 노드에 대한 포인터가 아니라 삭제할 노드에 대한 포인터만 있는 경우 단일 연결 목록에서 중간 노드를 삭제할 수 있습니까?삭제 후 이전 노드가 삭제된 노드 옆의 노드를 가리켜야 합니다.
그것은 확실히 실제 문제라기보다는 퀴즈에 가깝습니다.하지만, 우리가 어떤 가정을 할 수 있다면, 그것은 O(1)시간 안에 해결될 수 있습니다.이 작업을 수행하려면 목록이 가리키는 스트럭처가 복사 가능해야 합니다.알고리즘은 다음과 같습니다.
... -> 노드(i-1) -> 노드(i) -> 노드(i+1) ->와 같은 목록이 있으며 노드(i)를 삭제해야 합니다.
- 노드(i+1)에서 노드(i)로 데이터(포인터가 아니라 데이터 자체)를 복사합니다. 목록은 ... -> 노드(i-1) -> 노드(i+1) -> 노드(i+1) -> ...와 같습니다.
- 두 번째 노드(i+1)의 NEXT를 임시 변수로 복사합니다.
- 이제 두 번째 노드(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]; };
조금 부담스러울 것 같습니다.
불가능합니다.
삭제를 모방하기 위한 해킹이 있습니다.
그러나 포인터가 가리키는 노드는 실제로 삭제되지 않습니다.
다음 노드를 삭제하고 해당 내용을 삭제할 실제 노드에 복사하는 일반적인 솔루션은 목록의 노드를 가리키는 외부 포인터가 있으면 부작용이 발생하며, 이 경우 다음 노드를 가리키는 외부 포인터가 달랑거립니다.
이 솔루션의 독창성(다음 노드 삭제)은 높이 평가하지만 문제의 질문에 답하지는 않습니다.이것이 실제 솔루션인 경우 올바른 질문은 "연결된 목록에서 포인터가 지정된 노드에 포함된 VALUE 삭제"입니다.하지만 물론, 정답은 여러분에게 해결책에 대한 힌트를 줍니다.공식화된 문제는 (특히 인터뷰 진행자가 노드가 중간에 있다는 것을 언급하지 않았기 때문에) 사람을 혼란스럽게 하기 위한 것입니다.
한 가지 접근 방식은 데이터에 대해 null을 삽입하는 것입니다.목록을 통과할 때마다 이전 노드를 추적합니다.null 데이터를 찾으면 목록을 수정하고 다음 노드로 이동합니다.
가장 좋은 방법은 삭제할 노드에 다음 노드의 데이터를 복사하고 노드의 다음 포인터를 다음 노드의 다음 포인터로 설정한 다음 다음 노드를 삭제하는 것입니다.
삭제할 노드를 가리키는 외부 포인터 문제는 사실이지만 다음 노드에도 적용됩니다.다음 링크된 목록을 고려하십시오.
A->B->C->D->E->F와 G->H->I->D->E->F
노드 C를 삭제해야 하는 경우(첫 번째 링크 목록에서), 앞서 언급한 접근 방식에 따라 노드 C에 내용을 복사한 후 노드 D를 삭제합니다.그러면 다음과 같은 목록이 나타납니다.
A->B->D->E->F 및 G->H->I->Dangling 포인터
NODE C를 완전히 삭제하는 경우 결과 목록은 다음과 같습니다.
A->B->D->E->F와 G->H->I->D->E->F.
그러나 노드 D를 삭제하고 이전 접근 방식을 사용한다면 외부 포인터 문제는 여전히 남아 있습니다.
초기 제안은 다음과 같습니다.
a -> b -> c
대상:
a ->, c
노드의 주소에서 다음 노드의 주소로 지도와 같은 정보를 유지하면 다음 번에 목록을 이동하기 위해 체인을 수정할 수 있습니다.다음 순회 전에 여러 항목을 삭제해야 하는 경우 삭제 순서(예: 변경 목록)를 추적해야 합니다.
표준 솔루션은 건너뛰기 목록과 같은 다른 데이터 구조를 고려하는 것입니다.
소프트 삭제를 할까요?(즉, 노드에 "삭제" 플래그 설정) 필요한 경우 나중에 목록을 정리할 수 있습니다.
목록의 이동성을 유지하려면 그렇지 않습니다.다음 노드에 연결하려면 이전 노드를 업데이트해야 합니다.
그런데 어쩌다가 이런 상황이 된 거죠?당신은 무엇을 하려고 하는 것이 당신을 이 질문을 하게 합니까?
이전 노드를 찾으려면 목록 아래로 이동해야 합니다.그러면 일반적으로 O(n**2)가 삭제됩니다.사용자가 삭제를 수행하는 유일한 코드인 경우 이전 노드를 캐시하고 거기서 검색을 시작하여 실제로 더 나은 작업을 수행할 수 있지만, 이 작업이 도움이 되는지 여부는 삭제 패턴에 따라 다릅니다.
정해진
A -> B -> C -> D
예를 들어, B 항목에 대한 포인터는 다음과 같이 삭제합니다.
B의 회원들의 모든 기억을 자유롭게 합니다.
C의 내용을 B로 복사("다음" 포인터 포함)
전체 항목 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.
편집: 김보가 1분도 안 돼 나를 이겼습니다!
플래그를 사용하여 목록에서 노드를 링크 해제하도록 설정한 후 다음 적절한 트래버설에서 삭제하는 지연 링크를 수행할 수 있습니다.링크 해제하도록 설정된 노드는 목록을 크롤링하는 코드에 의해 적절하게 처리되어야 합니다.
처음부터 목록에서 항목을 가리키는 항목을 찾을 때까지 목록을 다시 한 번 이동할 수도 있습니다.최적은 아니지만 적어도 지연된 연결 해제보다 훨씬 더 나은 아이디어입니다.
일반적으로, 당신은 당신이 방금 온 물건에 대한 포인터를 알고 그것을 전달해야 합니다.
(편집: Ick, 제가 완전한 답변을 입력하는 데 걸린 시간과 함께 3조 명의 사람들이 제가 언급하고자 하는 거의 모든 요점을 다루었습니다. :()
이렇게 하는 유일한 방법은 선행하는 노드가 삭제할 노드를 찾을 때까지 두 개의 포인터로 목록을 이동한 다음 후행 포인터를 사용하여 다음 필드를 업데이트하는 것입니다.
목록에서 임의 항목을 효율적으로 삭제하려면 목록을 이중으로 연결해야 합니다.그러나 목록의 머리 부분에서 항목을 가져와 꼬리 부분에 추가하려는 경우에는 전체 목록을 이중으로 연결할 필요가 없습니다.목록을 하나만 연결하지만 목록의 마지막 항목의 다음 필드가 목록의 첫 번째 항목을 가리킵니다.그런 다음 목록 "머리"가 꼬리 항목(머리가 아님)을 가리킵니다.그런 다음 목록의 꼬리에 추가하거나 머리에서 제거하기가 쉽습니다.
당신이 명단의 선두를 차지하고 있죠?그냥 건너면 됩니다.
목록이 "head"로 가리키고 "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을 생성한 다음 사용자에게 삭제할 노드에 대한 포인터를 제공하도록 요청합니다.삭제 후 목록을 인쇄합니다. 삭제할 노드 이후에 삭제할 노드를 복사한 다음 삭제할 노드의 다음 노드를 삭제하는 것과 동일한 작업을 수행합니다.예
a-b-c-d
c를 band free 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;
}
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로 복사하여 삭제할 수 있습니다.그러나 단일 링크 리스트의 경우 노드를 삭제할 수 없습니다. 그렇게 하면 노드 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;
}
}
이것은 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);
}
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
}
언급URL : https://stackoverflow.com/questions/69209/deleting-a-middle-node-from-a-single-linked-list-when-pointer-to-the-previous-no
'codememo' 카테고리의 다른 글
| Visual Studio 코드가 설치된 Git를 감지할 수 없습니다. (0) | 2023.07.13 |
|---|---|
| IntelliJ Idea groovy.lang.그루비 런타임예외:충돌하는 모듈 버전 (0) | 2023.07.13 |
| 쉼표로 숫자를 수천 개의 구분자로 형식을 지정하는 방법은 무엇입니까? (0) | 2023.07.13 |
| 단일 워크북에서 여러 CSV를 여러 워크시트로 가져오기 (0) | 2023.07.13 |
| 이미 평가 중인 약속: 재귀적 기본 인수 참조 또는 이전 문제? (0) | 2023.07.13 |