Überprüfen Sie, ob die verknüpfte Liste in C++ leer ist

1. Verwenden Sie das Root-Element, um in C++ zu prüfen, ob die verknüpfte Liste leer ist
2. Überprüfen Sie, ob die verknüpfte Liste leer ist, ohne ein Root-Element in C++ zu verwenden
3. Verwenden Sie Stammpunkte, um in C++ zu prüfen, ob die verknüpfte Liste leer ist

Die verknüpfte Liste fungiert als Array und verwendet Zeiger für ihre Implementierung. Es ist das einfachste Beispiel einer dynamischen Datenstruktur, die von jedem Punkt im Array aus wachsen und schrumpfen kann.

Eine verknüpfte Liste hat mehrere dynamisch zugewiesene Knoten, die einen Wert und einen Zeiger enthalten. Dieses Tutorial zeigt Ihnen drei Möglichkeiten, um zu überprüfen, ob eine verknüpfte Liste in C++ leer ist.

Verwenden Sie das Root-Element, um in C++ zu prüfen, ob die verknüpfte Liste leer ist

Die Wurzel in einer verknüpften Liste fungiert als Element, das immer vorhanden ist, auch wenn die Liste leer ist. Die andere Verwendung einer Wurzel in einer verknüpften Liste besteht darin, das letzte Element zurück mit der Wurzel zu verknüpfen, wodurch ein Zyklus entsteht.

In C++ gibt es zwei primäre Möglichkeiten, um zu überprüfen, ob eine verknüpfte Liste leer ist, entweder durch Bereitstellung eines Zeigers auf das erste Element einer Liste (zum Beispiel: if (root->next == NULL) { /* empty list */ }) oder indem das Listenelement einer verketteten Liste zu ihrer Wurzel zurückverlinkt wird, um einen Zyklus zu bilden (if (root->next == root) { /*leere Liste */ }). Wenn Sie ein Stammelement verwenden, um zu überprüfen, ob eine verknüpfte Liste leer ist, ist mindestens ein verknüpfter Listenknoten erforderlich, der keine Daten enthält.

Codebeispiel:

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node *next;

  Node() {
    data = 0;
    next = NULL;
  }
};

class linked_list {
  Node *root;

 public:
  linked_list() { root = NULL; }

  Node *getRoot() { return root; }

  void add_node(int n) {
    Node *temp = new Node();
    temp->data = n;
    temp->next = NULL;
    if (root == NULL) {
      root = temp;
      root->next = root;
    } else {
      Node *last = root;
      while (last->next != root) {
        last = last->next;
      }
      temp->next = root;
      last->next = temp;
    }
  }

  void printList() {
    Node *temp = root;
    if (temp != NULL) {
      do {
        cout << temp->data << " ";
        temp = temp->next;
      } while (temp != root);
    }
  }

  bool isEmpty() {
    if (root->next == root && root->data == 0) return true;
    return false;
  }
};

int main() {
  linked_list l1;
  l1.add_node(5);
  l1.add_node(10);
  l1.add_node(15);

  if (l1.isEmpty())
    cout << "The list is empty!\n";
  else {
    cout << "The list is not empty! List contains:\n";
    l1.printList();
  }
  return 0;
}

Ausgang:

The list is not empty! List contains:
5 10 15

Ein Kopf- oder Wurzel-Knoten repräsentiert seine Startposition in einer verketteten Liste. Bei root gibt es immer ein Element.

Überprüfen Sie, ob die verknüpfte Liste leer ist, ohne ein Root-Element in C++ zu verwenden

Ohne root ist der Listenzeiger NULL, wenn die verknüpfte Liste leer ist. Die Komplexität der Überprüfung, ob die verknüpfte Liste leer ist oder nicht, ist bei diesem Ansatz die gleiche wie beim Element root, d.h. O(1).

Sie müssen einer Variablen einen vernünftigen Standardwert initialisieren, wenn Sie einen neuen Knoten zuweisen, damit ein Datenelement mit der Länge Null leicht identifiziert werden kann, um sein NULL -Verhalten zu identifizieren.

Codebeispiel:

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node* next;
};

void push(Node** head_ref, int new_data) {
  Node* new_node = new Node();
  new_node->data = new_data;
  new_node->next = (*head_ref);
  (*head_ref) = new_node;
}

bool isEmpty(Node** list) {
  if ((*list) == NULL) return true;
  return false;
}

void printList(Node* node) {
  while (node != NULL) {
    cout << node->data << " ";
    node = node->next;
  }
}

int main() {
  Node* list = NULL;
  if (isEmpty(&list))
    cout << "List is Empty" << endl;
  else {
    cout << "List is not empty! List contains:"
         << " ";
    printList(list);
  }
  // Inserting some elements in the list
  push(&list, 8);
  push(&list, 4);

  if (isEmpty(&list))
    cout << "The List is Empty" << endl;
  else {
    cout << "The list is not empty! The list contains:"
         << " ";
    printList(list);
  }
  return 0;
}

Ausgang:

The List is Empty
The list is not empty! The list contains: 4 8

Eine verkettete Liste ist nur dann richtig beendet, wenn ihr next-Zeiger eines Knotens auf NULL gesetzt ist. Wenn der Kopf-Zeiger der verknüpften Liste auf NULL gesetzt ist, wird sie als verkettete Liste der Länge Null bezeichnet, und eine verkettete Liste der Länge Null ist ebenfalls eine leere Liste, da sie einen NULL lead darstellt. Zeiger.

Verwenden Sie Stammpunkte, um in C++ zu prüfen, ob die verknüpfte Liste leer ist

Sie können das letzte Element einer verketteten Liste mit der Wurzel verknüpfen, um einen Zyklus zu bilden, der dabei hilft, die leere verkettete Liste zu identifizieren. Die Verwendung von Wurzelpunkten bringt verschiedene Vorteile mit sich, darunter niemals NULL als nächstes Element; Daher müssen Programmierer nicht mehr danach suchen.

Es bietet einige einzigartige Fälle, z. B. wenn die Wurzel- oder Kopf-Punkte einer verknüpften Liste auf sich selbst verweisen, stellt dies eine leere verknüpfte Liste dar. Wenn if (root->next == root) { /* empty list */ } wahr ist, dann ist eine verknüpfte Liste leer.

Pseudocode:

node *root;

... // process code (exp.)

if (root -> next == root) { /* empty list */ }

// check the head pointer - if it is NULL, there's no entry in the list.

int isEmpty( node * list )
 {
   if( !list )

      return 1;

   return 0; // otherwise in case false check
 }

Ihre Daten könnten neutralisiert oder auf Null gesetzt werden, wenn Sie eine Variable erstellen oder ihr in C++ einen unbrauchbaren Wert zuweisen. Sie müssen lernen, Ihre Variablen explizit zu initialisieren, ihnen eindeutige Werte zuzuweisen und die Regeln zu lernen, die sie regeln.