Gelinkte lijst in C: hoe een gelinkte lijst in C implementeren?

zijn blog over Linked List in C laat je kennismaken met de datastructuur van Linked List in C en helpt je de implementatie van gekoppelde lijsten in detail te begrijpen met voorbeelden.

Na arrays is de op één na populairste datastructuur Linked List. Een gekoppelde lijst is een lineaire datastructuur, bestaande uit een keten van knooppunten waarin elk knooppunt een waarde en een pointer naar het volgende knooppunt in de keten bevat. Laten we in dit artikel eens kijken hoe we een gelinkte lijst kunnen implementeren in C.

Wat is gekoppelde lijst in C?

Een gekoppelde lijst is een lineaire gegevensstructuur. Elke gekoppelde lijst bestaat uit twee delen: het gegevensgedeelte en het adresgedeelte dat het adres bevat van het volgende element in de lijst, dat een knooppunt wordt genoemd.



De grootte van de gekoppelde lijst staat niet vast en gegevensitems kunnen op elke locatie in de lijst worden toegevoegd. Het nadeel is dat om bij een knooppunt te komen, we helemaal van het eerste knooppunt naar het knooppunt moeten gaan dat we nodig hebben. De gekoppelde lijst is als een array, maar in tegenstelling tot een array wordt deze niet opeenvolgend in het geheugen opgeslagen.

De meest populaire soorten gekoppelde lijsten zijn:

  1. Enkele linklijst
  2. Dubbel link lijst

Voorbeeld van gekoppelde lijst

Formaat: [data, adres]

Hoofd -> [3,1000] -> [43,1001] -> [21,1002]

In het voorbeeld is het nummer 43 aanwezig op locatie 1000 en het adres is aanwezig op het vorige knooppunt. Dit is hoe een gekoppelde lijst wordt weergegeven.

Basisfuncties van gekoppelde lijsten

Er zijn meerdere functies die kunnen worden geïmplementeerd op de gelinkte lijst in C. Laten we proberen ze te begrijpen met behulp van een voorbeeldprogramma.Eerst maken we een lijst, geven deze weer, voegen op een willekeurige locatie in, verwijderen een locatie. De volgende code laat zien hoe u bewerkingen op de lijst uitvoert.

#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3.Voeg in op het begin n ') printf (' n 4.Voeg aan het einde n ') printf (' n 5.Voeg op gespecificeerde positie n ') printf (' n 6.Verwijder vanaf het begin n ') printf (' n 7.Verwijder vanaf het einde n ') printf (' n 8. verwijderen van gespecificeerde positie n ') printf (' n 9.Exit n ') printf (' n ----------------- --------------------- n ') printf (' Voer uw keuze in: t ') scanf ('% d ', & keuze) schakelaar (keuze) {case 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nVoer de datawaarde in voor het knooppunt: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} anders {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList is leeg: n ') return} else {ptr = start printf (' nDe lijstelementen zijn: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nVoer de datawaarde voor het knooppunt: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} p rintf ('nVoer de datawaarde in voor het knooppunt: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nVoer de positie in voor het nieuwe knooppunt dat moet worden ingevoegd: t') scanf ('% d' , & pos) printf ('nVoer de datawaarde van het knooppunt in: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition niet gevonden: [Ga voorzichtig om] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nHet verwijderde element is:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nHet verwijderde element is:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nHet verwijderde element is:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nDe lijst is leeg: n') exit (0)} else {printf ('nVoer de positie in van het te verwijderen knooppunt : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nHet verwijderde element is:% dt ', ptr-> info) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nHet verwijderde element is: % dt ', ptr-> info) gratis (ptr)}}}

Het eerste deel van deze code is het maken van een structuur. Er wordt een gekoppelde lijststructuur gemaakt zodat deze de gegevens en het adres kan bevatten zoals we die nodig hebben. Dit wordt gedaan om de compiler een idee te geven van hoe het knooppunt zou moeten zijn.

wat is pojo in het voorjaar
struct node {int info struct node * next}

In de structuur hebben we een gegevensvariabele genaamd info om gegevens vast te houden en een pointer-variabele om naar het adres te wijzen. Er zijn verschillende bewerkingen die kunnen worden uitgevoerd op een gekoppelde lijst, zoals:

  • maken ()
  • Scherm()
  • insert_begin ()
  • insert_end ()
  • ] insert_pos ()
  • delete_begin ()
  • delete_end ()
  • delete_pos ()

Deze functies worden aangeroepen door de menugestuurde hoofdfunctie. In de hoofdfunctie nemen we input van de gebruiker op basis van welke bewerking de gebruiker in het programma wil doen. De invoer wordt vervolgens naar de schakelkast gestuurd en op basis van gebruikersinvoer.

Op basis van wat er wordt ingevoerd, wordt de functie aangeroepen. Vervolgens hebben we verschillende functies die moeten worden opgelost. Laten we al deze functies eens bekijken.

Functie maken

Ten eerste is er een aanmaakfunctie om de gekoppelde lijst te maken. Dit is de basismanier waarop de gekoppelde lijst wordt gemaakt. Laten we naar de code kijken.

void create () {struct node * temp, * ptr printf ('nVoer de datawaarde voor het knooppunt in: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}

Uitvoer

Invoegen - Gekoppelde lijst - Edureka

Eerst worden twee verwijzingen gemaakt van het type knooppunt, ptr en temp . We nemen de waarde die moet worden toegevoegd aan de gekoppelde lijst van de gebruiker en slaan deze op in het infogedeelte van de tijdelijke variabele en wijzen temp van het volgende dat het adresgedeelte is toe aan null. Er is een startwijzer die het begin van de lijst vasthoudt. Vervolgens kijken we naar het begin van de lijst. Als het begin van de lijst null is, wijzen we temp toe aan de startpointer. Anders gaan we naar het laatste punt waar de gegevens zijn toegevoegd.

Hiervoor kennen we ptr de startwaarde en doorlopen tot toe ptr-> volgende = null . We wijzen dan toe ptr-> volgende het adres van temp. Op een vergelijkbare manier wordt er code gegeven voor invoegen aan het begin, invoegen aan het einde en invoegen op een gespecificeerde locatie.

Weergavefunctie

Hier is de code voor de weergavefunctie.

void display () {struct node * ptr if (start == NULL) {printf ('nList is leeg: n') return} else {ptr = start printf ('nDe lijstelementen zijn: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> volgende}}}

Uitvoer

In de weergavefunctie controleren we eerst of de lijst leeg is en retourneren we als deze leeg is. In het volgende deel wijzen we de startwaarde toe aan ptr. We voeren dan een lus uit totdat ptr nul is en drukken het data-element voor elk knooppunt af, totdat ptr nul is, wat het einde van de lijst aangeeft.

java sorteerlijst van gehele getallen

Functie verwijderen

Hier is het codefragment om een ​​knooppunt uit de gekoppelde lijst te verwijderen.

void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nDe lijst is leeg: n') exit (0)} else {printf ('nVoer de positie van de knooppunt dat moet worden verwijderd: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nHet verwijderde element is:% dt ', ptr-> info ) free (ptr)} else {ptr = start voor (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe verwijderd element is:% dt ', ptr-> info) gratis (ptr)}}}

Uitvoer

Tijdens het verwijderingsproces controleert het eerst of de lijst leeg is, zo ja, dan bestaat deze. Als het niet leeg is, wordt de gebruiker gevraagd om de positie te verwijderen. Zodra de gebruiker de positie betreedt, controleert hij of dit de eerste positie is, zo ja, wijst hij toe ptr om te starten en verplaatst de startwijzer naar de volgende locatie en verwijdert ptr. Als het positie is niet nul , dan voert het een for-lus uit van 0 helemaal naar de pos die door de gebruiker is ingevoerd en is opgeslagen in de pos variabele. Er is een if-statement om te beslissen of de ingevoerde positie niet aanwezig is. Als ptr is gelijk aan null , dan is het niet aanwezig.

Wij wijs ptr toe aan temp in de for-lus, en ptr gaat dan verder met het volgende deel. Hierna wanneer de positie is gevonden. We maken de tijdelijke variabele om de waarde van vast te houden ptr-> volgende dus het overslaan van de ptr. Vervolgens wordt ptr verwijderd. Evenzo kan het worden gedaan voor het verwijderen van het eerste en het laatste element.

Dubbel gekoppelde lijst

Het wordt de dubbel gelinkte lijst genoemd omdat er twee zijn aanwijzingen , één punt naar het volgende knooppunt en andere wijst naar het vorige knooppunt. De bewerkingen die worden uitgevoerd in dubbel gelinkte, zijn vergelijkbaar met die van een enkelvoudig gelinkte lijst. Hier is de code voor basisbewerkingen.

#include #include struct Knooppunt typedef struct Knooppunt * PtrToNode typedef PtrToNode Lijst typedef PtrToNode Positie struct Knooppunt {int e Positie vorige Positie volgende} void Invoegen (int x, Lijst l, Positie p) {Positie TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> vorige = p TmpCell-> volgende = p-> volgende p-> volgende = TmpCell}} void Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> previous p2 = p -> next p1 - > next = p -> next if (p2! = NULL) // als het knooppunt niet het laatste knooppunt is p2 -> vorige = p -> vorige} else printf ('Element bestaat niet !!! n')} void Toon (Lijst l) {printf ('Het lijstelement is ::') Positie p = l-> volgende terwijl (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('DOUBLY LINKED LIST IMPLEMENTATION OF L IST ADTnn ') doe {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn Voer de keuze in :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Voer het in te voegen element :: ') scanf ('% d', & x) printf ('Voer de positie van het element ::' in) scanf ('% d', & pos) voor (i = 1 inext} Invoegen (x, l, p) break case 2: p = l printf ('Voer het element in dat verwijderd moet worden ::') scanf ('% d', & x) Verwijder (x, p) break case 3: Weergeven (l) break}} while (ch<4) } 

Uitvoer

wat is applet in java met voorbeeld

Dus, zoals u kunt zien, is het concept van bewerkingen vrij eenvoudig. De dubbel gelinkte lijst heeft dezelfde bewerkingen als die van de enkel gelinkte lijst in programmeertaal C. Het enige verschil is dat er een andere adresvariabele is die helpt om de lijst beter te doorlopen in een dubbel gelinkte lijst.

Ik hoop dat je hebt begrepen hoe je basisbewerkingen uitvoert op een enkelvoudig en dubbel gelinkte lijst in C.

Als u Linked List in Java wilt leren, is hier een .

Mocht u vragen tegenkomen, stel dan gerust al uw vragen in het commentaargedeelte van 'Linked List in C' en ons team zal u graag beantwoorden.