Länkad lista i C: Hur implementerar jag en länkad lista i C?

Efter matriser är den näst mest populära datastrukturen den länkade listan. En länkad lista är en linjär datastruktur, gjord av en kedja av noder där varje nod innehåller ett värde och en pekare till nästa nod i kedjan. I den här artikeln ska vi se hur man implementerar en länkad lista i C.

Vad är länkad lista i C?

En länkad lista är en linjär datastruktur. Varje länkad lista har två delar, datasektionen och adressavsnittet som innehåller adressen till nästa element i listan, som kallas en nod.

Storleken på den länkade listan är inte fast och dataobjekt kan läggas till var som helst i listan. Nackdelen är att för att komma till en nod måste vi korsa hela vägen från den första noden till den nod som vi behöver. Den länkade listan är som en matris men till skillnad från en matris lagras den inte sekventiellt i minnet.

De mest populära typerna av en länkad lista är:

hur man använder filer i java

1. Enstaka länklista
2. Dubbel länklista

Exempel på länkad lista

Format: [data, adress]

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

I exemplet är siffran 43 närvarande på plats 1000 och adressen finns i den tidigare noden. Således representeras en länkad lista.

Grundläggande länkade funktioner

Det finns flera funktioner som kan implementeras på den länkade listan i C. Låt oss försöka förstå dem med hjälp av ett exempelprogram.Först skapar vi en lista, visar den, infogar var som helst, tar bort en plats. Följande kod visar hur du utför åtgärder i listan.

#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. Insert in början n ') printf (' n 4. Infoga i slutet n ') printf (' n 5. Infoga vid angiven position n ') printf (' n 6. Radera från början n ') printf (' n 7. Radera från slutet n ') printf (' n 8. Radera från angiven position n ') printf (' n 9. Avsluta n ') printf (' n ----------------- --------------------- n ') printf (' Ange ditt val: t ') scanf ('% d ', & val) switch (val) {fall 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 Fel val: n') break}} return 0} voi d skapa () {struct nod * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nUt minne: n') exit (0) } printf ('n Ange datavärdet för noden: t') scanf ('% d', & temp-> info) temp-> nästa = NULL om (start == NULL) {start = temp} annat {ptr = start medan (ptr-> nästa! = NULL) {ptr = ptr-> nästa} ptr-> nästa = temp}} ogiltig visning () {struct nod * ptr om (start == NULL) {printf ('nList är tom: n ') returnera} annat {ptr = start printf (' n Listelementen är: n ') medan (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> nästa}}} ogiltigt insert_begin () {struct nod * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nUt minneutrymme: n') returnera} printf ('nAnge datavärde för noden: t ') scanf ('% d ', & temp-> info) temp-> nästa = NULL om (start == NULL) {start = temp} annat {temp-> nästa = start start = temp }} ogiltig insert_end () {struct nod * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} sid rintf ('n Ange datavärdet för noden: t') scanf ('% d', & temp-> info) temp-> nästa = NULL om (start == NULL) {start = temp} annat {ptr = start medan (ptr-> nästa! = NULL) {ptr = ptr-> nästa} ptr-> nästa = temp}} ogiltig insert_pos () {struct nod * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nUt minneutrymme: n') return} printf ('n Ange positionen för den nya noden som ska infogas: t') scanf ('% d' , & pos) printf ('n Ange datavärdet för noden: t') scanf ('% d', & temp-> info) temp-> nästa = NULL om (pos == 0) {temp-> nästa = start start = temp} annat {för (i = 0, ptr = startinxt om (ptr == NULL) {printf ('nPosition hittades inte: [Hantera med försiktighet] n') retur}} temp-> nästa = ptr-> nästa ptr -> nästa = temp}} ogiltig delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nDet borttagna elementet är:% dt ', ptr-> info) gratis (ptr)}} ogiltigt delete_end () {struct nod * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } annat om (start-> nästa == NULL) {ptr = start start = NULL printf ('nDet borttagna elementet är:% dt', ptr-> info) gratis (ptr)} annat {ptr = start medan (ptr- > nästa! = NULL) {temp = ptr ptr = ptr-> nästa} temp-> nästa = NULL printf ('nDet borttagna elementet är:% dt', ptr-> info) gratis (ptr)}} ogiltig delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('n Listan är tom: n') exit (0)} else {printf ('n Ange positionen för noden som ska raderas : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> nästa printf (' nDet borttagna elementet är:% dt ', ptr-> info) gratis (ptr )} annat {ptr = start för (i = 0 nästa om (ptr == NULL) {printf ('nPosition hittades inte: n') return}} temp-> nästa = ptr-> nästa printf ('nDet borttagna elementet är: % dt ', ptr-> info) gratis (ptr)}}}

Den första delen av den här koden skapar en struktur. En länkad liststruktur skapas så att den kan hålla data och adress som vi behöver den. Detta görs för att ge kompilatorn en uppfattning om hur noden ska vara.

struct node {int info struct node * next}

I strukturen har vi en datavariabel som kallas info för att hålla data och en pekervariabel för att peka på adressen. Det finns olika operationer som kan göras på en länkad lista, som:

• skapa()
• visa()
• insert_begin ()
• insert_end ()
• ] infoga_pos ()
• delete_begin ()
• delete_end ()
• delete_pos ()

Dessa funktioner anropas av den menystyrda huvudfunktionen. I huvudfunktionen tar vi input från användaren baserat på vilken operation användaren vill göra i programmet. Ingången skickas sedan till switchväskan och baseras på användarinmatning.

Baserat på vilken ingång som tillhandahålls kommer funktionen att anropas. Därefter har vi olika funktioner som behöver lösas. Låt oss ta en titt på var och en av dessa funktioner.

Skapa funktion

Först finns det en skapa-funktion för att skapa den länkade listan. Detta är det grundläggande sättet som den länkade listan skapas. Låt oss titta på koden.

ogiltig skapa () {struct nod * temp, * ptr printf ('n Ange datavärdet för noden: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} annat {ptr = start medan (ptr-> nästa! = NULL) {ptr = ptr-> nästa} ptr-> nästa = temp}}

Produktion

Först skapas två pekare av typen nod, ptr och temp . Vi tar värdet som behövs för att läggas till i den länkade listan från användaren och lagrar det i informationsdel av tempvariabeln och tilldelar temp för nästa som är adressdelen till null. Det finns en startpekare som håller början på listan. Sedan letar vi efter början på listan. Om början på listan är noll, tilldelar vi temp till startpekaren. Annars går vi till den sista punkten där data har lagts till.

För detta tilldelar vi ptr startvärdet och travers till ptr-> nästa = null . Vi tilldelar sedan ptr-> nästa adressen till temp. På liknande sätt finns det kod för att infoga i början, infoga i slutet och infoga på en viss plats.

Displayfunktion

Här är koden för visningsfunktion.

hur man gör dubbel till int Java

void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('n Listelementen är: n') medan (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> nästa}}}

Produktion

I visningsfunktionen kontrollerar vi först om listan är tom och återgår om den är tom. I nästa del tilldelar vi startvärdet till ptr. Vi kör sedan en slinga tills ptr är noll och skriver ut dataelementet för varje nod tills ptr är noll, vilket anger slutet på listan.

Radera funktion

Här är kodavsnittet för att ta bort en nod från den länkade listan.

ogiltig delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('n Listan är tom: n') exit (0)} else {printf ('n Ange positionen för nod som ska raderas: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> nästa printf (' nDet borttagna elementet är:% dt ', ptr-> info ) gratis (ptr)} annat {ptr = start för (i = 0 nästa om (ptr == NULL) {printf ('nPosition hittades inte: n') return}} temp-> nästa = ptr-> nästa printf ('nThe raderat element är:% dt ', ptr-> info) gratis (ptr)}}}

Produktion

I borttagningsprocessen kontrollerar den först om listan är tom, om ja den finns. Om den inte är tom ber den användaren att positionen ska raderas. När användaren kommer in i positionen kontrollerar den om det är den första positionen, om ja den tilldelas ptr för att starta och flyttar startpekaren till nästa plats och raderar ptr. Om position är inte noll , sedan kör den en for-loop från 0 hela vägen till den post som användaren angett och lagrat i pos variabel. Det finns ett if-uttalande för att avgöra om den intagna positionen inte är närvarande. Om ptr är lika med null , då är det inte närvarande.

Vi tilldela ptr till temp i for-slingan och ptr går sedan vidare till nästa del. Efter detta när positionen hittas. Vi gör tempvariabeln för att hålla värdet på ptr-> nästa därmed hoppa över ptr. Sedan raderas ptr. På samma sätt kan det göras för första och sista radering av element.

Dubbel länkad lista

Det kallas den dubbelt länkade listan eftersom det finns två pekare , en punkt till nästa nod och andra punkter till föregående nod. De operationer som utförs i dubbelt länkade liknar de i en enskilt länkad lista. Här är koden för grundläggande operationer.

#include #include struct Nod typedef struct Nod * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Nod {int e Position previous Position next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) om (TmpCell == NULL) printf ('Memory out of spacen') annat {TmpCell-> e = x TmpCell-> föregående = p TmpCell-> nästa = p-> nästa p-> nästa = TmpCell}} ogiltig Radera (int x, Lista l) {Position p, p1, p2 p = Hitta (x, l) om (p! = NULL) {p1 = p -> föregående p2 = p -> nästa p1 - > nästa = p -> nästa om (p2! = NULL) // om noden inte är den sista noden p2 -> föregående = p -> föregående} annars printf ('Element existerar inte !!! n')} ogiltig Visa (Lista l) {printf ('Listelementet är ::') Position p = l-> nästa medan (p! = NULL) {printf ('% d ->', p-> e) p = p- > nästa}} 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 ('DUBBELLÄNKT LISTA GENOMFÖRANDE AV L IST ADTnn ') gör {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnAnge valet :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Ange elementet som ska infogas :: ') scanf ('% d', & x) printf ('Ange positionen för elementet ::') scanf ('% d', & pos) för (i = 1 inästa} Infoga (x, l, p) break case 2: p = l printf ('Ange elementet som ska raderas ::') scanf ('% d', & x) Radera (x, p) break case 3: Display (l) bryta}} medan (kap<4) } 

Produktion

Så som du ser är begreppet operationer ganska enkelt. Den dubbelt länkade listan har samma operationer som den för enstaka länkade listor i C-programmeringsspråk. Den enda skillnaden är att det finns en annan adressvariabel som hjälper till att passera listan bättre i en dubbelt länkad lista.

Jag hoppas att du har förstått hur man utför grundläggande operationer på en enda och dubbelt länkad lista i C.

Om du vill lära dig länkad lista i Java, här är en .

Om du stöter på några frågor är du välkommen att ställa alla dina frågor i kommentarfältet i 'Länkad lista i C' så kommer vårt team gärna svara.