My IT Utilities

Doubly linked list

Step through a C++ doubly linked list: insertion at both ends, deletion, reversal and the rule of five.

Everything is simulated in this browser; nothing is sent to any server.

Operations

The constructor is called

The constructor is called

l1Not constructed
∅
  • Current
  • Pointer

Step 1 / 34

l1
l2
l3

Code

#include <iostream>
#include <utility>
class Nodo { // A node holds the data and pointers to the previous and next ones
private: // Private attributes: only the methods touch them
int dato_;
Nodo* anterior_;
Nodo* siguiente_;
public:
Nodo(int dato, Nodo* anterior = nullptr, Nodo* siguiente = nullptr) {
dato_ = dato;
anterior_ = anterior;
siguiente_ = siguiente;
}
int getDato() const { return dato_; }
void setDato(int dato) { dato_ = dato; }
Nodo* getAnterior() const { return anterior_; }
void setAnterior(Nodo* anterior) { anterior_ = anterior; }
Nodo* getSiguiente() const { return siguiente_; }
void setSiguiente(Nodo* siguiente) { siguiente_ = siguiente; }
};
class Lista {
private:
Nodo* cabeza_; // First node of the list
Nodo* cola_; // Last node of the list
int n_; // Number of nodes
public:
Lista() { // Default constructor: creates an empty list
cabeza_ = nullptr;
cola_ = nullptr;
n_ = 0;
}
~Lista() { // Destructor: frees every node
while (cabeza_ != nullptr) {
Nodo* borra = cabeza_;
cabeza_ = borra->getSiguiente();
delete borra;
}
cola_ = nullptr;
}
Lista(const Lista& origin) { // Copy constructor: makes a deep copy
cabeza_ = nullptr;
cola_ = nullptr;
n_ = 0;
Nodo* aux = origin.cabeza_;
while (aux != nullptr) {
insertarAlFinal(aux->getDato()); // Inserting at the tail keeps the original order
aux = aux->getSiguiente();
}
}
Lista& operator=(const Lista& origin) { // Copy assignment: frees the old nodes, then copies
if (this != &origin) { // Guard against self-assignment
while (cabeza_ != nullptr) { // Free the nodes the list already has
Nodo* borra = cabeza_;
cabeza_ = borra->getSiguiente();
delete borra;
}
cola_ = nullptr;
n_ = 0;
Nodo* aux = origin.cabeza_;
while (aux != nullptr) {
insertarAlFinal(aux->getDato());
aux = aux->getSiguiente();
}
}
return *this;
}
Lista(Lista&& origin) noexcept { // Move constructor: steals the nodes of the source
cabeza_ = origin.cabeza_;
cola_ = origin.cola_;
n_ = origin.n_;
origin.cabeza_ = nullptr; // Leave the source empty
origin.cola_ = nullptr;
origin.n_ = 0;
}
Lista& operator=(Lista&& origin) noexcept { // Move assignment: frees the old nodes, then steals the new ones
if (this != &origin) { // Guard against self-assignment
while (cabeza_ != nullptr) { // Free the nodes the list already has
Nodo* borra = cabeza_;
cabeza_ = borra->getSiguiente();
delete borra;
}
cola_ = nullptr;
cabeza_ = origin.cabeza_;
cola_ = origin.cola_;
n_ = origin.n_;
origin.cabeza_ = nullptr; // Leave the source empty
origin.cola_ = nullptr;
origin.n_ = 0;
}
return *this;
}
int getTamano() const { return n_; }
Nodo* getCabeza() const { return cabeza_; }
Nodo* getCola() const { return cola_; }
void insertarElemento(int valor) { // Insert at the head: O(1)
Nodo* nodo = new Nodo(valor);
n_ += 1;
nodo->setSiguiente(cabeza_);
if (cabeza_ != nullptr) {
cabeza_->setAnterior(nodo);
} else {
cola_ = nodo;
}
cabeza_ = nodo;
}
void insertarAlFinal(int valor) { // Insert at the tail: O(1) thanks to cola_
Nodo* nodo = new Nodo(valor);
n_ += 1;
nodo->setAnterior(cola_);
if (cola_ != nullptr) {
cola_->setSiguiente(nodo);
} else {
cabeza_ = nodo;
}
cola_ = nodo;
}
void imprimirLista() const { // Print from the head to the tail
Nodo* actual = cabeza_;
while (actual != nullptr) {
std::cout << actual->getDato() << " ";
actual = actual->getSiguiente();
}
std::cout << std::endl;
}
void imprimirListaAtras() const { // Print from the tail to the head
Nodo* actual = cola_;
while (actual != nullptr) {
std::cout << actual->getDato() << " ";
actual = actual->getAnterior();
}
std::cout << std::endl;
}
void eliminarNodo(int indice) { // Delete the node at the given index
if (indice < 0 || indice >= n_) return; // Invalid index: nothing happens
Nodo* eliminar = cabeza_;
for (int i = 0; i < indice; i++) {
eliminar = eliminar->getSiguiente();
}
if (eliminar->getAnterior() != nullptr) {
eliminar->getAnterior()->setSiguiente(eliminar->getSiguiente());
} else {
cabeza_ = eliminar->getSiguiente();
}
if (eliminar->getSiguiente() != nullptr) {
eliminar->getSiguiente()->setAnterior(eliminar->getAnterior());
} else {
cola_ = eliminar->getAnterior();
}
delete eliminar;
n_--;
}
void invertirLista() { // Reverse the list in place: every node swaps anterior_ and siguiente_
Nodo* actual = cabeza_;
Nodo* temporal = nullptr;
while (actual != nullptr) {
temporal = actual->getAnterior();
actual->setAnterior(actual->getSiguiente());
actual->setSiguiente(temporal);
actual = actual->getAnterior(); // anterior_ is now the old siguiente_
}
temporal = cabeza_; // Finally swap the head and the tail
cabeza_ = cola_;
cola_ = temporal;
}
};
int main() {
Lista l1;
l1.insertarElemento(10);
l1.insertarElemento(20);
l1.insertarAlFinal(5);
l1.insertarElemento(30);
Lista l2;
l2.insertarElemento(100);
l2 = l1; // Copy assignment (without swap)
l2.imprimirLista();
l2.imprimirListaAtras();
Lista l3;
l3 = std::move(l1); // Move assignment (without swap)
l3.invertirLista();
l3.imprimirLista();
return 0;
}

This doubly linked list visualizer shows how every C++ node keeps a pointer to the previous node and another to the next one, and how the list maintains cabeza_, cola_ and n_. Three lists, l1, l2 and l3, share the canvas so you can insert at the head or the tail, delete by index, reverse the list and print it forwards and backwards. Then try the five special members of the rule of five: destructor, copy constructor, copy assignment, move constructor and move assignment. Every operation plays step by step with the C++ line highlighted, simulated addresses and the detached node while both pointers are reconnected. Everything is simulated in your browser.

How to use it

  1. Pick an example from the list or start with the first one, which builds a list and destroys it.
  2. Add operations to any of the three lists: insert at the head or the tail, delete by index, reverse or print in both directions.
  3. Choose the source list next to each row for copies and moves, and type a value or an index when needed.
  4. Press Play or step through and follow the highlighted C++ line, the two pointers of every node and their addresses.

Frequently asked questions

What is a doubly linked list?
It is a list where every node stores a pointer to the previous node and another to the next one. That lets you walk it in both directions and, with a pointer to the tail, insert at the end in O(1).
What is the advantage of keeping cola_?
With cola_ you insert at the end without walking the list, and you can print backwards starting from the last node.
What is the difference between copying and moving a list?
A copy creates new nodes with new addresses and leaves the source untouched. A move takes the source's nodes, keeps their addresses and leaves the source empty, with cabeza_ and cola_ set to nullptr.
Is the C++ code really compiled?
No. The page simulates every operation in your browser and highlights the matching line of code, so nothing is sent to any server.

Related tools