it-swarm-ko.tech

이전 노드에 대한 포인터를 사용할 수없는 경우 단일 링크 목록에서 중간 노드 삭제

사용 가능한 유일한 정보가 삭제할 노드에 대한 포인터이고 이전 노드에 대한 포인터가 아닌 경우 단일 링크 목록에서 중간 노드를 삭제할 수 있습니까? 삭제 후 이전 노드는 다음 노드를 가리켜 야합니다 삭제 된 노드.

40
Nitin

실제 문제가 아닌 퀴즈입니다. 그러나 어떤 가정을 할 수 있다면 O(1) time.)에서 해결할 수 있습니다. 그렇게하기 위해리스트 포인트를 복사 할 수 있어야합니다. 알고리즘은 다음과 같습니다. 수행원:

...-> 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. 두 번째 노드 (i + 1)의 NEXT를 임시 변수에 복사하십시오.
  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;
}

마이크.

87
Mikhail Tatarnikov

구조가있는 목록을 가정 해 봅시다

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

조금 부담 스러울 것입니다.

26
Ben Combee

불가능합니다.

삭제를 모방하는 해킹이 있습니다.

그러나 포인터가 가리키는 노드는 실제로 삭제되지 않습니다.

following 노드를 삭제하고 해당 내용을 actual 노드에 복사하는 일반적인 솔루션은 external pointers 포인팅이 있으면 부작용이 있습니다 목록의 노드에 연결하면 다음 노드를 가리키는 외부 포인터가 매달려있게됩니다.

11
codaddict

이 솔루션의 독창성 (다음 노드 삭제)에 감사하지만 문제의 질문에 대답하지 않습니다. 이것이 실제 솔루션 인 경우 올바른 질문은 "포인터가 제공되는 노드에 포함 된 값을 링크 된 목록에서 삭제"해야합니다. 그러나 물론 올바른 질문은 솔루션에 대한 힌트를 제공합니다. 그것이 공식화 된 문제는 사람을 혼란스럽게하기위한 것입니다 (특히 면접관이 노드가 중간에 있다고 언급하지 않았기 때문에 실제로 저에게 일어났습니다).

5
Alex B

한 가지 방법은 데이터에 null을 삽입하는 것입니다. 목록을 탐색 할 때마다 이전 노드를 추적합니다. 널 데이터를 찾으면 목록을 수정하고 다음 노드로 이동하십시오.

4
Joe Hildebrand

가장 좋은 방법은 여전히 ​​다음 노드의 데이터를 삭제할 노드에 복사하고 노드의 다음 포인터를 다음 노드의 다음 포인터로 설정 한 후 다음 노드를 삭제하는 것입니다.

삭제할 노드를 가리키는 외부 포인터의 문제는 true이지만 다음 노드에도 적용됩니다. 다음과 같은 연결 목록을 고려하십시오.

A-> B-> C-> D-> E-> F 및 G-> H-> I-> D-> E-> F

첫 번째 링크 된 목록에서 노드 C를 삭제해야하는 경우 언급 된 접근 방식에 따라 컨텐츠를 노드 C에 복사 한 후 노드 D를 삭제합니다. 그러면 다음 목록이 나타납니다.

A-> B-> D-> E-> F 및 G-> H-> I-> 매달려 포인터.

NODE C를 완전히 삭제하면 결과 목록은 다음과 같습니다.

A-> B-> D-> E-> F 및 G-> H-> I-> D-> E-> F.

그러나 노드 D를 삭제하고 이전 방법을 사용하는 경우 외부 포인터 문제가 여전히 있습니다.

4
Sandeep Mathias

초기 제안은 다음과 같이 변형되었습니다.

a-> b-> c

에:

a->, c

노드의 주소에서 다음 노드의 주소로의 맵 주위에 정보를 유지하면 다음에 체인을 수정하여 목록을 탐색 할 수 있습니다. 다음 순회 전에 여러 항목을 삭제 해야하는 경우 삭제 순서 (예 : 변경 목록)를 추적해야합니다.

표준 솔루션은 건너 뛰기 목록과 같은 다른 데이터 구조를 고려합니다.

3
Allan Wind

소프트 삭제를 수행 할 수 있습니까? (즉, 노드에서 "삭제됨"플래그 설정) 필요할 경우 나중에 목록을 정리할 수 있습니다.

3
perimosocordiae

주어진

A-> B-> C-> D

항목 B에 대한 포인터는
1. B 멤버의 메모리를 비우십시오
2. C의 내용을 B로 복사합니다 ( "다음"포인터 포함).
삼. 전체 항목 C를 삭제

물론 한 항목의 목록 작업과 같은 Edge 사례에주의해야합니다.

이제 B가 있던 곳에 C가 있고 C였던 스토리지가 해제되었습니다.

1
DarenW

아래 링크 목록 고려

1-> 2-> 3-> NULL

노드 2에 대한 포인터는 "ptr"이라고합니다.

다음과 같은 의사 코드를 가질 수 있습니다.

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

목록의 순회를 유지하려는 경우에는 아닙니다. 다음 노드에 연결하려면 이전 노드를 업데이트해야합니다.

어쨌든이 상황에 어떻습니까? 이 질문을 할 수 있도록 무엇을하려고합니까?

1
Allen

이전 노드를 찾으려면 목록을 아래로 이동해야합니다. 그러면 일반적으로 O (n ** 2)가 삭제됩니다. 삭제를 수행하는 유일한 코드 인 경우 이전 노드를 캐싱하고 검색을 시작하여 실제로 더 잘 수행 할 수 있지만 삭제 패턴에 따라 도움이되는지 여부가 달라집니다.

1
Kimbo
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;
   }
}
0
Aneesh

예,하지만 연결을 해제 할 수 없습니다. 메모리 손상에 신경 쓰지 않는다면 ;-)로 이동하십시오.

0
Steven A. Lowe

다음 코드는 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;
}
0

예, 그러나 목록을 삭제하면 목록이 손상됩니다.

이 경우 목록을 다시 탐색하고 해당 포인터를 가져옵니다! 일반적 으로이 질문을하는 경우 아마도 당신이하는 일에 버그가있을 수 있습니다.

0
owenmarshall
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;
   }
}
0
Aneesh

이전 목록 항목으로 이동하려면 현재 항목을 가리키는 next 포인터가있는 항목을 찾을 때까지 처음부터 목록을 탐색해야합니다. 그런 다음 목록에서 현재 항목을 제거하기 위해 수정해야 할 각 항목에 대한 포인터가 있습니다. 간단히 previous->next에서 current->next 그런 다음 current를 삭제하십시오.

편집 : Kimbo는 1 분 이내에 저를 이겼습니다!

0
Eltariel

플래그를 사용하여 목록에서 노드가 링크 해제되도록 설정 한 다음 링크 해제시 지연된 링크 해제를 수행 한 후 다음 적절한 순회에서 노드를 삭제할 수 있습니다. 연결 해제되도록 설정된 노드는 목록을 크롤링하는 코드에 의해 올바르게 처리되어야합니다.

목록에서 항목을 가리키는 것을 찾을 때까지 처음부터 다시 목록을 탐색 할 수 있다고 가정합니다. 거의 최적은 아니지만 지연된 연결 해제보다 훨씬 더 좋은 아이디어입니다.

일반적으로, 당신은 당신이 방금 온 아이템에 대한 포인터를 알아야하고 당신은 그것을 통과해야합니다.

(편집 : Ick, 시간이 지남에 따라 3 명의 gazillion 사람들이 내가 언급 할 거의 모든 요점을 다루었습니다. :()

0
DJ Capelis

이 작업을 수행하는 유일한 방법은 선행 노드가 삭제할 노드를 찾을 때까지 몇 개의 포인터로 목록을 탐색 한 후 후행 포인터를 사용하여 다음 필드를 업데이트하는 것입니다.

목록에서 임의의 항목을 효율적으로 삭제하려면 이중으로 연결해야합니다. 그러나 목록의 헤드에서 항목을 가져 와서 꼬리에 추가하려는 경우 전체 목록을 이중으로 연결할 필요가 없습니다. 목록을 한 번에 연결하지만 목록의 마지막 항목의 다음 필드가 목록의 첫 번째 항목을 가리 키도록합니다. 그런 다음 목록 "머리"가 머리가 아닌 꼬리 항목을 가리 키도록합니다. 그런 다음 목록의 꼬리에 쉽게 추가하거나 머리에서 제거 할 수 있습니다.

0
Paul

당신은 목록의 머리를 가지고 있습니까? 당신은 그것을 통과합니다.

목록이 "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;
0
Charles Graham

링크 된 목록 A-> B-> C-> D와 노드 B에 대한 포인터가있는 경우이 노드를 삭제해야하는 경우 노드 C의 컨텐츠를 B로 복사하고 노드 D를 C로 복사하고 D를 삭제할 수 있습니다. 단독으로 연결된 목록의 경우 노드를 삭제할 수 없으므로 노드 A도 손실됩니다. 이중으로 연결된 목록의 경우 A로 역 추적 할 수 있지만.

내가 맞아?

0
Smitha

이것은 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);
}
0
Desyn8686