Comprobar si la lista vinculada está vacía en C++

1. Use el elemento raíz para verificar si la lista vinculada está vacía en C++
2. Compruebe si la lista vinculada está vacía sin usar un elemento raíz en C++
3. Use puntos raíz para verificar si la lista vinculada está vacía en C++

La lista enlazada funciona como una matriz y utiliza punteros para su implementación. Es el ejemplo más simple de una estructura de datos dinámica que puede crecer y reducirse desde cualquier punto de la matriz.

Una lista enlazada tiene múltiples nodos asignados dinámicamente que contienen un valor y un puntero. Este tutorial le enseñará tres formas de comprobar si una lista enlazada está vacía en C++.

Use el elemento raíz para verificar si la lista vinculada está vacía en C++

La raíz en una lista enlazada actúa como un elemento que siempre está presente incluso si la lista está vacía. El otro uso de tener una raíz en una lista enlazada es vincular el último elemento a la raíz formando un ciclo.

En C++, hay dos formas principales de comprobar si una lista enlazada está vacía proporcionando un puntero al primer elemento de una lista (por ejemplo: si (raíz->siguiente == NULL) { /* lista vacía * / }) o enlazando el elemento de lista de una lista enlazada a su raíz para formar un ciclo (if (raíz->siguiente == raíz) { /*lista vacía */ }). El uso de un elemento raíz para verificar si una lista vinculada está vacía requiere al menos un nodo de lista vinculada que no contenga datos.

Ejemplo de código:

#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;
}

Producción :

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

Un nodo principal o raíz representa su posición inicial en una lista enlazada. Con raíz, siempre hay un elemento.

Compruebe si la lista vinculada está vacía sin usar un elemento raíz en C++

Sin una raíz, el puntero de la lista es NULL cuando la lista enlazada está vacía. La complejidad de comprobar si la lista enlazada está vacía o no en este enfoque es la misma que con el elemento raíz, es decir, O(1).

Debe inicializar un valor predeterminado razonable para una variable cuando asigna un nuevo nodo para que pueda ser fácil identificar un miembro de datos con longitud cero para identificar su comportamiento NULO.

Ejemplo de código:

#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;
}

Producción :

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

Una lista enlazada solo se termina correctamente cuando su puntero siguiente de un nodo se establece en NULL. Si el puntero head de la lista enlazada se establece en NULL, entonces se llamará lista enlazada de longitud cero, y una lista enlazada de longitud cero también es una lista vacía porque representa un cliente potencial NULL puntero.

Use puntos raíz para verificar si la lista vinculada está vacía en C++

Puede vincular el último elemento de una lista vinculada a la raíz para formar un ciclo de modo que pueda ayudar a identificar la lista vinculada vacía. El uso de puntos raíz tiene varios beneficios, incluido nunca tener NULL como el siguiente elemento; por lo tanto, los programadores ya no están obligados a comprobarlo.

Ofrece algunos casos únicos, como si los puntos raíz o principal de una lista enlazada se vinculan a sí mismos, representa una lista enlazada vacía. Si if (raíz->siguiente == raíz) { /* lista vacía */ } es verdadero, entonces una lista enlazada está vacía.

Pseudocódigo:

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
 }

Sus datos podrían neutralizarse o ponerse a cero si crea una variable o le asigna algún valor basura en C++. Debe aprender a inicializar su variable explícitamente, asignarles valores únicos y aprender las reglas que la rigen.