Simulate the realization of List container (C++)

overview

List Container Framework

List simulation implementation

ListNode node class

MyList structure

No parameter construction

List iterator

Complete MyList class definition

Insert to insert data

Erase delete data

Push to insert data

Pop delete data

other functions

ClearClear data

destructor

Test code MyList.cpp

Complete code MyList.hpp

---

Overview

Learned from the blogger: (84 messages) [C + +] teach you how to write your own list class_Ornamrr’s Blog-CSDN Blog

List container frame

The underlying data structure of the List container is actually a leading two-way circular linked list. The frame structure is shown in the figure:

List simulation implementation

ListNode node class

In the underlying structure, the node is the basic unit, first we need to define the template of the node class:

 node template
template<class T>
class ListNode {
public:
ListNode<T>* _prev;
T_val;
ListNode<T>* _next;

ListNode(const T & val) : _prev(nullptr), _val(val), _next(nullptr){}
};

MyList structure

After defining the node class, we need to clarify the implementation logic of the List container: the List container mainly maintains a head node pointer to access the entire linked list:

No parameter construction

From the above structure, the MyList class can be designed and initialized:

///The implementation of the list template class maintains a head node pointer, and the head is only used for connection and does not store data
template<class T>
class MyList {
typedef ListNode<T> Node;
private:
Node* _head;
public:
// no parameter construction
MyList() {//leading node, not practical
_head = new Node(0);
_head->_next = _head;
_head->_prev = _head;
}
}

List Iterator

In the standard template library STL, each container has its unique iterator, and the iterator of the List container is essentially a node pointer, and because the List iterator is more complicated than the vector container , it is encapsulated here, and the operators that may be used are overloaded:

The definition of

/list iterator is not just a simple type pointer, its next position is _next
template<class T>
struct _list_iterator//parameter template Ref, pointer template Ptr
{
typedef _list_iterator<T> self;
typedef ListNode<T> Node;

Node* _node;

\t//Constructor
_list_iterator(Node* node)
:_node(node)
{}
//overload dereference
T operator*()
{
return _node->_val;
}
// Overload ++ and --
self operator + + ()
{
this->_node = this->_node->_next;
return *this;
}
self operator--()
{
this->_node = this->_node->_prev;
return *this;
}
// Overload == and ! =
bool operator==(const self & amp; it) const {
return _node == it._node;
}

bool operator!=(const self & amp; it) const {
return _node != it._node;
}
};

Complete MyList class definition

///The implementation of the list template class maintains a head node pointer, and the head is only used for connection and does not store data
template<class T>
class MyList {
typedef ListNode<T> Node;
typedef _list_iterator<T> list_iterator;
private:
Node* _head;
public:
// no parameter construction
MyList() {//leading node, not practical
_head = new Node(0);
_head->_next = _head;
_head->_prev = _head;
}
// copy construction
MyList(MyList<T> & Lt) {
_head = new Node(0);
_head->_next = _head;
_head->_prev = _head;
Node* cur = Lt._head->_next;
while (cur != Lt._head) {
this->push_back(cur->_val);
cur = cur->_next;
}
}
// overload assignment
MyList<T> & amp; operator=(MyList<T> & amp; Lt) {
this->_head = Lt._head;
return *this;
}
\t
//member function
void push_back(T val);
void push_front(T val);
void pop_back();
void pop_front();
void insert(list_iterator pos, T val);
void erase(list_iterator pos);
int size();
bool empty();
T front();//Get the head element
T back();//Get the tail element
void clear();//Clear all nodes except the head node

//Simulation of iterator iterator head and tail iterator
list_iterator begin() {//Insert the node at the previous position insert header and tail insert
return _head->_next;//The actual head position
}
list_iterator end() {
return _head;//The next position of the tail is the head
}

//destructor
~MyList() {
this->clear();//Release other nodes
delete _head;//Release the head node
_head = NULL;
}
};

Insert insert data

The insertion here is to insert the node at the previous position of pos position, head insertion and tail insertion are also applicable, and the operation logic is as shown in the figure:

template<class T>
void MyList<T>::insert(list_iterator pos, T val) {
Node* prev = pos._node->_prev;
Node* new_node = new Node(val);
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = pos._node;
pos._node->_prev = new_node;
}

Erase delete data

Note the position of the head node:

template<class T>
void MyList<T>::erase(list_iterator pos) {
if (_head->_next == _head) {
cout << "The deletion has been completed and cannot be deleted again!!" << endl;
return;
}
if (pos._node == _head) {//Prevent deleting the head
Node* prev = pos._node->_prev;
Node* pprev = prev->_prev;
pprev->_next = _head;
_head->_prev = pprev;
return;
}
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
}

Push insert data

It can be realized by analysis, or directly by using Insert:

template<class T>
void MyList<T>::push_back(T val) {
//Node* tail = _head->_prev;
//Node* new_node = new Node(val);

//tail->_next = new_node;
//new_node->_prev = tail;
//new_node->_next = _head;
//_head->_prev = new_node;

this->insert(this->end(), val);
}

template<class T>
void MyList<T>::push_front(T val) {
//Node* next = _head->_next;
//Node* new_node = new Node(val);

//new_node->_next = next;
//next->_prev = new_node;
//new_node->_prev = _head;
//_head->_next = new_node;
this->insert(this->begin(), val);
}

Pop delete data

It can be achieved by analysis, or directly by using Erase:

template<class T>
void MyList<T>::pop_back() {
/*if (_head->_next == _head) {
cout << "The deletion has been completed and cannot be deleted again!!" << endl;
return;
}
Node* tail = _head->_prev;
Node* tailprev = tail->_prev;
delete tail;
tail = NULL;
tailprev->_next = _head;
_head->_prev = tailprev;*/
this->erase(this->end());
}

template<class T>
void MyList<T>::pop_front() {
/*if (_head->_next == _head) {
cout << "The deletion has been completed and cannot be deleted again!!" << endl;
return;
}
Node* front = _head->_next;
Node* next = front->_next;
delete front;
_head->_next = next;
next->_prev = _head;*/
this->erase(this->begin());
}

Other functions

template<class T>
int MyList<T>::size() {
int count = 0;
Node* cur = _head->_next;
while (cur != _head) {
count + + ;
cur = cur->_next;
}
return count;
}

template<class T>
bool MyList<T>::empty() {
return this->size() == 0;
}

template<class T>
T MyList<T>::front() {
return _head->_next->_val;
}

template<class T>
T MyList<T>::back() {
return _head->_prev->_val;
}

Clear clear data

Clear data, freeing all nodes except the head node:

template<class T>
void MyList<T>::clear() {
//Release all nodes except the head node
while (_head->_next != _head) {
this->erase(this->begin());
}
}

Destructor

Release all nodes:

//destructor
template<class T>
MyList<T>::~MyList() {
this->clear();//Release other nodes
delete _head;//Release the head node
_head = NULL;
}

Test code MyList.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "MyList.hpp"

int main() {
MyList<int> lt;//No parameter construction
lt.push_back(1);//tail plug
lt. push_back(2);
lt.push_back(3);
lt. push_back(4);
lt. push_back(5);

lt.push_front(6);//head plug
lt.push_front(7);
lt.push_front(8);

lt.pop_back();//tail deletion
lt. pop_back();

lt.pop_front();//head delete
lt. pop_front();

MyList<int> lt1(lt);//copy construction

MyList<int> lt2 = lt;//Assignment operation

lt.insert(lt.begin(), 9);//insert test
lt.insert(lt.end(), 10);

cout << "size = " << lt. size() << endl;
cout << "front = " << lt. front() << endl;
cout << "back = " << lt.back() << endl;
cout << "empty = " << lt.empty() << endl;

for (_list_iterator<int> it = lt.begin(); it != lt.end(); + + it) {
cout << *it << " ";
}
cout << endl;
cout << endl;

lt.erase(lt.begin());//delete test
lt.erase(lt.end());

lt.clear();//clear test
cout << "After cleaning: " << endl;
cout << "empty = " << lt.empty() << endl;


return 0;
}

Complete code MyList.hpp

#pragma once
#include 

using namespace std;

//The use of class templates requires the function declaration and implementation to be written in a file,
//And the file suffix is changed to .hpp, and the header file is included when used.

/C ++ implements list with a headed doubly linked list

node template
template
class ListNode {
public:
ListNode* _prev;
T_val;
ListNode* _next;

ListNode(const T & val) : _prev(nullptr), _val(val), _next(nullptr){}
};

The definition of /list iterator is not just a simple type pointer, its next position is _next
template<class T>
struct _list_iterator//parameter template Ref, pointer template Ptr
{
typedef _list_iterator<T> self;
typedef ListNode<T> Node;

Node* _node;

\t//Constructor
_list_iterator(Node* node)
:_node(node)
{}
//overload dereference
T operator*()
{
return _node->_val;
}
// Overload ++ and --
self operator + + ()
{
this->_node = this->_node->_next;
return *this;
}
self operator--()
{
this->_node = this->_node->_prev;
return *this;
}
// Overload == and ! =
bool operator==(const self & amp; it) const {
return _node == it._node;
}

bool operator!=(const self & amp; it) const {
return _node != it._node;
}
};

///The implementation of the list template class maintains a head node pointer, and the head is only used for connection and does not store data
template<class T>
class MyList {
typedef ListNode<T> Node;
typedef _list_iterator<T> list_iterator;
private:
Node* _head;
public:
// no parameter construction
MyList() {//leading node, not practical
_head = new Node(0);
_head->_next = _head;
_head->_prev = _head;
}
// copy construction
MyList(MyList<T> & Lt) {
_head = new Node(0);
_head->_next = _head;
_head->_prev = _head;
Node* cur = Lt._head->_next;
while (cur != Lt._head) {
this->push_back(cur->_val);
cur = cur->_next;
}
}
// overload assignment
MyList<T> & amp; operator=(MyList<T> & amp; Lt) {
this->_head = Lt._head;
return *this;
}
\t
//member function
void push_back(T val);
void push_front(T val);
void pop_back();
void pop_front();
void insert(list_iterator pos, T val);
void erase(list_iterator pos);
int size();
bool empty();
T front();//Get the head element
T back();//Get the tail element
void clear();//Clear all nodes except the head node

//Simulation of iterator iterator head and tail iterator
list_iterator begin() {//Insert the node at the previous position insert header and tail insert
return _head->_next;//The actual head position
}
list_iterator end() {
return _head;//The next position of the tail is the head
}

//destructor
~MyList() {
this->clear();//Release other nodes
delete _head;//Release the head node
_head = NULL;
}
};

template<class T>
void MyList<T>::push_back(T val) {
//Node* tail = _head->_prev;
//Node* new_node = new Node(val);

//tail->_next = new_node;
//new_node->_prev = tail;
//new_node->_next = _head;
//_head->_prev = new_node;

this->insert(this->end(), val);
}

template<class T>
void MyList<T>::push_front(T val) {
//Node* next = _head->_next;
//Node* new_node = new Node(val);

//new_node->_next = next;
//next->_prev = new_node;
//new_node->_prev = _head;
//_head->_next = new_node;
this->insert(this->begin(), val);
}

template<class T>
void MyList<T>::pop_back() {
/*if (_head->_next == _head) {
cout << "The deletion has been completed and cannot be deleted again!!" << endl;
return;
}
Node* tail = _head->_prev;
Node* tailprev = tail->_prev;
delete tail;
tail = NULL;
tailprev->_next = _head;
_head->_prev = tailprev;*/
this->erase(this->end());
}

template<class T>
void MyList<T>::pop_front() {
/*if (_head->_next == _head) {
cout << "The deletion has been completed and cannot be deleted again!!" << endl;
return;
}
Node* front = _head->_next;
Node* next = front->_next;
delete front;
_head->_next = next;
next->_prev = _head;*/
this->erase(this->begin());
}

template<class T>
void MyList<T>::insert(list_iterator pos, T val) {
Node* prev = pos._node->_prev;
Node* new_node = new Node(val);
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = pos._node;
pos._node->_prev = new_node;
}

template<class T>
void MyList<T>::erase(list_iterator pos) {
if (_head->_next == _head) {
cout << "The deletion has been completed and cannot be deleted again!!" << endl;
return;
}
if (pos._node == _head) {//Prevent deleting the head
Node* prev = pos._node->_prev;
Node* pprev = prev->_prev;
pprev->_next = _head;
_head->_prev = pprev;
return;
}
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
}

template<class T>
int MyList<T>::size() {
int count = 0;
Node* cur = _head->_next;
while (cur != _head) {
count + + ;
cur = cur->_next;
}
return count;
}

template<class T>
bool MyList<T>::empty() {
return this->size() == 0;
}

template<class T>
T MyList<T>::front() {
return _head->_next->_val;
}

template<class T>
T MyList<T>::back() {
return _head->_prev->_val;
}

template<class T>
void MyList<T>::clear() {
//Release all nodes except the head node
while (_head->_next != _head) {
this->erase(this->begin());
}
}