Dieser Artikel ist dem Start des Kurses „Algorithmen für Entwickler“ von OTUS gewidmet. Ich bedanke mich für die Unterstützung der Ressource durch dieses Unternehmen.
Sehen wir uns an, welche Operationen für eine verknüpfte Liste ausgeführt werden können.
Zwei wichtige Punkte, die Sie sich merken sollten:
- head zeigt auf den ersten Knoten der verknüpften Liste
- nächster der letzte Knotenzeiger ist nullptr , wenn also der nächste Knoten vom aktuellen Knoten nullptr ist, haben wir das Ende der verketteten Liste erreicht.
In allen Beispielen gehen wir davon aus, dass die verknüpfte Liste drei Knoten 1 ---> 2 ---> 3 mit einer Knotenstruktur wie unten gezeigt hat:
struct node
{
int data;
struct node* next {nullptr};
};
Wie man durch eine verkettete Liste iteriert
Das Anzeigen des Inhalts einer verknüpften Liste ist sehr einfach. Wir verschieben den temporären Knoten weiter zum nächsten und zeigen seinen Inhalt an.
Wenn temp NULL ist, wissen wir, dass wir das Ende der verknüpften Liste erreicht haben, also verlassen wir die while -Schleife.
struct node* temp = head;
std::cout << std::endl << std::endl << "List elements are - " << std::endl;
while(temp != nullptr)
{
std::cout << temp->data << " ---> ";
temp = temp->next;
}
Die Ausgabe dieses Programms wird sein:
List elements are - 1 ---> 2 ---> 3 --->
Wie man Elemente zu einer verketteten Liste hinzufügt
Sie können Elemente am Anfang, in der Mitte oder am Ende einer verknüpften Liste hinzufügen.
Zum Anfang hinzufügen
- Speicher für den neuen Knoten zuweisen
- Daten speichern
- Ändern Sie den neuen Knoten next so, dass er auf head zeigt
- Ändern Sie head so, dass es auf den neu erstellten Knoten zeigt
struct node* newNode = new node(); newNode->data = value; newNode->next = head; head = newNode;
Zum Ende hinzufügen
- Speicher für den neuen Knoten zuweisen
- Daten speichern
- Machen Sie einen Übergang zum letzten Knoten
- Ändere next vom letzten Knoten zum neu erstellten Knoten
struct node* newNode = new node();
newNode->data = value;
newNode->next = nullptr;
struct node *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = newNode;
Zur Mitte hinzufügen
- Weisen Sie Speicher zu und speichern Sie Daten für den neuen Knoten
- Zum Knoten unmittelbar vor der gewünschten Position des neuen Knotens springen
- Ändere nächste Zeiger, um dazwischen einen neuen Knoten hinzuzufügen
struct node *newNode = new node();
newNode->data = value;
struct node *temp = head;
for (int i=2; i < position; i++)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
So entfernen Sie einen Knoten aus einer verknüpften Liste
Sie können entweder am Anfang, am Ende oder ab einer bestimmten Position löschen.
Von Anfang an löschen
- Setzen Sie den Kopfzeiger auf den zweiten Knoten
head = head->next;
Am Ende löschen
- Gehe zum vorletzten Element
- Ändere den nächsten Zeiger auf nullptr
struct node* temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
temp->next = nullptr;
Aus der Mitte entfernen
- Gehen Sie zu dem Element vor dem zu entfernenden Element
- Ändere nächste Zeiger, um den Knoten aus der Kette auszuschließen
struct node* temp = head;
for (int i = 2; i < position; ++i)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
temp->next = temp->next->next;
Vollständiges Programm für verkettete Listenoperationen
Hier ist das vollständige Programm für alle verketteten Listenoperationen, die wir gelernt haben. Viele Grenzfälle wurden weggelassen, um das Programm kurz zu halten.
Wir schlagen vor, dass Sie sich das Programm einfach ansehen und versuchen, es selbst umzusetzen.
Beachten Sie auch, wie wir die Adresse von head als struct node headRef in den Funktionen insertAtFront und deleteFromFront übergeben. Diese beiden Funktionen ändern die Position des head -Zeigers, also müssen wir die Adresse des head**-Zeigers übergeben und seinen Wert innerhalb der Funktion ändern.
#include <iostream>
struct node
{
int data;
struct node* next {nullptr};
};
void display(struct node* head)
{
struct node* temp = head;
std::cout << std::endl << std::endl << "List elements are - " << std::endl;
while(temp != nullptr)
{
std::cout << temp->data << " ---> ";
temp = temp->next;
}
}
void insertAtMiddle(struct node *head, int position, int value)
{
struct node *newNode = new node();
newNode->data = value;
struct node *temp = head;
for (int i=2; i < position; i++)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
}
void insertAtFront(struct node** headRef, int value)
{
struct node* head = *headRef;
struct node* newNode = new node();
newNode->data = value;
newNode->next = head;
head = newNode;
*headRef = head;
}
void insertAtEnd(struct node* head, int value)
{
struct node* newNode = new node();
newNode->data = value;
newNode->next = nullptr;
struct node *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = newNode;
}
void deleteFromFront(struct node** headRef)
{
struct node* head = *headRef;
head = head->next;
*headRef = head;
}
void deleteFromEnd(struct node* head)
{
struct node* temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
temp->next = nullptr;
}
void deleteFromMiddle(struct node* head, int position)
{
struct node* temp = head;
for (int i = 2; i < position; ++i)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
temp->next = temp->next->next;
}
int main()
{
/* Initialize nodes */
struct node *head;
struct node *one = new node();
struct node *two = new node();
struct node *three = new node();
/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = nullptr;
/* Save address of first node in head */
head = one;
display(head); // 1 ---> 2 ---> 3 --->
insertAtFront(&head, 4);
display(head); // 4 ---> 1 ---> 2 ---> 3 --->
deleteFromFront(&head);
display(head); // 1 ---> 2 ---> 3 --->
insertAtEnd(head, 5);
display(head); // 1 ---> 2 ---> 3 ---> 5 --->
deleteFromEnd(head);
display(head); // 1 ---> 2 ---> 3 --->
int position = 3;
insertAtMiddle(head, position, 10);
display(head); // 1 ---> 2 ---> 10 ---> 3 --->
deleteFromMiddle(head, position);
display(head); // 1 ---> 2 ---> 3 --->
}
Die Ausgabe des Programms sieht wie folgt aus
List elements are - 1 ---> 2 ---> 3 ---> List elements are - 4 ---> 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 ---> 5 ---> List elements are - 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 10 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 --->
Fazit
Im Kurs "Algorithmen für Entwickler" von OTUS können Sie sich auch eingehender mit Algorithmen befassen Sie können sowohl grundlegende als auch komplexere Algorithmen vertiefen.
Der Kurs bietet Folgendes:
- Verständnis der Funktionsprinzipien verschiedener Algorithmen, Datenstrukturen
- Fähigkeit, vorgefertigte Algorithmen und Datenstrukturen zu verwenden und eigene für die Aufgabe zu erstellen
- Besitz der Technik zur Berechnung der Komplexität von Algorithmen
- Beherrschung fortgeschrittener Datenstrukturen: Hash-Tabellen, Grafiken, Suchbäume und mehr
- Fähigkeit, algebraische Probleme und dynamische Programmierprobleme zu lösen
Gleichzeitig bietet dieser Kurs das Studium von Algorithmen und Datenstrukturen mit Programmiersprachen wie Java, C ++, Python.
Sie können Ihre Fähigkeiten in testing testen, um zu verstehen, ob Sie bereit sind, an diesem Kurs teilzunehmen und was dieser Kurs leisten wird gibst du zusätzlich.
