Implementieren Sie Iterator für eine doppelt verkettete Liste in C++
- Verwenden Sie Klassen, um Iterator für eine doppelt verknüpfte Liste in C++ zu implementieren
- Verwenden Sie Knoten, um Iterator für eine doppelt verknüpfte Liste in C++ zu implementieren
Da die doppelt verknüpfte Datenstruktur aus einem Satz sequentiell verknüpfter Knoten besteht, zeigen die vorherigen und nächsten Verknüpfungen ihres Anfangs- und Endknotens auf einen Terminator (typischerweise ein Sentinel-Knoten oder null), um das Durchlaufen der verknüpften Liste zu erleichtern. In diesem Tutorial lernen Sie, wie Sie einen Iterator für eine doppelt verknüpfte Liste in C++ implementieren.
Im Allgemeinen wird die Iterator-Klasse als Zeiger auf einen Linked-List-Knoten als neues Element implementiert, da sie als Unterklasse zu der Linked-List-Klasse gehört. Vier primäre Operationen verwenden die Iterator-Klasse, einschließlich; Dereferenzierungszuweisung, Vergleich und Inkrementoperation.
Verwenden Sie Klassen, um Iterator für eine doppelt verknüpfte Liste in C++ zu implementieren
Die Verwendung von Klassen zum Schreiben doppelt verketteter Listen ist eine ausgezeichnete Praxis, da Sie damit den Iterator und die doppelt verkettete Liste optimieren können. In Bezug auf das Hinzufügen neuer Elemente zur doppelt verknüpften Liste sind die Iteratorklassen in der Lage, die Objekte vom Typ T zu erstellen.
Darüber hinaus ermöglicht der C++-Compiler die Iteratorinitialisierung unter Verwendung einer einfachen Listeninitialisierung (als Datenstruktur) ohne manuelle Hilfe, um sie zu spezifizieren. Darüber hinaus können Sie den Standardkonstruktor von T aufrufen, wenn Sie ein Node-Objekt erstellen, indem Sie explizit das value-Mitglied initialisieren.
In Bezug auf diese Methode akzeptiert/nimmt die Iterator-Klasse zwei Argumente, einschließlich des iterator<T> als Iterator-Objekt und des constT& als einzufügendes Element. Er gibt als Ergebnis einen Iterator an den neu eingefügten Knoten zurück.
Als Ergebnis wird ein neuer doppelt verketteter Listenknoten erstellt, der als Element das Item constT& enthält, weil es von der Iteratorklasse produziert wird und vor jedem Einfügen durch den Iterator erfolgreich in die verkettete Liste eingefügt werden kann.
#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;
}
Ausgang:
Iterator for the doubly-linked list is successfully implemented!
3
4
7
2
9
Da ein Iterator die Daten in der Linked-List-Klasse manipulieren kann, zeigt er auf einen Knoten in einer Linked-List, den Sie löschen, aktualisieren oder erstellen möchten. Das insert und erase aus der Iterator-Klasse kann dieses Problem lösen, aber diese Lösung erzeugt ein anderes Problem.
Das Problem besteht darin, die Methode begin() zu handhaben, die einen Iterator zurückgeben soll, der auf den Startpunkt einer verknüpften Liste zeigt. Um dieses Problem zu lösen, verwenden Sie vor dem eigentlichen Startknoten der Liste einen Dummy-Kopfknoten, etwa so:
iterator begin() const {return iterator(head);} // to handle begin()
Die Prä-Inkrement-Operatoren ++itr und Post-Inkrement-Operatoren itr++ werden vom Iterator unterstützt, und ihr Unterschied wird deutlicher, wenn sie zusammen mit den anderen Operatoren in derselben Anweisung im C++-Code verwendet werden.
Verwenden Sie Knoten, um Iterator für eine doppelt verknüpfte Liste in C++ zu implementieren
Es beinhaltet die Implementierung eines Iterators für eine ziemlich standardmäßige doppelt verknüpfte Liste als C++-Vorlage. Es verwendet bedingte Kompilierungsdirektiven im Beispielcode und enthält keine schwerwiegenden oder anderen Fehler, die es Ihnen ermöglichen, Funktionen hinzuzufügen, wenn Sie seine Mitglieder ändern möchten.
C++ unterstützte die Inkrementoperatoren (Prä-Inkrement ++itr und Post-Inkrement itr++) und erforderte eine besondere Konvention, um ihre einzigartige Natur zu definieren oder zu verdeutlichen, indem sie in der Iteratorklasse überladen wurden. Verwenden Sie den iterator& operator++() bzw. den iterator operator++(int) für Pre- oder Post-Increment, und Sie können den return *this; Funktion zum Ausführen von Inkrementen in einem zusammengesetzten C++-Ausdruck.
#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;
}
Ausgang:
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
Zusammenfassend erfordert die doppelt verknüpfte Liste zusätzlichen Platz und Speicher, um Zeiger zu speichern und die Suche effizient zu gestalten. Es ist auch sehr effizient, die Iteratoren zu implementieren, wenn die Beschränkung ihres Speichers kein Problem darstellt.
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