c - verkettete - zirkuläre liste java




Löschen eines mittleren Knotens aus einer einzelnen verknüpften Liste, wenn der Zeiger zum vorherigen Knoten nicht verfügbar ist (16)

Der beste Ansatz besteht immer noch darin, die Daten des nächsten Knotens in den zu löschenden Knoten zu kopieren, den nächsten Zeiger des Knotens auf den nächsten Zeiger des nächsten Knotens zu setzen und den nächsten Knoten zu löschen.

Die Probleme von externen Zeigern, die auf den Knoten zeigen, der gelöscht werden soll, obwohl er wahr ist, würden auch für den nächsten Knoten gelten. Betrachten Sie die folgenden verknüpften Listen:

A → B → C → D → E → F und G → H → I → D → E → F

Falls Sie den Knoten C (in der ersten verketteten Liste) löschen müssen, löschen Sie nach dem genannten Ansatz Knoten D nach dem Kopieren des Inhalts in den Knoten C. Daraus ergeben sich folgende Listen:

A-> B-> D-> E-> F und G-> H-> I-> Dangling-Zeiger.

Falls Sie den NODE C vollständig löschen, lauten die resultierenden Listen:

A → B → D → E → F und G → H → I → D → E → F.

Wenn Sie jedoch den Knoten D löschen möchten und den früheren Ansatz verwenden, ist das Problem der externen Zeiger immer noch vorhanden.

Ist es möglich, einen mittleren Knoten in der einzelnen verknüpften Liste zu löschen, wenn die einzige verfügbare Information der Zeiger auf den zu löschenden Knoten und nicht der Zeiger auf den vorherigen Knoten ist? Nach dem Löschen sollte der vorherige Knoten auf den Knoten neben zeigen gelöschter Knoten


Der einzige vernünftige Weg, dies zu tun, besteht darin, die Liste mit ein paar Zeigern zu durchlaufen, bis der führende den Knoten findet, der gelöscht werden soll, und dann das nächste Feld mit dem abschließenden Zeiger aktualisiert.

Wenn Sie zufällige Elemente effizient aus einer Liste löschen möchten, müssen Sie sie doppelt verknüpfen. Wenn Sie Elemente vom Kopf der Liste nehmen und sie am Ende hinzufügen möchten, müssen Sie die gesamte Liste nicht doppelt verknüpfen. Einfach die Liste verknüpfen, aber das nächste Feld des letzten Eintrags in der Liste auf den ersten Eintrag in der Liste setzen. Dann mache die Liste "Kopf" auf das Endstück (nicht den Kopf). Es ist dann einfach, zum Ende der Liste hinzuzufügen oder vom Kopf zu entfernen.


Dies ist ein Stück Code, den ich zusammengestellt habe, das tut, was das OP verlangt, und kann sogar das letzte Element in der Liste löschen (nicht auf die eleganteste Art, aber es macht es fertig). Schrieb es während des Lernens, wie man verknüpfte Listen benutzt. Ich hoffe es hilft.

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

Ein Ansatz wäre, eine Null für die Daten einzufügen. Wenn Sie die Liste durchlaufen, behalten Sie den vorherigen Knoten im Auge. Wenn Sie Nulldaten finden, beheben Sie die Liste und gehen zum nächsten Knoten.


Gegeben

A -> B -> C -> D

und einen Zeiger auf, sagen wir, Element B, Sie würden es löschen
1. Befreie jeden Speicher, der zu Mitgliedern von B gehört
2. kopiere den Inhalt von C in B (dies schließt seinen "nächsten" Zeiger ein)
3. Löschen Sie den gesamten Eintrag C

Natürlich müssen Sie bei Edge-Fällen vorsichtig sein, etwa wenn Sie an Listen eines Artikels arbeiten.

Jetzt, wo B war, hast du C und der Speicher, der früher C war, ist befreit.


Ich schätze den Einfallsreichtum dieser Lösung (Löschen des nächsten Knotens), aber sie beantwortet nicht die Frage des Problems. Wenn dies die tatsächliche Lösung ist, sollte die korrekte Frage lauten: "Lösche aus der verknüpften Liste den Wert, der in einem Knoten enthalten ist, auf den der Zeiger gegeben ist". Aber natürlich gibt die richtige Frage einen Hinweis auf die Lösung. Das Problem, wie es formuliert ist, soll die Person verwirren (was mir tatsächlich passiert ist, besonders weil der Interviewer nicht einmal erwähnt hat, dass der Knoten in der Mitte ist).


Ja, aber Sie können es nicht trennen. Wenn es dir nichts ausmacht, die Erinnerung zu zerstören, mach weiter ;-)


Mit dem folgenden Code wird ein LL erstellt, und der Benutzer wird aufgefordert, den Zeiger auf den zu löschenden Knoten zu setzen. Nach dem Löschen wird die Liste ausgedruckt. Dies geschieht genauso wie beim Kopieren des Knotens nach dem zu löschenden Knoten über den zu löschenden Knoten und dann Löschen des nächsten Knotens des zu löschenden Knotens. dh

A B C D

kopiere c nach b und frei c, so dass das Ergebnis ist

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

Nicht möglich.

Es gibt Hacks, um die Löschung nachzuahmen.

Aber keiner von denen wird tatsächlich den Knoten löschen, auf den der Zeiger zeigt.

Die beliebte Lösung, den folgenden Knoten zu löschen und seinen Inhalt auf den tatsächlich zu löschenden Knoten zu kopieren, hat Nebenwirkungen, wenn externe Zeiger auf Knoten in der Liste zeigen. In diesem Fall wird ein externer Zeiger, der auf den folgenden Knoten zeigt, frei.


Nicht, wenn Sie die Traversierbarkeit der Liste beibehalten möchten. Sie müssen den vorherigen Knoten aktualisieren, um ihn mit dem nächsten zu verknüpfen.

Wie kommst du überhaupt in diese Situation? Was versuchst du, dass du diese Frage stellst?


Sie können verzögerte Delinking durchführen, indem Sie Knoten, die aus der Liste entfernt werden sollen, mit einem Flag setzen und sie dann beim nächsten geeigneten Traversal löschen. Knoten, die deaktiviert werden sollen, müssen vom Code, der die Liste durchsucht, ordnungsgemäß verarbeitet werden.

Ich nehme an, Sie könnten die Liste auch einfach von Anfang an durchlaufen, bis Sie das Ding gefunden haben, das auf Ihren Gegenstand in der Liste zeigt. Kaum optimal, aber zumindest eine viel bessere Idee als ein verzögertes Auskochen.

Im Allgemeinen sollten Sie den Zeiger auf den Gegenstand kennen, von dem Sie gerade gekommen sind, und Sie sollten diesen herumreichen.

(Edit: Ick, mit der Zeit, die ich gebraucht habe, um eine vollständige Antwort einzugeben, haben drei Millionen Leute fast alle Punkte abgedeckt, die ich erwähnen würde.)


Sie müssen die Liste nach unten durchgehen, um den vorherigen Knoten zu finden. Das macht das Löschen im Allgemeinen O (n ** 2). Wenn Sie als einziger Code gelöscht werden, können Sie in der Praxis besser vorgehen, indem Sie den vorherigen Knoten zwischenspeichern und Ihre Suche dort starten. Ob dies jedoch hilft, hängt vom Löschmuster ab.


Vielleicht ein sanftes Löschen? (Setzen Sie auf dem Knoten ein "gelöscht" -Flag) Sie können die Liste später bei Bedarf löschen.


Wenn Sie eine verknüpfte Liste A -> B -> C -> D und einen Zeiger auf Knoten B haben. Wenn Sie diesen Knoten löschen müssen, können Sie den Inhalt von Knoten C in B, Knoten D in C kopieren und D löschen Wir können den Knoten als solchen im Fall einer einfach verknüpften Liste nicht löschen, da dann Knoten A ebenfalls verloren geht. Obwohl wir im Fall einer doppelt verknüpften Liste zu A zurückgehen können.

Habe ich recht?


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




linked-list