Hvordan slette en node i en koblet liste C ++

En lenket liste er i utgangspunktet en kombinasjon av to ting: informasjonsdelen og adressedelen. Adressedelen, også kalt pekeren eller neste node -koblingen, lagrer adressen til neste node. Den koblede listen er i utgangspunktet en lineær datastruktur som lagrer data dynamisk gjennom pekere som enkelt kan nås av den forrige nodepekeren.

Noden til den koblede listen ser slik ut:

Sammenlignet med matrisen er den koblede listen ikke en sekvensiell datastruktur fordi den er en dynamisk lagret datastruktur. Den lagrer alle dataene på forskjellige minneplasser, og vi kan få tilgang til disse dataene gjennom pekeren til noden som lagrer adressen til dataene.

Denne måten å lagre data har disse fordelene:

1. Vi har ikke en forhåndsdefinert minnestørrelse som en matrise, noe som fører til mye minneavfall.

2. I en matrise, hvis vi definerer engangsminne, kan vi ikke redusere eller øke det i henhold til våre krav. Men i en lenket liste kan vi øke eller redusere nodene i henhold til våre krav.

Den koblede listen ser slik ut:

Hver koblede liste har en overskriftsnode som er den første noden på den koblede listen; og en haleknute som er til stede på slutten av den koblede listen. Fra haleknuten er den koblede listen som peker til neste node over fordi den lagrer nulladressen, som betyr ingenting. Hvis noen koblet liste bare har en node, betyr det at toppnoden og haleknoden er de samme.

Sletting av en koblet liste:

Som gitt nedenfor kan vi slette en node fra en koblet liste på tre måter:

1. Slett den første noden med koblet liste

2. Slett den siste noden med koblet liste

3. Slett en spesifikk posisjonsnode

Forklaring av alle disse konseptene:

Slett den første noden med koblet liste (overskriftsnoden):-

Å slette den første noden fra den koblede listen betyr å slette toppnoden (første noden) på den koblede listen. For å gjøre dette, må vi følge følgende prosedyre:

en. Vi må lage en peker (midlertidig).

b. Adressen til toppnoden er kopiert til pekeren (midlertidig).

c. Nå har vi lagret adressen til toppnoden. Så vi kan erklære den neste noden til overskriften som en koblet liste første node.

Å slette den første noden betyr at toppnoden er enkel:

C ++ kode for å slette den første noden fra den koblede listen:

void DeletelinkedListFirstNode ()

Node *TemporaryNode = Ny node;
midlertidignode = headnode;
headnode = headnode-> neste;
slett midlertidignode;

Slette den siste noden (haleknute):

Det var enkelt å slette den koblede listen. Men når vi ønsket å slette den koblede listens siste node eller haleknute, må vi overføre nullpekeren fra haleknuten til den forrige noden til halen, som har adressen til haleknuten.

For å implementere dette, må vi bruke to midlertidige noder og løpe gjennom den koblede listen. Når den kryssende koblede listen er over, vil den ene midlertidige noden peke på den nåværende noden, og en annen midlertidig node peker på forrige node. Nå tar begge påkrevde noder adressene vi har, og vi kan slette haleknuten mens vi skifter nullpekeren til den forrige noden.

C ++ kode for å slette den siste noden fra den koblede listen:

ugyldig deletelinkedlistlastnode ()

Node *CurrentNode = ny node;
Node *forrige node = ny node;
CurrentNode = headnode;
mens (CurrentNode-> Neste!= Null)

ForrigeNode = CurrentNode;
Current = CurrentNode-> Neste;

hale = forrige node;
forrige node-> neste = null;
Slett CurrentNode;

Slette noden i spesifikk stilling:

For å slette en node fra hvor som helst i den koblede listen, må vi legge inn den spesielle posisjonen til noden som vi ønsker å slette. For å definere den spesifikke posisjonsnoden, bruker vi to midlertidige noder, som vi gjorde mens vi slettet haleknuten. Vi krysser hele koblede listen før vi ikke får den spesifikke posisjonsnoden som vi ønsker å slette, og etter at vi har fått den noden, vil den andre midlertidige noden holde den forrige nodeadressen til den gjeldende noden. Ettersom vi har begge nodedetaljer, kan vi enkelt flytte adressen fra den slettede noden til forrige adresseknute, som nå vil peke på neste node, akkurat som i den forrige slettede metoden i den siste noden.

C ++ -kode for å slette den nde noden fra den koblede listen:

void sletentHpositionNode (int posisjonsnummer)
Node *CurrentNode = ny node;
Node *forrige node = ny node;
CurrentNode = headnode;
for (int count = 1; iForrigeNode = CurrentNode;
CurrentNode = CurrentNode-> Neste;

forrige node-> neste = currentNode-> neste;

C ++ Program for å slette en nth node fra den koblede listen

#inkludere
ved hjelp av navneområdet STD;
klasse LinkedListNode
offentlig:
int info;
LinkedListNode *peker;
;
int langecalculate (linkedListnode* node)
int count = 0;
mens (node!= Null)
node = node-> peker;
telle ++;

returantall;

void insert (linkedListnode ** headnode, int info)
LinkedListNode* newNode = new LinkedListNode ();
newNode-> info = info;
newNode-> peker = *headnode;
*headnode = newNode;

void Deletenodemethod (int Count, LinkedListNode ** headnode)
LinkedListNode * MIDATORYNODE = * HEADNODE;
LinkedListNode* forrige Node;
int lengde = lengdeCalculate (*headnode);
hvis (teller < 1 || count > lengde)
cout << "Deletion of linked list node is not valid" << endl;
komme tilbake;

// Denne fucntionen vil slette den første noden på den koblede listen
if (count == 1)
*headnode = (*headnode)-> peker;
cout << temporaryNode->info << " deleted the linked first node" << endl;
slett (midlertidignode);
komme tilbake;

// dette mens Loop vil stoppe når den nås på
// slutten av den koblede listen
mens (-count)
ForrigeNode = TemporaryNode;
midlertidignode = midlertidignode-> peker;

// Denne linjen vil oppdatere forrige nodepeker
// med NTH Linked List Node Pointer
forrige node-> peker = midlertidignode-> peker;
// Denne koden vil slette den nde noden fra den koblede listen
cout << temporaryNode->info << " deleted" << endl;;
slett (midlertidignode);

void displayLinkedList (LinkedListNode* element)
cout << "\nDisplaying LinkedList => : ";
// Denne tilstanden vil stoppe når LinkedList nådde på slutten
mens (vare!= Null)
cout << item->info << " ";
element = vare-> peker;

cout << endl;

int main ()
LinkedListNode* headnode = null;
Sett inn (& headnode, 29);
Sett inn (& headnode, 34);
Sett inn (& headnode, 23);
Sett inn (& headnode, 27);
Sett inn (& headnode, 31);
Sett inn (& headnode, 50);
displayLinkedList (headnode);
cout << "\n Deleting node number 3 = ";
deletenodemethod (3, & headnode);
cout << "\n After delete node number 3, linked list will be =";
displayLinkedList (headnode);
cout << "\n Deleting node number 5 = ";
Deletenodemethod (5, & headnode);
cout << "\n After delete node number 5, linked list will be =";
displayLinkedList (headnode);
retur 0;

Produksjon:

Viser LinkedList =>: 50 31 27 23 34 29
Slette node nummer 3 = 27 slettet
Etter slett node nummer 3 vil koblet liste være =
Viser LinkedList =>: 50 31 23 34 29
Slette node nummer 5 = 29 slettet
Etter å ha slettet node nummer 5, vil koblet liste være =
Visning av LinkedList =>: 50 31 23 34

Konklusjon:

I denne bloggen har vi studert forskjellige måter å slette de koblede listekonseptene og hvordan vi også kan kode i et C ++ -program. Til slutt studerte vi hovedbegrepene for å slette noden fra en bestemt posisjon. Koblede listekonsepter er alltid viktige fordi dette er måten å leke med minnet om operativsystemet og har mange fordeler sammenlignet med matrisen.