Lista circular doblemente enlazada en C++

Jinku Hu 12 octubre 2023

C++ C++ Data Structure

Este artículo demostrará cómo implementar una lista circular doblemente enlazada en C++.

Estructura de datos de lista circular doblemente enlazada desde cero en C++

Una lista doblemente enlazada es una estructura de datos en la que cada nodo almacena punteros tanto al siguiente como al anterior. Esto lo convierte en una opción óptima para implementar contenedores tipo std::deque. Sería mejor hacer circular una lista doblemente enlazada de modo que el miembro next del último nodo apunte al principio de la lista y el primer nodo también apunte al último nodo como su anterior.

Al principio, necesitamos declarar una struct llamada ListNode que se utiliza para construir una lista. A continuación, definimos una clase CircularList con dos miembros de datos de tipo ListNode y funciones de tres miembros.

Tenga en cuenta que decidimos incluir solo un constructor que acepte un valor de string e inicialice el primer nodo, pero esta parte se puede modificar si el programador lo crea conveniente. Dos miembros de datos, head y end, almacenan el primer y el último nodos. También tenemos funciones separadas para agregar elementos en cada lado de la lista.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next = nullptr;
  struct ListNode *prev = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->prev = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  ListNode *insertNodeHead(string data);
  void printNodes();

  ~CircularList();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = head;
  new_node->prev = end;
  new_node->data = std::move(data);

  head->prev = new_node;
  end->next = new_node;
  end = end->next;
  return end;
}

ListNode *CircularList::insertNodeHead(string data) {
  auto new_node = new ListNode;
  new_node->next = head;
  new_node->prev = end;
  new_node->data = std::move(data);

  head->prev = new_node;
  end->next = new_node;
  head = new_node;
  return head;
}

CircularList::~CircularList() {
  while (head != end) {
    auto tmp = head;
    head = head->next;
    delete tmp;
  }
  delete head;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  CircularList clist("Xenial");

  clist.insertNodeHead("Saucy");
  clist.insertNodeEnd("Quantal");

  clist.printNodes();
  cout << " ----------------------------------- " << endl;

  clist.insertNodeHead("Bionic");
  clist.printNodes();

  return EXIT_SUCCESS;
}

Producción :

node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal

El algoritmo general para la inserción de elementos implica asignar un nuevo objeto ListNode, asignar los punteros de nodo correspondientes a sus miembros y luego modificar los miembros head / end según sea necesario. También incluimos una función printNodes para mostrar el contenido de la lista, ya que es posible que necesitemos inspeccionar la exactitud del código. Tenga en cuenta que no debe olvidarse de desasignar toda la memoria después de que el objeto de la lista quede fuera de alcance. La última función se implementa como destructor.

Autor: Jinku Hu

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Estructura de datos de lista circular doblemente enlazada desde cero en C++

Artículo relacionado - C++ Data Structure