Implementar iterador para una lista doblemente enlazada en C++
Syed Hassan Sabeeh Kazmi
12 octubre 2023
- Usar clases para implementar iterador para una lista doblemente enlazada en C++
- Use nodos para implementar iterador para una lista doblemente enlazada en C++
Como la estructura de datos doblemente enlazada consta de un conjunto de nodos enlazados secuencialmente, los enlaces anterior y siguiente de su nodo inicial y final apuntan a un terminador (normalmente un nodo centinela o nulo) para facilitar el cruce de la lista enlazada. Este tutorial le enseñará cómo implementar un iterador para una lista doblemente enlazada en C++.
En general, la clase de iterador se implementa como un puntero a un nodo de lista enlazada como un elemento nuevo porque pertenece a la clase de lista enlazada como su subclase. Cuatro operaciones principales utilizan la clase de iterador, que incluyen; Asignación de desreferencia, comparación y operaciones de incremento.
Usar clases para implementar iterador para una lista doblemente enlazada en C++
El uso de clases para escribir listas doblemente enlazadas es una práctica excelente porque permite optimizar el iterador y la lista doblemente enlazada. En términos de agregar nuevos elementos a la lista doblemente enlazada, las clases iteradoras son capaces de construir los objetos tipo T.
Además, el compilador de C++ permite la inicialización del iterador mediante la inicialización de una lista simple (como estructura de datos) sin ninguna ayuda manual para especificarla. Además, puede llamar al constructor predeterminado de T cuando crea un objeto Nodo inicializando explícitamente el miembro valor.
Con respecto a este método, la clase iterador acepta/toma dos argumentos, incluido el iterador<T> como objeto iterador y el constT& como elemento a insertar. Devuelve un iterador como resultado al nodo recién insertado.
Como resultado, se crea un nuevo nodo de lista doblemente vinculado, que contiene el elemento constT& como su elemento porque la clase del iterador lo produce y se puede insertar con éxito en la lista vinculada antes de que el iterador lo inserte.
#include <iostream>
// optional: using namespace std;
// template with the `T` typename to manipulate and initialize the variables
template <typename T>
// the `linkedlist_node` class has access to the linked list
class linkedlist_node {
public:
T list_data;
linkedlist_node<T>* node_next;
linkedlist_node() : node_next(nullptr) {}
linkedlist_node(const T& con_listitem,
linkedlist_node<T>* activelist_ptr = nullptr)
: list_data(con_listitem), node_next(activelist_ptr) {}
};
// the `linkedlist_main` is the primary/main linked list class
template <typename T>
class linkedlist_main {
public:
linkedlist_main() {
// creating dummy head and tail nodes
node_head = node_tail = new linkedlist_node<T>();
}
linkedlist_main(const linkedlist_main<T>& other) = delete;
linkedlist_main(linkedlist_main<T>&& other) = delete;
~linkedlist_main() {
while (node_head->node_next != nullptr) {
// build the `node_head` head node from the `listdata_temp`
linkedlist_node<T>* listdata_temp = node_head;
node_head = node_head->node_next;
delete listdata_temp; // delete the temp afterward
}
// empty the `node_head` by removing its content
delete node_head;
}
// delete the `linkedlist_main` contents after a successful insertion or
// creation
linkedlist_main<T>& operator=(const linkedlist_main<T>& other) = delete;
linkedlist_main<T>& operator=(linkedlist_main<T>&& other) = delete;
// the `mainCon_iterator` is an inner class inherited from the
// `linkedlist_main` class it creates an iterator implemented on a
// doubly-linked list
class mainCon_iterator {
friend class linkedlist_main; // inherited from
private: // private elements (restricted access)
linkedlist_node<T>* listnode_ptr; // it's a private node that can only be
// accessed by authorized personnel
// only an authorized person can create instances of iterators because the
// constructor is private
mainCon_iterator(linkedlist_node<T>* newlist_ptrnode)
: listnode_ptr(newlist_ptrnode) {}
public: // public elements (general access)
mainCon_iterator() : listnode_ptr(nullptr) {}
// Overload: comparison operator !=
// create an object from the `mainCon_iterator` and perform the comparison
// operator
bool operator!=(const mainCon_iterator& obj_itr) const {
return listnode_ptr != obj_itr.listnode_ptr; // comparison
}
// Overload: dereference operator *
// pass the node via `operator` object `const`
T& operator*() const {
// access to the `list_node` node
return listnode_ptr->node_next->list_data;
}
// Overload: post-increment operator ++
mainCon_iterator operator++(int) {
mainCon_iterator iterator_temp = *this;
listnode_ptr = listnode_ptr->node_next;
return iterator_temp;
}
}; // end of the `mainCon_iterator` inner class
mainCon_iterator begin() const { return mainCon_iterator(node_head); }
mainCon_iterator end() const { return mainCon_iterator(node_tail); }
mainCon_iterator insert(mainCon_iterator iterator_pos,
const T& itrPos_value) {
linkedlist_node<T>* new_listnode = new linkedlist_node<T>(
itrPos_value, iterator_pos.listnode_ptr->node_next);
if (iterator_pos.listnode_ptr == node_tail) node_tail = new_listnode;
iterator_pos.listnode_ptr->node_next = new_listnode;
return iterator_pos;
}
mainCon_iterator erase(mainCon_iterator iterator_pos) {
linkedlist_node<T>* itrposition_delete =
iterator_pos.listnode_ptr->node_next;
iterator_pos.listnode_ptr->node_next =
iterator_pos.listnode_ptr->node_next->node_next;
if (itrposition_delete == node_tail) node_tail = iterator_pos.listnode_ptr;
delete itrposition_delete;
return iterator_pos;
}
private:
linkedlist_node<T>* node_head;
linkedlist_node<T>* node_tail;
};
int main(int argc, const char* argv[]) {
std::cout
<< "Iterator for the doubly-linked list is successfully implemented!"
<< std::endl;
linkedlist_main<int> list_var;
list_var.insert(list_var.end(), 4);
list_var.insert(list_var.end(), 7);
list_var.insert(list_var.end(), 9);
auto iterator = list_var.begin();
iterator = list_var.insert(iterator, 3);
iterator++;
list_var.insert(iterator++, 6);
iterator++;
list_var.insert(iterator, 2);
iterator = list_var.begin();
iterator++;
list_var.erase(iterator);
for (auto iterator = list_var.begin(); iterator != list_var.end(); iterator++)
std::cout << *iterator << std::endl;
return 0;
}
Producción :
Iterator for the doubly-linked list is successfully implemented!
3
4
7
2
9
Como un iterador puede manipular los datos en la clase de lista enlazada, apunta a un nodo en una lista enlazada que le gustaría borrar, actualizar o crear. El insertar y borrar de la clase iterador pueden resolver este problema, pero esta solución crea otro problema.
El problema es manejar el método begin(), que supone devolver un iterador que apunta al punto de inicio de una lista enlazada. Para manejar este problema, utilizará un nodo principal ficticio antes del nodo de inicio real de la lista, algo así como,
iterator begin() const {return iterator(head);} // to handle begin()
Los operadores de incremento previo ++itr y de incremento posterior itr++ son compatibles con el iterador, y su diferencia se vuelve más clara cuando se utiliza junto con los otros operadores en la misma instrucción en código C++.
Use nodos para implementar iterador para una lista doblemente enlazada en C++
Implica implementar un iterador en una lista doblemente enlazada bastante estándar como una plantilla de C++. Utiliza directivas de compilación condicional en el código de muestra y no contiene fallas graves o de otro tipo que le permitan agregar funciones si desea modificar sus miembros.
C++ admitía los operadores de incremento (pre-incremento ++itr y post-incremento itr++) y requería una convención peculiar para definir o aclarar su naturaleza única al sobrecargarlos en la clase de iterador. Utilice el operador iterador&++() o el operador iterador++(int) respectivamente para el incremento previo o posterior, y puede utilizar return *this; función para realizar incrementos en una expresión compuesta de C++.
#include <ctime>
#include <iostream>
#include <random>
template <typename T>
class linkedlist_main {
private:
struct list_node {
list_node* right_node;
list_node* left_node;
T list_value;
list_node(list_node* listnode_left, const T& listnode_value,
list_node* listnode_right)
: left_node(listnode_left),
list_value(listnode_value),
right_node(listnode_right) {}
list_node(list_node* listnode_left, list_node* listnode_right)
: left_node(listnode_left), right_node(listnode_right) {}
};
public:
class iterator_mainClass;
class con_itr_main : public std::iterator<std::bidirectional_iterator_tag,
list_node, int, list_node*, T> {
friend class linkedlist_main;
friend class iterator_mainClass;
private:
typename con_itr_main::pointer pointer_main;
con_itr_main(typename con_itr_main::pointer pointer_first)
: pointer_main(pointer_first) {}
public:
con_itr_main& operator++() {
pointer_main = pointer_main->right_node;
return *this;
}
con_itr_main& operator--() {
pointer_main = pointer_main->left_node;
return *this;
}
con_itr_main operator++(int) {
typename con_itr_main::pointer type_temp = pointer_main;
pointer_main = pointer_main->right_node;
return type_temp;
}
con_itr_main operator--(int) {
typename con_itr_main::pointer type_temp = pointer_main;
pointer_main = pointer_main->left_node;
return type_temp;
}
typename con_itr_main::reference operator*() {
return pointer_main->list_value;
}
friend bool operator==(const con_itr_main& list_first,
const con_itr_main& list_second) {
return list_first.pointer_main == list_second.pointer_main;
}
friend bool operator!=(const con_itr_main& list_first,
const con_itr_main& list_second) {
return !(list_first == list_second);
}
friend bool operator==(const con_itr_main& pri_iterator,
const iterator_mainClass& itr_ele);
friend bool operator!=(const con_itr_main& pri_iterator,
const iterator_mainClass& itr_ele);
};
class iterator_mainClass
: public std::iterator<std::bidirectional_iterator_tag, const list_node,
int, const list_node*, const T> {
friend class linkedlist_main;
private:
typename iterator_mainClass::pointer pointer_main;
iterator_mainClass(typename iterator_mainClass::pointer pointer_first)
: pointer_main(pointer_first) {}
public:
iterator_mainClass(const con_itr_main& pri_iter)
: pointer_main(pri_iter.pointer_main) {}
iterator_mainClass& operator++() {
pointer_main = pointer_main->right_node;
return *this;
}
iterator_mainClass& operator--() {
pointer_main = pointer_main->left_node;
return *this;
}
iterator_mainClass operator++(int) {
typename iterator_mainClass::pointer death = pointer_main;
pointer_main = pointer_main->right_node;
return death;
}
iterator_mainClass operator--(int) {
typename iterator_mainClass::pointer ordinary = pointer_main;
pointer_main = pointer_main->left_node;
return ordinary;
}
typename iterator_mainClass::reference operator*() {
return pointer_main->list_value;
}
friend bool operator==(const iterator_mainClass& temp_iterator,
const iterator_mainClass& temp_iteratorSec) {
return temp_iterator.pointer_main == temp_iteratorSec.pointer_main;
}
friend bool operator!=(const iterator_mainClass& temp_iterator,
const iterator_mainClass& temp_iteratorSec) {
return !(temp_iterator == temp_iteratorSec);
}
friend bool operator==(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt);
friend bool operator!=(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt);
};
friend bool operator==(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt) {
return primary_itr.pointer_main == primary_itrrator_alt.pointer_main;
}
friend bool operator!=(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt) {
return !(primary_itr == primary_itrrator_alt);
}
linkedlist_main() = default;
template <typename... Types>
linkedlist_main(const T& value, Types&&... values)
: linkedlist_main(values...) {
add_valuetotop(value);
}
linkedlist_main(const linkedlist_main& QEL) { *this = QEL; }
linkedlist_main(iterator_mainClass position_start,
const iterator_mainClass position_end) {
for (; position_start != position_end; position_start++)
this->add_valuetoend(*position_start);
}
linkedlist_main(T&& value) { push_front(value); }
~linkedlist_main() {
this->clear();
delete valueto_end;
}
void delete_lastnode() // deletes the last node
{
list_node* delete_lasttemp = valueto_end;
valueto_end = valueto_end->left_node;
valueto_end->right_node = nullptr;
delete delete_lasttemp;
linkedlist_size--;
}
void delete_firstnode() // deletes the first node
{
list_node* delete_firsttemp = listnode_head;
listnode_head = listnode_head->right_node;
listnode_head->left_node = nullptr;
delete delete_firsttemp;
linkedlist_size--;
}
void add_valuetoend(
const T& linkedlist_addvalue) // adds the value to the end of the list
{
valueto_end = new list_node(valueto_end, nullptr);
valueto_end->left_node->list_value = linkedlist_addvalue;
if (linkedlist_size > 0)
valueto_end->left_node->left_node->right_node = valueto_end->left_node;
valueto_end->left_node->right_node = valueto_end;
linkedlist_size++;
}
void add_valuetotop(const T& linkedlist_addvalue_top) // adds the value to
// the top of the list
{
listnode_head =
new list_node(nullptr, linkedlist_addvalue_top, listnode_head);
listnode_head->right_node->left_node = listnode_head;
linkedlist_size++;
}
void clear() {
list_node* clear_buffer;
// a loop to clear all the linked lists temp obj
for (int temp = 0; temp < linkedlist_size; temp++) {
clear_buffer = listnode_head;
listnode_head = listnode_head->right_node;
delete clear_buffer;
}
listnode_head = valueto_end;
linkedlist_size = 0;
}
void erase(iterator_mainClass
node_current_pos) // deletes the node that the iterator points
// to (the iterator itself becomes hung)
{
if (node_current_pos.pointer_main != listnode_head &&
node_current_pos.pointer_main != valueto_end->left_node) {
node_current_pos.pointer_main->left_node->right_node =
node_current_pos.pointer_main->right_node;
node_current_pos.pointer_main->right_node->left_node =
node_current_pos.pointer_main->left_node;
delete node_current_pos.pointer_main;
linkedlist_size--;
} else if (node_current_pos.pointer_main == listnode_head) {
this->delete_firstnode();
} else {
this->delete_lastnode();
}
}
void erase(iterator_mainClass node_startposition,
const iterator_mainClass
node_endposition) // deletes everything from begin_pos to
// end_pos (end_pos itself is not deleted)
{
while (node_startposition != node_endposition) {
this->erase(node_startposition++);
}
}
// the start of the primary iterator
con_itr_main begin() { return con_itr_main(listnode_head); }
iterator_mainClass con_itr_begin() const {
return iterator_mainClass(listnode_head);
}
// the end-point of the primary iterator
con_itr_main end() { return con_itr_main(valueto_end); }
iterator_mainClass con_itr_end() const {
return iterator_mainClass(valueto_end);
}
T& operator[](unsigned const int& oprIndex_con) const {
if (oprIndex_con > (linkedlist_size - 1) / 2) {
return scroll_node(-(linkedlist_size - 1 - oprIndex_con),
valueto_end->left_node)
->list_value;
} else {
return scroll_node(oprIndex_con, listnode_head)->list_value;
}
}
void operator=(const linkedlist_main& oprQel_var) {
this->clear();
auto iter = oprQel_var.con_itr_begin();
for (; iter != oprQel_var.con_itr_end(); iter++) {
this->add_valuetoend(*iter);
}
}
size_t size() const { return linkedlist_size; }
private:
size_t linkedlist_size = 0;
list_node* valueto_end = new list_node(nullptr, nullptr);
list_node* listnode_head = valueto_end;
list_node* scroll_node(int numIndex_pri, list_node* node_ptr) const {
if (numIndex_pri > 0)
for (int i = 0; i < numIndex_pri; i++) {
node_ptr = node_ptr->right_node;
}
else {
numIndex_pri = abs(numIndex_pri);
for (int i = 0; i < numIndex_pri; i++) {
node_ptr = node_ptr->left_node;
}
}
return node_ptr;
}
};
template <typename S>
linkedlist_main<S> template_sort(const linkedlist_main<S>& new_linkedlist) {
srand(time(NULL));
// in case the linked list exists and isn't null
if (new_linkedlist.size() <= 1) {
return new_linkedlist;
}
linkedlist_main<S> size_minimum;
linkedlist_main<S> size_maximum;
linkedlist_main<S> list_elements;
S list_element = new_linkedlist[rand() % new_linkedlist.size()];
auto opr_iterator = new_linkedlist.con_itr_begin();
for (; opr_iterator != new_linkedlist.con_itr_end(); opr_iterator++) {
if (*opr_iterator > list_element) {
size_maximum.add_valuetoend(*opr_iterator);
} else if (*opr_iterator < list_element) {
size_minimum.add_valuetoend(*opr_iterator);
} else {
list_elements.add_valuetoend(list_element);
}
}
size_minimum = template_sort(size_minimum);
opr_iterator = list_elements.con_itr_begin();
for (; opr_iterator != list_elements.con_itr_end(); opr_iterator++) {
size_minimum.add_valuetoend(*opr_iterator);
}
size_maximum = template_sort(size_maximum);
opr_iterator = size_maximum.con_itr_begin();
for (; opr_iterator != size_maximum.con_itr_end(); opr_iterator++) {
size_minimum.add_valuetoend(*opr_iterator);
}
return size_minimum;
}
template <typename S>
linkedlist_main<S> tempSort_selection(linkedlist_main<S> selection_linkedlist) {
linkedlist_main<int> linkedlist_second;
while (selection_linkedlist.size() > 0) {
auto int_maximum = selection_linkedlist.begin();
auto iterator_main = int_maximum;
for (; iterator_main != selection_linkedlist.end(); iterator_main++)
if (*iterator_main > *int_maximum) int_maximum = iterator_main;
linkedlist_second.add_valuetotop(*int_maximum);
selection_linkedlist.erase(int_maximum);
}
return linkedlist_second;
}
int main() {
linkedlist_main<int> linkedlist_orig(0, 1, 9, 26, 8, 3, 7, 4, 6, 5, 11, 47,
2);
linkedlist_main<int> linkedlist_rev = template_sort(linkedlist_orig);
std::cout << "The original list | Size: " << linkedlist_orig.size()
<< std::endl;
std::cout << "Revised version of the original list: " << linkedlist_rev.size()
<< std::endl;
for (int i = 0; i < linkedlist_rev.size(); i++)
std::cout << linkedlist_rev[i] << std::endl;
linkedlist_main<int> linkedlist_sec(tempSort_selection(
linkedlist_main<int>(5, 67, 4, 7, 3, 8, 2, 9, 1, 22, 54, 6)));
std::cout << "The sorted list: " << linkedlist_sec.size() << std::endl;
for (int info = 0; info < linkedlist_sec.size(); info++)
std::cout << linkedlist_rev[info] << std::endl;
std::cout << clock() / static_cast<double>(CLOCKS_PER_SEC) << std::endl;
return 0;
}
Producción :
The original list | Size: 13
Revised version of the original list: 13
0
1
2
3
4
5
6
7
8
9
11
26
47
The sorted list: 12
0
1
2
3
4
5
6
7
8
9
11
26
0
En conclusión, la lista doblemente enlazada requiere espacio y memoria adicionales para almacenar punteros y hacer que la búsqueda sea eficiente. También es muy eficiente implementar los iteradores cuando la limitación de su memoria no es un problema.
Autor: Syed Hassan Sabeeh Kazmi
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub