Verknüpfte Liste in C: Wie implementiere ich eine verknüpfte Liste in C?

Sein Blog über die verknüpfte Liste in C führt Sie in die Datenstruktur der verknüpften Liste in C ein und hilft Ihnen, die Implementierung der verknüpften Liste anhand von Beispielen im Detail zu verstehen.

Nach Arrays ist die zweitbeliebteste Datenstruktur die verknüpfte Liste. Eine verknüpfte Liste ist eine lineare Datenstruktur, die aus einer Knotenkette besteht, in der jeder Knoten einen Wert und einen Zeiger auf den nächsten Knoten in der Kette enthält. In diesem Artikel erfahren Sie, wie Sie eine verknüpfte Liste in C implementieren.

Was ist eine verknüpfte Liste in C?

Eine verknüpfte Liste ist eine lineare Datenstruktur. Jede verknüpfte Liste besteht aus zwei Teilen, dem Datenabschnitt und dem Adressabschnitt, der die Adresse des nächsten Elements in der Liste enthält, das als Knoten bezeichnet wird.



Die Größe der verknüpften Liste ist nicht festgelegt, und Datenelemente können an beliebigen Stellen in der Liste hinzugefügt werden. Der Nachteil ist, dass wir, um zu einem Knoten zu gelangen, den gesamten Weg vom ersten Knoten zum gewünschten Knoten zurücklegen müssen. Die verknüpfte Liste ähnelt einem Array, wird jedoch im Gegensatz zu einem Array nicht nacheinander im Speicher gespeichert.

Die beliebtesten Arten einer verknüpften Liste sind:

Erhöhen Sie eine Zahl zu einer Kraft in Java
  1. Linkliste einfach
  2. Doppelte Linkliste

Beispiel einer verknüpften Liste

Format: [Daten, Adresse]

Kopf -> [3.1000] -> [43.1001] -> [21.1002]

In dem Beispiel ist die Nummer 43 an Position 1000 vorhanden und die Adresse ist an dem vorherigen Knoten vorhanden. So wird eine verknüpfte Liste dargestellt.

Grundlegende Funktionen für verknüpfte Listen

Es gibt mehrere Funktionen, die in der verknüpften Liste in C implementiert werden können. Versuchen wir, sie mithilfe eines Beispielprogramms zu verstehen.Zuerst erstellen wir eine Liste, zeigen sie an, fügen sie an einer beliebigen Stelle ein und löschen eine Stelle. Der folgende Code zeigt Ihnen, wie Sie Vorgänge für die Liste ausführen.

#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 Auswahl während (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3.Insert at der Anfang n ') printf (' n 4. Am Ende einfügen n ') printf (' n 5. An der angegebenen Position einfügen n ') printf (' n 6. Von Anfang an löschen n ') printf (' n 7. Löschen vom Ende n ') printf (' n 8. Von der angegebenen Position löschen n ') printf (' n 9.Exit n ') printf (' n ----------------- --------------------- n ') printf (' Geben Sie Ihre Wahl ein: t ') scanf ('% d ', & Auswahl) Schalter (Auswahl) {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 Falsche Wahl: n') break}} return 0} voi d create () {Strukturknoten * temp, * ptr temp = (Strukturknoten *) malloc (Größe von (Strukturknoten)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nGeben Sie den Datenwert für den Knoten ein: 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 display () {Strukturknoten * ptr if (start == NULL) {printf ('nList ist leer: n ') return} else {ptr = start printf (' nDie Listenelemente sind: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {Strukturknoten * temp temp = (Strukturknoten *) malloc (sizeof (Strukturknoten)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nGeben Sie die ein Datenwert für den Knoten: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {Strukturknoten * temp, * ptr temp = (Strukturknoten *) malloc (Größe von (Strukturknoten)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} p rintf ('nGeben Sie den Datenwert für den Knoten ein: 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 () {Strukturknoten * ptr, * temp int i, pos temp = (Strukturknoten *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nGeben Sie die Position für den neuen einzufügenden Knoten ein: t') scanf ('% d') , & pos) printf ('nGeben Sie den Datenwert des Knotens ein: 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 nicht gefunden: [Vorsichtig behandeln] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {Strukturknoten * ptr if (ptr == NULL) {printf ('nListe ist leer: n') return} else {ptr = start start = start-> next printf (' nDas gelöschte Element lautet:% dt ', ptr-> info) free (ptr)}} void delete_end () {Strukturknoten * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nDas gelöschte Element ist:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nDas gelöschte Element ist:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nDie Liste ist leer: n') exit (0)} else {printf ('nGeben Sie die Position des zu löschenden Knotens ein : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nDas gelöschte Element ist:% dt ', ptr-> info) free (ptr )} else {ptr = Start für (i = 0inext if (ptr == NULL) {printf ('nPosition nicht gefunden: n') return}} temp-> next = ptr-> next printf ('nDas gelöschte Element ist: % dt ', ptr-> info) free (ptr)}}}

Der erste Teil dieses Codes erstellt eine Struktur. Eine verknüpfte Listenstruktur wird erstellt, damit die Daten und Adressen nach Bedarf gespeichert werden können. Dies geschieht, um dem Compiler eine Vorstellung davon zu geben, wie der Knoten sein soll.

Strukturknoten {int info Strukturknoten * weiter}

In der Struktur haben wir eine Datenvariable namens info zum Speichern von Daten und eine Zeigervariable zum Zeigen auf die Adresse. Es gibt verschiedene Vorgänge, die für eine verknüpfte Liste ausgeführt werden können, z.

  • erstellen()
  • Anzeige()
  • insert_begin ()
  • insert_end ()
  • ] insert_pos ()
  • delete_begin ()
  • delete_end ()
  • delete_pos ()

Diese Funktionen werden von der menügesteuerten Hauptfunktion aufgerufen. In der Hauptfunktion nehmen wir Eingaben vom Benutzer basierend auf der Operation vor, die der Benutzer im Programm ausführen möchte. Die Eingabe wird dann an den Schalterfall gesendet und basiert auf Benutzereingaben.

Je nachdem, welche Eingabe bereitgestellt wird, wird die Funktion aufgerufen. Als nächstes haben wir verschiedene Funktionen, die gelöst werden müssen. Schauen wir uns jede dieser Funktionen an.

Funktion erstellen

Erstens gibt es eine Erstellungsfunktion zum Erstellen der verknüpften Liste. Dies ist die grundlegende Art und Weise, wie die verknüpfte Liste erstellt wird. Schauen wir uns den Code an.

void create () {struct node * temp, * ptr printf ('nGeben Sie den Datenwert für den Knoten ein: 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}}

Ausgabe

Einfügen - Verknüpfte Liste - Edureka

Zunächst werden zwei Zeiger des Typs erstellt Knoten, ptr und temp . Wir nehmen den Wert, der zum Hinzufügen in die verknüpfte Liste benötigt wird, vom Benutzer und speichern ihn im Info-Teil der temporären Variablen und weisen temp von next, dem Adressenteil, null zu. Es gibt einen Startzeiger, der den Anfang der Liste hält. Dann prüfen wir den Anfang der Liste. Wenn der Anfang der Liste null ist, weisen wir dem Startzeiger Temp zu. Andernfalls fahren wir bis zum letzten Punkt, an dem die Daten hinzugefügt wurden.

Dazu weisen wir ptr den Startwert zu und durchlaufen bis ptr-> next = null . Wir weisen dann zu ptr-> next die Adresse von temp. In ähnlicher Weise wird Code zum Einfügen am Anfang, Einfügen am Ende und Einfügen an einer bestimmten Stelle angegeben.

Anzeigefunktion

Hier ist der Code für die Anzeigefunktion.

void display () {struct node * ptr if (start == NULL) {printf ('nList ist leer: n') return} else {ptr = start printf ('nDie Listenelemente sind: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> next}}}

Ausgabe

In der Anzeigefunktion prüfen wir zunächst, ob die Liste leer ist, und kehren zurück, wenn sie leer ist. Im nächsten Teil weisen wir ptr den Startwert zu. Wir führen dann eine Schleife aus, bis ptr null ist, und drucken das Datenelement für jeden Knoten, bis ptr null ist, was das Ende der Liste angibt.

Funktion löschen

Hier ist der Codeausschnitt zum Löschen eines Knotens aus der verknüpften Liste.

void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nDie Liste ist leer: n') exit (0)} else {printf ('nGeben Sie die Position des ein zu löschender Knoten: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nDas gelöschte Element ist:% dt ', ptr-> info ) free (ptr)} else {ptr = Start für (i = 0inext if (ptr == NULL) {printf ('nPosition nicht gefunden: n') return}} temp-> next = ptr-> next printf ('nThe gelöschtes Element ist:% dt ', ptr-> info) free (ptr)}}}

Ausgabe

Beim Löschvorgang wird zunächst geprüft, ob die Liste leer ist und ob sie vorhanden ist. Wenn es nicht leer ist, wird der Benutzer aufgefordert, die Position zu löschen. Sobald der Benutzer die Position eingegeben hat, prüft er, ob es sich um die erste Position handelt, wenn ja, weist er sie zu ptr zu starten und bewegt den Startzeiger zur nächsten Position und löscht ptr. Wenn die Position ist nicht Null Anschließend wird eine for-Schleife von 0 bis zu der vom Benutzer eingegebenen und in der gespeicherten Position ausgeführt pos Variable. Es gibt eine if-Anweisung, um zu entscheiden, ob die eingegebene Position nicht vorhanden ist. Wenn ptr ist gleich null dann ist es nicht vorhanden.

Wir Weisen Sie ptr temp zu in der for-Schleife, und ptr fährt dann mit dem nächsten Teil fort. Danach, wenn die Position gefunden ist. Wir machen die Temp-Variable so, dass sie den Wert von enthält ptr-> next somit wird der ptr übersprungen. Dann wird ptr gelöscht. Ebenso kann dies für das Löschen des ersten und des letzten Elements erfolgen.

Doppelt verknüpfte Liste

Es wird die doppelt verknüpfte Liste genannt, weil es zwei gibt Zeiger , ein Punkt zum nächsten Knoten und andere Punkte zum vorherigen Knoten. Die Operationen, die doppelt verknüpft ausgeführt werden, ähneln denen einer einfach verknüpften Liste. Hier ist der Code für grundlegende Operationen.

#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position vorherige Position next} void Insert (int x, Liste l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Speicher außerhalb des Raums') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete (int x, Liste l) {Position p, p1, p2 p = Finde (x, l) wenn (p! = NULL) {p1 = p -> vorheriges p2 = p -> nächstes p1 - > next = p -> next if (p2! = NULL) // wenn der Knoten nicht der letzte Knoten ist p2 -> previous = p -> previous} else printf ('Element existiert nicht !!! n')} void Anzeige (Liste l) {printf ('Das Listenelement ist ::') Position p = l-> next while (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i Liste l, l1 l = (Strukturknoten *) malloc (Größe von (Strukturknoten)) l-> previous = NULL l-> next = NULL Liste p = l printf ('DOPPELVERBUNDENE LISTE UMSETZUNG VON L. IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnGeben Sie die Auswahl ein :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Geben Sie das einzufügende Element ein :: ') scanf ('% d', & x) printf ('Geben Sie die Position des Elements ein ::') scanf ('% d', & pos) für (i = 1 inext} Fügen Sie (x, l, p) Unterbrechungsfall 2 ein: p = l printf ('Geben Sie das zu löschende Element ein ::') scanf ('% d', & x) Löschen Sie (x, p) Unterbrechungsfall 3: Anzeige (l) break}} while (ch<4) } 

Ausgabe

Wie Sie sehen, ist das Konzept der Operationen recht einfach. Die doppelt verknüpfte Liste hat die gleichen Operationen wie die einfach verknüpfte Liste in der Programmiersprache C. Der einzige Unterschied besteht darin, dass es eine andere Adressvariable gibt, mit deren Hilfe die Liste in einer doppelt verknüpften Liste besser durchlaufen werden kann.

Ich hoffe, Sie haben verstanden, wie man grundlegende Operationen an einfach und doppelt verknüpften Listen in C ausführt.

Wenn Sie die verknüpfte Liste in Java lernen möchten, finden Sie hier eine .

Wenn Sie auf Fragen stoßen, können Sie alle Ihre Fragen im Kommentarbereich von „Verknüpfte Liste in C“ stellen. Unser Team beantwortet diese gerne.