Legg til en node i en koblet liste i C ++

En koblet liste er en datastruktur som lagrer en samling av noder, der hver node lagrer en dataverdi og en peker til neste node i listen. I motsetning til matriser, kan koblede lister vokse og krympe dynamisk, noe som gjør det lettere å jobbe med data som stadig endres. Linked List Insertion er prosessen med å legge til en ny node til en koblet liste.

I C ++ kan vi sette inn en ny node i en koblet liste på tre måter:

1. I begynnelsen av den koblede listen
2. På slutten av den koblede listen
3. Etter en gitt node i den koblede listen

La oss snakke om hvordan du gjør hver av de koblede listeinnsettingsmetodene en etter en.

I begynnelsen av den koblede listen

For å legge til en hvilken som helst node i starten av den koblede listen, må vi følge disse trinnene:

1. Lag en ny node.
2. Den koblede listens overskriftsadresse er gitt til den nye nodepekeren, slik at den kan begynne å peke på toppnoden som allerede eksisterer.
3. Tilordne den nye nodeadressen til overskriften.

Neste ville være null hvis denne newnoden er den første noden i den koblede listen.

På slutten av den koblede listen

For å legge til en hvilken som helst node på slutten av den koblede listen, må vi følge disse trinnene:

1. Lag en ny node.
2. Kryss den koblede listen til vi kommer til slutten av den koblede listen.
3. Tilordne den nyopprettede noden til den koblede listepekeradressen til den siste noden til den koblede listepekeradressen slik at den kan begynne å peke på den nyopprettede noden.
4. På slutten, legg til en nullpeker til den nyopprettede noden på den koblede listen siden den nå er den siste noden.

Etter en gitt node i den koblede listen

For å legge til en hvilken som helst node i den første plasseringen av den koblede listen, må vi følge disse trinnene:

1. Lag en ny node.
2. Sjekk om brukerens ønskede posisjon for den nye noden er gyldig; det vil si om plasseringen av den nye noden er større enn eller mindre enn den koblede listestørrelsen.
3. Kryss den koblede listen til den første plasseringen av den koblede listen.
4. Tilordne den nde neste pekeren til den nyopprettede neste pekeren.
5. Tilordne den nye nodeadressen til den nde neste pekeren slik at den kan begynne å peke på den nye noden.

C ++ Program Implemenasjon for nodeinnsetting i lenket liste:

// Komplett program for innsetting i en koblet liste i C++
#inkludere
ved hjelp av navneområdet STD;
Klasseknute

offentlig:
int -data;
Node *Neste;
;
void insertatbeginningLinkedList (node ​​** headnode, int data)
// Lag minne dynamisk for denne newnoden
Node* newNode = new node ();
newNode-> data = data;
newNode-> next = *headnode;
*headnode = newNode;
cout << newNode->data << " inserted data successfully"
"Into Linked List" << endl;

void insertatlastlinkedlist (node ​​** headnode, int data)
Node* newNode = new node ();
newNode-> data = data;
// siste node peker alltid på null
newNode-> neste = null;
// Hvis koblet liste var tom
if (*headnode == null)
*headnode = newNode;
cout << newNode->data << " inserted data successfully"
"Into Linked List" << endl;
komme tilbake;

Node * tempnode = * headnode;
// nå til den siste noden med koblet liste
mens (tempnode-> neste!= Null)
tempnode = tempnode-> neste;
// tilordne newnode til den siste noden neste
tempnode-> neste = newNode;
cout << newNode->data størrelse ++;

returstørrelse;

void insertafternthnodelinkedlist
(int n, int data, node ** headnode)

int loc = n;
int størrelse = lengdeoflinkedlist (*headnode);
// Ingen negativ posisjonsinnsatser tillatt
// innsetting er ikke mulig hvis stedet er større
// enn den koblede listens størrelse.
hvis (n < 0 || n > størrelse)
cout << "Insert position not valid";
if (n == 0)
insertatbeginningLinkedList (headnode, data);

annet
Node* newNode = new node ();
newNode-> data = data;
newNode-> neste = null;
// brukte tempnode for å iterere gjennom den koblede listen
Node * tempnode = * headnode;
// Traverse til du kommer til NTH -noden
mens (-n)
tempnode = tempnode-> neste;
// til den nde noden neste, tilordne newnodes neste.
newNode-> neste = tempnode-> neste;
// tilordne nth node's ved siden av denne nye noden
tempnode-> neste = newNode;
// newnode satt inn
cout << newNode->data << " inserted data after index " <

void printlinkedList (node* node)
cout << "\n";
// mens tilstanden vil stoppe når node == null
mens (node!= Null)
cout << node->data << " "; node = node->neste;

cout << "\n" << endl;

int main ()

Node* headnode = null;
insertatbeginningLinkedList (& headnode, 10);
insertatbeginningLinkedList (& headnode, 9);
insertatbeginningLinkedList (& headnode, 8);
printlinkedList (headnode);
insertatlastLinkedList (& headnode, 11);
insertatlastLinkedList (& headnode, 12);
insertatlastLinkedList (& headnode, 14);
printlinkedList (headnode);
// setter inn data i den aktuelle posisjonen
InsertafternThnodelinkedList (5, 17, & headnode);
InsertafternThnodelinkedList (1, 11, & headnode);
printlinkedList (headnode);
retur 0;

Produksjon:

10 innsatte data med hell i koblet liste
9 Sett inn data med hell i koblet liste
8 innsatte data med hell i koblet liste
8 9 10
11 innsatte data på slutten
12 innsatte data på slutten
14 innsatte data på slutten
8 9 10 11 12 14
17 innsatte data etter indeks 5
11 innsatte data etter indeks 1
8 11 9 10 11 12 17 14

Forklaring:

Koden definerer en klasse som heter Node som har to egenskaper: (1) Data (av Type Int) for å lagre nodens verdi, og (2) Neste (av Type Node*) for å lagre pekeren til neste node i listen.

Programmet implementerer tre funksjoner for å sette inn nodene i den koblede listen:

• InsertatBeginningLinkedList: Setter inn en node i begynnelsen av den koblede listen.
• InsertatlastLinkedList: Setter inn en node på slutten av den koblede listen.
• Insertafternthnodelinkedlist: Setter inn en node etter den nde noden til den koblede listen.

En heltalldata og en dobbel peker til den koblede listens hodeknute blir sendt til InsertatBeginningLinkedList () -funksjonen. Ved hjelp av den nye noden () opprettes en ny nodes minne dynamisk, og dataene blir deretter tilordnet den nye noden. Senere oppdaterer den hodeknuten slik at det er den nye noden ved å sette den nye nodenes neste peker til forrige hodeknute.

Et heltalldata og en dobbel peker til den koblede listens hodeknute blir sendt til InsertatlastLinkedList () -metoden. Ved hjelp av den nye noden () opprettes en ny nodes minne dynamisk, og dataene blir deretter tilordnet den nye noden. Den nye nodens neste peker blir deretter satt til null. Hvis den koblede listen er tom, oppdateres hodeknuten for å tjene som den nye noden. I alle andre tilfeller krysser den den koblede listen til den når den siste noden, da den setter den nye noden til den siste nodens neste peker.

InsertafternThnodelinkedList () -funksjonen legger til en ny node med de gitte dataene etter den nth noden i en koblet liste. Den koblede listen og dens størrelse, så vel som posisjon n og dataene som skal settes inn, blir bestått som argumenter. For det første verifiserer funksjonen om plasseringen n er riktig (i.e., ikke negativ og ikke større enn størrelsen på den koblede listen). Feilmeldinger skrives ut hvis stillingen er ugyldig. Hvis posisjonen er gyldig, konstruerer funksjonen en ny node, setter sine data og neste felt, og søker deretter iterativt gjennom den koblede listen for å finne NTH -noden. Deretter kobler den den første noden og den nye noden ved å endre de neste pekerne i den nth noden og den nye noden.

Lengden på den koblede listen returneres av LengthoflinkedList () -funksjonen som godtar en peker til den koblede listens hodeknute. Dette oppnås ved å sløyfe rundt den koblede listen, telle nodene og returnere tellingen.

I hovedmetoden oppretter programmet en tom koblet liste, og kaller deretter alle tre innsettingsmetoder med forskjellige data og posisjonsinnganger. Til slutt skriver den ut den koblede listen for å se resultatene.

Konklusjon

Avhengig av hvor en innsetting blir gjort til en lenket liste, er det forskjellige tidsmessige og romlige kompleksitetsproblemer. Som en ekstremt effektiv operasjon har innsetting i begynnelsen av listen en konstant tidskompleksitet på O (1) og en konstant romkompleksitet på O (1). I det verste scenariet tar det å sette inn på slutten av listen O (N) lineær tid, der N er det totale antallet listeoppføringer. Dette er slik at vi kan oppdage haleknuten ved å krysse listen. I verste fall tar det å sette inn i en spesifikk posisjon i listen også lineær tid, som er O (n), fordi vi må gå gjennom listen for å finne noden i den spesifikke posisjonen. Uansett hvordan de blir lagt til, er de koblede listene en fleksibel og dynamisk måte å lagre dataene som kan brukes på mange forskjellige måter.