双方向連結リスト
C++ の双方向連結リストをステップごとに確認します:両端への挿入、削除、反転、ルール・オブ・ファイブ。
すべてこのブラウザ内でシミュレートされ、サーバーには一切送信されません。
操作
コンストラクタを呼び出す
コンストラクタを呼び出す
l1未構築
∅
- 現在
- ポインタ
ステップ 1 / 34
l1
l2
l3
コード
#include <iostream>
#include <utility>
class Nodo { // ノードはデータと前後のノードへのポインタを保持します
private: // プライベート属性:メソッドだけが触れます
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_; // リストの先頭ノード
Nodo* cola_; // リストの末尾ノード
int n_; // ノード数
public:
Lista() { // デフォルトコンストラクタ:空のリストを作ります
cabeza_ = nullptr;
cola_ = nullptr;
n_ = 0;
}
~Lista() { // デストラクタ:すべてのノードを解放します
while (cabeza_ != nullptr) {
Nodo* borra = cabeza_;
cabeza_ = borra->getSiguiente();
delete borra;
}
cola_ = nullptr;
}
Lista(const Lista& origin) { // コピーコンストラクタ:ディープコピーを作ります
cabeza_ = nullptr;
cola_ = nullptr;
n_ = 0;
Nodo* aux = origin.cabeza_;
while (aux != nullptr) {
insertarAlFinal(aux->getDato()); // 末尾に挿入すると元の順序が保たれます
aux = aux->getSiguiente();
}
}
Lista& operator=(const Lista& origin) { // コピー代入:古いノードを解放してからコピーします
if (this != &origin) { // 自己代入から保護します
while (cabeza_ != nullptr) { // リストが既に持つノードを解放します
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 { // ムーブコンストラクタ:元のノードを奪います
cabeza_ = origin.cabeza_;
cola_ = origin.cola_;
n_ = origin.n_;
origin.cabeza_ = nullptr; // 元のリストを空にします
origin.cola_ = nullptr;
origin.n_ = 0;
}
Lista& operator=(Lista&& origin) noexcept { // ムーブ代入:古いノードを解放してから新しいノードを奪います
if (this != &origin) { // 自己代入から保護します
while (cabeza_ != nullptr) { // リストが既に持つノードを解放します
Nodo* borra = cabeza_;
cabeza_ = borra->getSiguiente();
delete borra;
}
cola_ = nullptr;
cabeza_ = origin.cabeza_;
cola_ = origin.cola_;
n_ = origin.n_;
origin.cabeza_ = nullptr; // 元のリストを空にします
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) { // 先頭に挿入: 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) { // 末尾に挿入: cola_ のおかげで O(1)
Nodo* nodo = new Nodo(valor);
n_ += 1;
nodo->setAnterior(cola_);
if (cola_ != nullptr) {
cola_->setSiguiente(nodo);
} else {
cabeza_ = nodo;
}
cola_ = nodo;
}
void imprimirLista() const { // 先頭から末尾へ出力
Nodo* actual = cabeza_;
while (actual != nullptr) {
std::cout << actual->getDato() << " ";
actual = actual->getSiguiente();
}
std::cout << std::endl;
}
void imprimirListaAtras() const { // 末尾から先頭へ出力
Nodo* actual = cola_;
while (actual != nullptr) {
std::cout << actual->getDato() << " ";
actual = actual->getAnterior();
}
std::cout << std::endl;
}
void eliminarNodo(int indice) { // 指定した位置のノードを削除します
if (indice < 0 || indice >= n_) return; // 無効なインデックス:何も起こりません
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() { // リストをその場で反転: 各ノードが anterior_ と siguiente_ を入れ替えます
Nodo* actual = cabeza_;
Nodo* temporal = nullptr;
while (actual != nullptr) {
temporal = actual->getAnterior();
actual->setAnterior(actual->getSiguiente());
actual->setSiguiente(temporal);
actual = actual->getAnterior(); // anterior_ は元の siguiente_ になっています
}
temporal = cabeza_; // 最後に先頭と末尾を入れ替えます
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; // コピー代入(swap なし)
l2.imprimirLista();
l2.imprimirListaAtras();
Lista l3;
l3 = std::move(l1); // ムーブ代入(swap なし)
l3.invertirLista();
l3.imprimirLista();
return 0;
}