LinkedList-Datenstruktur

Inhaltsverzeichnis

Darstellung von LinkedList
Dienstprogramm für verknüpfte Listen
Beispiele für verknüpfte Listen in Python-, Java-, C- und C ++ - Beispielen
Komplexität der verknüpften Liste
Anwendungen für verknüpfte Listen

In diesem Tutorial lernen Sie die Datenstruktur verknüpfter Listen und deren Implementierung in Python, Java, C und C ++ kennen.

Eine verknüpfte Listendatenstruktur enthält eine Reihe verbundener Knoten. Hier speichert jeder Knoten die Daten und die Adresse des nächsten Knotens. Beispielsweise,

LinkedList-Datenstruktur

Sie müssen irgendwo anfangen, also geben wir der Adresse des ersten Knotens einen speziellen Namen namens HEAD.

Außerdem kann der letzte Knoten in der verknüpften Liste identifiziert werden, da sein nächster Teil auf NULL zeigt.

Möglicherweise haben Sie das Spiel Treasure Hunt gespielt, bei dem jeder Hinweis die Informationen zum nächsten Hinweis enthält. So funktioniert die verknüpfte Liste.

Darstellung von LinkedList

Mal sehen, wie jeder Knoten der LinkedList dargestellt wird. Jeder Knoten besteht aus:

Ein Datenelement
Eine Adresse eines anderen Knotens

Wir verpacken sowohl das Datenelement als auch die nächste Knotenreferenz in eine Struktur wie folgt:

 struct node ( int data; struct node *next; );

Das Verständnis der Struktur eines verknüpften Listenknotens ist der Schlüssel, um ihn zu verstehen.

Jeder Strukturknoten hat ein Datenelement und einen Zeiger auf einen anderen Strukturknoten. Lassen Sie uns eine einfache verknüpfte Liste mit drei Elementen erstellen, um zu verstehen, wie dies funktioniert.

 /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;

Wenn Sie keine der obigen Zeilen verstanden haben, benötigen Sie lediglich eine Auffrischung der Zeiger und Strukturen.

In nur wenigen Schritten haben wir eine einfache verknüpfte Liste mit drei Knoten erstellt.

LinkedList-Darstellung

Die Stärke von LinkedList beruht auf der Fähigkeit, die Kette zu unterbrechen und wieder zu verbinden. Wenn Sie beispielsweise ein Element 4 zwischen 1 und 2 setzen möchten, lauten die Schritte:

Erstellen Sie einen neuen Strukturknoten und weisen Sie ihm Speicher zu.
Addieren Sie den Datenwert als 4
Zeigen Sie mit dem nächsten Zeiger auf den Strukturknoten, der 2 als Datenwert enthält
Ändern Sie den nächsten Zeiger von "1" auf den gerade erstellten Knoten.

Um etwas Ähnliches in einem Array zu tun, müssten die Positionen aller nachfolgenden Elemente verschoben werden.

In Python und Java kann die verknüpfte Liste mithilfe von Klassen implementiert werden, wie in den folgenden Codes gezeigt.

Dienstprogramm für verknüpfte Listen

Listen sind eine der beliebtesten und effizientesten Datenstrukturen und können in allen Programmiersprachen wie C, C ++, Python, Java und C # implementiert werden.

Abgesehen davon sind verknüpfte Listen eine großartige Möglichkeit, um zu lernen, wie Zeiger funktionieren. Indem Sie üben, wie verknüpfte Listen bearbeitet werden, können Sie sich darauf vorbereiten, erweiterte Datenstrukturen wie Diagramme und Bäume zu erlernen.

Beispiele für verknüpfte Listen in Python-, Java-, C- und C ++ - Beispielen

Python Java C C +

 # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next

 // Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )

 // Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )

 // Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )