TechCodeview

• Eine verknüpfte Liste kann als Sammlung aufgerufener Objekte definiert werden Knoten die zufällig im Speicher abgelegt werden.
• Ein Knoten enthält zwei Felder, d. h. die an dieser bestimmten Adresse gespeicherten Daten und den Zeiger, der die Adresse des nächsten Knotens im Speicher enthält.
• Der letzte Knoten der Liste enthält einen Zeiger auf die Null.

Verwendungsmöglichkeiten der verknüpften Liste

• Die Liste muss nicht zusammenhängend im Speicher vorhanden sein. Der Knoten kann sich an einer beliebigen Stelle im Speicher befinden und zu einer Liste verknüpft werden. Dadurch wird eine optimale Raumausnutzung erreicht.
• Die Listengröße ist auf die Speichergröße beschränkt und muss nicht im Voraus deklariert werden.
• Ein leerer Knoten darf nicht in der verknüpften Liste vorhanden sein.
• Wir können Werte primitiver Typen oder Objekte in der einfach verknüpften Liste speichern.

Warum eine verknüpfte Liste anstelle eines Arrays verwenden?

Bisher verwendeten wir eine Array-Datenstruktur, um die Gruppe von Elementen zu organisieren, die einzeln im Speicher gespeichert werden sollen. Array hat jedoch mehrere Vor- und Nachteile, die bekannt sein müssen, um die Datenstruktur zu bestimmen, die im gesamten Programm verwendet wird.

Array enthält folgende Einschränkungen:

1. Die Größe des Arrays muss im Voraus bekannt sein, bevor es im Programm verwendet werden kann.
2. Die Vergrößerung des Arrays ist ein zeitaufwändiger Prozess. Es ist nahezu unmöglich, die Größe des Arrays zur Laufzeit zu erweitern.
3. Alle Elemente im Array müssen zusammenhängend im Speicher gespeichert werden. Das Einfügen eines beliebigen Elements in das Array erfordert das Verschieben aller seiner Vorgänger.

Eine verknüpfte Liste ist die Datenstruktur, die alle Einschränkungen eines Arrays überwinden kann. Die Verwendung einer verknüpften Liste ist nützlich, weil

df.loc

1. Der Speicher wird dynamisch zugewiesen. Alle Knoten der verknüpften Liste werden nicht zusammenhängend im Speicher gespeichert und mithilfe von Zeigern miteinander verknüpft.
2. Die Größenbestimmung stellt kein Problem mehr dar, da wir die Größe zum Zeitpunkt der Deklaration nicht definieren müssen. Die Liste wächst je nach Bedarf des Programms und ist auf den verfügbaren Speicherplatz beschränkt.

Einfach verknüpfte Liste oder Einwegkette

Eine einfach verknüpfte Liste kann als Sammlung geordneter Mengen von Elementen definiert werden. Die Anzahl der Elemente kann je nach Programmbedarf variieren. Ein Knoten in der einfach verknüpften Liste besteht aus zwei Teilen: einem Datenteil und einem Linkteil. Der Datenteil des Knotens speichert tatsächliche Informationen, die vom Knoten dargestellt werden sollen, während der Linkteil des Knotens die Adresse seines unmittelbaren Nachfolgers speichert.

Eine Einwegkette oder eine einfach verknüpfte Liste kann nur in eine Richtung durchlaufen werden. Mit anderen Worten: Wir können sagen, dass jeder Knoten nur den nächsten Zeiger enthält und wir daher die Liste nicht in umgekehrter Richtung durchlaufen können.

Java for-Schleife

Stellen Sie sich ein Beispiel vor, bei dem die vom Schüler in drei Fächern erzielten Noten in einer verknüpften Liste gespeichert werden, wie in der Abbildung dargestellt.

In der obigen Abbildung stellt der Pfeil die Links dar. Der Datenteil jedes Knotens enthält die Noten, die der Student in den verschiedenen Fächern erhalten hat. Der letzte Knoten in der Liste wird durch den Nullzeiger identifiziert, der im Adressteil des letzten Knotens vorhanden ist. Wir können im Datenteil der Liste so viele Elemente haben, wie wir benötigen.

lexikographische Ordnung

Komplexität

Operationen auf einfach verknüpften Listen

Es gibt verschiedene Operationen, die für eine einfach verknüpfte Liste ausgeführt werden können. Eine Liste aller dieser Operationen finden Sie unten.

Knotenerstellung

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

Einfügen

Das Einfügen in eine einfach verkettete Liste kann an verschiedenen Positionen erfolgen. Basierend auf der Position des neuen Knotens, der eingefügt wird, wird die Einfügung in die folgenden Kategorien kategorisiert.

Löschen und Durchlaufen

Das Löschen eines Knotens aus einer einfach verknüpften Liste kann an verschiedenen Positionen erfolgen. Basierend auf der Position des zu löschenden Knotens wird der Vorgang in die folgenden Kategorien eingeteilt.

Verknüpfte Liste in C: Menügesteuertes Programm

 #include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('

*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
 5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
 Enter the location of the node after which you want to perform deletion 
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } 

Ausgabe:

 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9