Mit Beispielen erläuterte Datenstrukturen - Verknüpfte Liste

So wie eine Girlande aus Blumen besteht, besteht eine verknüpfte Liste aus Knoten. Wir nennen jede Blume auf dieser bestimmten Girlande einen Knoten. Und jeder der Knoten zeigt auf den nächsten Knoten in dieser Liste und hat Daten (hier ist es der Blumentyp).

Typen

Einfach verknüpfte Liste

Einfach verknüpfte Listen enthalten Knoten, die sowohl ein dataFeld als auch ein nextFeld haben, das auf den nächsten Knoten in der Sequenz zeigt. Operationen, die für einfach verknüpfte Listen ausgeführt werden können, sind Einfügen, Löschen und Durchlaufen.

 head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+

Die interne Implementierung von CPython, die Frames und die ausgewerteten Variablen werden auf einem Stapel gespeichert.

Dazu müssen wir nur vorwärts iterieren, um den Kopf zu bekommen, daher wird eine einfach verknüpfte Liste verwendet.

Doppelt verknüpfte Liste

Doppelt verknüpfte Listen enthalten Knoten, deren dataFeld, nextFeld und ein anderes Verknüpfungsfeld prevauf den vorherigen Knoten in der Sequenz verweisen.

 head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+

Der Browser-Cache, mit dem Sie die Schaltflächen ZURÜCK und VORWÄRTS drücken können. Hier müssen wir eine doppelt verknüpfte Liste mit URLsals Datenfeld führen, um den Zugriff in beide Richtungen zu ermöglichen. Um zur vorherigen URL zu gelangen, verwenden wir das prevFeld und um zur nächsten Seite zu gelangen, verwenden wir das nextFeld.

Zirkuläre verknüpfte Liste

Kreisförmig verknüpfte Listen sind einfach verknüpfte Listen, in denen das nextFeld des letzten Knotens auf den ersten Knoten in der Sequenz zeigt.

 head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+

Timesharing-Problem vom Betriebssystem gelöst.

In einer Timesharing-Umgebung muss das Betriebssystem eine Liste der vorhandenen Benutzer führen und jedem Benutzer abwechselnd erlauben, einen kleinen Teil der CPU-Zeit einzeln zu verwenden. Das Betriebssystem wählt einen Benutzer aus, lässt ihn eine kleine Menge CPU-Zeit verwenden und fährt dann mit dem nächsten Benutzer fort.

Für diese Anwendung sollte es keine NULL-Zeiger geben, es sei denn, es gibt absolut niemanden, der die CPU-Zeit anfordert, dh die Liste ist leer.

Grundoperationen

Einfügen

Hinzufügen eines neuen Elements zur Liste.

Einfügen am Anfang:

  • Erstellen Sie einen neuen Knoten mit den angegebenen Daten.
  • Zeigen Sie neue Knoten nextauf alte head.
  • Zeigen Sie headauf diesen neuen Knoten.

Einsetzen in der Mitte / am Ende.

Einfügen nach Knoten X.

  • Erstellen Sie einen neuen Knoten mit den angegebenen Daten.
  • Punkt neuer Knoten ist nextzu alt X next.
  • Zeigen Sie mit X nextauf diesen neuen Knoten.

Zeitkomplexität: O (1)

Streichung

Vorhandenes Element aus der Liste löschen.

Löschen am Anfang

  • Holen Sie sich den Knoten headals Temp.
  • Zeigen Sie headauf Temp's next.
  • Freier Speicher, der vom Temp-Knoten verwendet wird.

Löschung in der Mitte / am Ende.

Löschung nach Knoten X.

  • Holen Sie sich den Knoten Xals Temp.
  • Zeigen Sie mit X nextauf Temp next.
  • Freier Speicher, der vom Temp-Knoten verwendet wird.

Zeitkomplexität: O (1)

Durchqueren

Über die Liste reisen.

Durchquerung

  • Lassen Sie den Knoten headals Aktuell anzeigen.
  • Überprüfen Sie, ob Current nicht null ist, und zeigen Sie es an.
  • Zeigen Sie Strom auf Strom nextund fahren Sie mit dem obigen Schritt fort.

Zeitkomplexität: O (n) // Hier ist n die Größe der Linkliste

Implementierung

C ++ Implementierung einer einfach verknüpften Liste

// Header files #include  struct node { int data; struct node *next; }; // Head pointer always points to first element of the linked list struct node *head = NULL;

Drucken von Daten in jedem Knoten

// Display the list void printList() { struct node *ptr = head; // Start from the beginning while(ptr != NULL) { std::cout 

Insertion at the beginning

// Insert link at the beginning void insertFirst(int data) { // Create a new node struct node *new_node = new struct node; new_node->data = data; // Point it to old head new_node->next = head; // Point head to new node head = new_node; std::cout << "Inserted successfully" << std::endl; }

Deletion at the beginning

// Delete first item void deleteFirst() { // Save reference to head struct node *temp = head; // Point head to head's next head = head->next; // Free memory used by temp temp = NULL: delete temp; std::cout << "Deleted successfully" << std::endl; }

Size

// Find no. of nodes in link list void size() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) { length++; } std::cout << "Size of Linked List is " << length << std::endl; }

Searching

// Find node with given data void find(int data){ // Start from the head struct node* current = head; // If list is empty if(head == NULL) { std::cout << "List is empty" next == NULL){ std::cout << "Not Found" 

Deletion after a node

// Delete a node with given data void del(int data){ // Start from the first node struct node* current = head; struct node* previous = NULL; // If list is empty if(head == NULL){ std::cout << "List is empty" next == NULL){ std::cout << "Element not found" next; } else { // Skip the current node previous->next = current->next; } // Free space used by deleted node current = NULL; delete current; std::cout << "Deleted succesfully" << std::endl; }

Python Implementation of Singly Linked List

class Node(object): # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to get data def get_data(self): return self.data # Function to get next node def get_next(self): return self.next # Function to set next field def set_next(self, new_next): self.next = new_next class LinkedList(object): def __init__(self, head=None): self.head = head

Insertion

 # Function to insert data def insert(self, data): # new_node is a object of class Node new_node = Node(data) new_node.set_next(self.head) self.head = new_node print("Node with data " + str(data) + " is created succesfully")

Size

 # Function to get size def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() print("Size of link list is " + str(count))

Searching

 # Function to search a data def search(self, data): current = self.head found = False while current and found is False: if current.get_data() == data: found = True else: current = current.get_next() if current is None: print("Node with data " + str(data) + " is not present") else: print("Node with data " + str(data) + " is found")

Deletion after a node

 # Function to delete a node with data def delete(self, data): current = self.head previous = None found = False while current and found is False: if current.get_data() == data: found = True else: previous = current current = current.get_next() if current is None: print("Node with data " + str(data) + " is not in list") elif previous is None: self.head = current.get_next() print("Node with data " + str(data) + " is deleted successfully") else: previous.set_next(current.get_next()) print("Node with data " + str(data) + " is deleted successfully")

Advantages

  1. Linked lists are a dynamic data structure, which can grow and shrink, allocating and deallocating memory while the program is running.
  2. Insertion and deletion of node are easily implemented in a linked list at any position.

Disadvantages

  1. They use more memory than arrays because of the memory used by their pointers (next and prev).
  2. Random access is not possible in linked list. We have to access nodes sequentially.
  3. It’s more complex than array. If a language supports array bound check automatically, Arrays would serve you better.

Note

We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.

Original text