# preface

In the previous section, we briefly described the concept of list, knew that its bottom layer is a two-way circular linked list of leading nodes, and introduced its use method, * * but** We should not only know how to use it, but also try how to implement it simply

Therefore, in this article, bloggers will simply implement the bottom layer from all directions of the list, including: two constructors, data head and tail deletion and interpolation, iterator implementation, etc;

# Structure construction of list

template <class T> // Node creation struct __list_node { __list_node* _next; __list_node* _prev; T _val; __list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){} }; template <class T> // list structure construction class list { public: typedef __list_node<T> node; //Remember to have < T > private: node* _head; };

# Two constructors

The two building functions mentioned here are Default building function and iterator interval building function

## ① Default build function

When the blogger explained c + + classes and objects in the previous chapter, you must already know what happened to the default construction. The blogger will not repeat it here. Let's start the implementation directly

list() { _head = new node; // Open up a space for the head node _head->_next = _head; _head->_prev = _head; }

## ② Iterator interval construction function

In the previous chapters on string and vector, bloggers have demonstrated its use, but how to implement it?

template <class InputIterator, class OutputIterator> list(InputIterator input,OutputIterator output) { //Note ~, you can't write list(), mistakenly thinking it's a function call, because list itself is a class, so it's an anonymous object _head = new node; // Open up a space for the head node _head->_next = _head; _head->_prev = _head; while(input != output) { push_back(*input); //This function is used to implement tail interpolation data. Bloggers will explain it below input++; } }

# copy constructor

For copy construction, we can reuse push directly_ back();

list(const list<T>& lt) { _head = new Node; // You must first open the header node space ~ ~, because this is a copy structure, not an assignment _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); //This function will be implemented later } }

# Assignment overload

list<T>& operator=(const list<T> lt) // Note that the parameters here deliberately do not use references. In this way lt, the value is obtained through the copy structure { swap(_head, lt._head); //Then exchange the head nodes of the two linked lists return *this; }

# Head and tail deletion and interpolation of data

There are four main types of head and tail deletion and insertion, namely push_back(),pop_back(),push_front(),pop_front(), now the blogger will roughly implement it

## ① Tail plug push_back()

In learning the double linked list chapter, remember how the data is connected?

- Create a new node for the data
- Save tail node
- Tail node and new node connection
- New node and head node connection

void push_back(const T& val) { node* tmp = new node(val); //Create a new node for new data node* tail = _head->_prev; //Save tail node tail->_next = tmp; tmp->_prev = tail; //Tail node and new node connection _head->_prev = tmp; tmp->_next = _head; //Header node and new data connection }

Test results:

## ② Tail deletion pop_back()

Similarly, remember the steps of deleting the tail node?

- Save the previous node of the tail node
- Release tail node
- The header node is connected to the saved node

void pop_back() { assert(_head != _head->_next); //If the data is empty, it cannot be deleted node* oldtail = _head->_prev; //Extract old tail node node* newtail = oldtail->_prev; //Save the previous node of the old tail node delete oldtail; oldtail = nullptr; _head->_prev = newtail; newtail->_next = _head; }

Test:

## ③ Head insert push_front()

Do you still remember the steps of inserting the head?

- Create a new node for the new data
- Save the next node of the header node
- The header node is connected to the new data node
- New node and saved node connection

void push_front(const T& val) { node* tmp = new node(val); //Create a new node for the new data node* next = _head->_next; //Save the next node of the header node _head->_next = tmp; tmp->_prev = _head; //The header node is connected to the new data node tmp->_next = next; next->_prev = tmp; //New node and saved node connection }

Test results:

## ④ Header deletion pop_front()

Do you still remember the steps of header deletion?

- Save the two nodes under the header node
- Release the head node to the next node
- Head node and save node connection

void pop_front() { assert(_head != _head->_next); //If the data is empty, it cannot be deleted node* dnext = _head->_next->_next; delete _head->_next; _head->_next = dnext; dnext->_prev = _head; }

Test results:

# Implementation of iterator

Unlike the previous two sections, bloggers have always stressed that iterators can be used as pointers at this stage because pointers naturally support *, +, -, + +, -, <, > and other operations, and iterators are also used in this way, which has the same effect as pointers. However, today bloggers will emphasize that iterators can not be used as pointers here, because we want to implement iterators of lists, List is a leading two-way circular linked list. If we add or subtract node pointers, it is meaningless because we can't use * to access elements

So since we can no longer regard iterators as pointers, how can we implement them? The answer is to encapsulate the node pointer and then overload the operator

Now let's look at what the iteration needs to do:

- ++Represents the next position of the data. Bloggers only realize the front position here++
- – represents the last position of the data, and bloggers only realize the front –
- *****Represents the element that gets the iterator location
- != Determine whether the positions of the two iterators are different
- ==Determine whether the positions of the two iterators are the same

Now that you know the requirements, you can start implementing them

template<class T> struct __list_iterator { typedef __list_iterator<T> iterator; //iterator typedef __list_node<T> node; //The linked list node has been defined above node* _node; __list_iterator(node* pnode):_node(pnode) {} T& operator*() //The iterator uses * to get the node value, so it dereferences directly_ Node, and then return { return _node->_val; } iterator& operator++() //++It means that the iterator moves backward one position, but it is still an iterator after moving, so the return value is still iterator { _node = _node->_next; return *this; } iterator& operator--() //--It means that the iterator moves forward one position, but it is still the iterator after moving, so the return value is still the iterator { _node = _node->_prev; return *this; } bool operator!=(const iterator & target) const //To judge whether the iterators are equal is to judge whether the positions are equal_ node { return _node != target._node; } bool operator==(const iterator & target) const //To judge whether the iterators are equal is to judge whether the positions are equal_ node { return _node == target._node; } };

So far, it seems that almost all functions have been realized, but is it really so? Take a closer look, we also ignore the constant iterator (representing that the node value cannot be modified). What should we do? According to the previous implementation of string and vector, the first idea may be to redefine an iterator. Is this idea wrong? The answer is no mistake, but there is a simpler way, that is to give__ list_iterator adds one more parameter, which is defined as follows:

template <class T,class Ref> class __list_iterator {};

Therefore, when we implement other interfaces in the list, we should first name the iterator:

typedef __list_iterator<T,T&> iterator; //Ordinary iterator typedef __list_iterator<T,const T&> const_iterator; //Constant iterator

Now that the parameter problem has been modified, where does the second parameter apply? Answer: operator *, because the constant iterator only affects whether the data value can be modified; Revised as follows:

Ref operator*() //If it is an ordinary iterator, Ref is t&. If it is a constant iterator, Ref is const t& { return _node->_val; }

So, after that, do you still think we have completed the simple implementation? However, the fact is that we still ignore one detail: if we store a structure, that is, T is a structure, suppose that the structure is defined as follows:

struct Date { int _year; int _month; };

Then we store the structure as follows:

Date date[10]; list<Date> li(date,date+10);

Then, how do we get the elements of the structure with the iterator?

list<Date>::iterator it_b = li.begin(); list<Date>::iterator it_e = li.end(); while(it_b != it_e) { cout<<(*it_b)._year; //Do you want to use three operators? They are * () }

That is, through the above, we need to use three operators * ()

Can we use - > directly? If we want to use - >, we need to * * treat the iterator as a pointer to the structure (see below - > overloaded return value) * *, so we need to set another parameter

template <class T,class Ref,class Ptr> class __list_iterator {};

Where Ptr is the pointer to T

Then we can define the iterator name inside the list like this

typedef __list_iterator<T,T&,T*> iterator; //Ordinary iterator typedef __list_iterator<T,const T&,const T*> const_iterator; //Constant iterator

We also need to overload the - > operator in the iterator

Ptr operator->() { return &(_node->_val); //This must be the address of the return structure!!!, This is explained below }

Now let's assume that there is a list iterator it, and we want to access the data of the Date structure_ How to write the year value? The answer is: it - > - >_ But does that look awkward? Awkward Therefore, the compiler helps us optimize, so we just need to write it - > year

At this point, a complete list iterator is completed!!!

template <class T,class Ref,class Ptr> struct __list_iterator { typedef __list_iterator<T> iterator; //iterator typedef __list_node<T> node; //The linked list node has been defined above node* _node; __list_iterator(node* pnode):_node(pnode) {} Ref operator*() //The iterator uses * to get the node value, so it dereferences directly_ Node, and then return { return _node->_val; } Ptr operator->() { return &(_node->_val); } iterator& operator++() //++It means that the iterator moves backward one position, but it is still an iterator after moving, so the return value is still iterator { _node = _node->_next; return *this; } iterator& operator--() //--It means that the iterator moves forward one position, but it is still the iterator after moving, so the return value is still the iterator { _node = _node->_prev; return *this; } bool operator!=(const iterator & target) const //To judge whether the iterators are equal is to judge whether the positions are equal_ node { return _node != target._node; } bool operator==(const iterator & target) const //To judge whether the iterators are equal is to judge whether the positions are equal_ node { return _node == target._node; } };

# Iterator Interface

We mainly use four (two ordinary and two constant iterations)

iterator begin() { return iterator(_head->_next); } iterator end() {return iterator(_head);} const_iterator begin() const { return iterator(_head->_next); } const_iterator end() const { return iterator(_head); }

# Clear

Note that this cleanup will only clear the data after the header node, not even the header node

void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }

# Destructor

~list() { clear(); //Be sure to release the data behind the header node first delete _head; _head = nullptr; }

# The implementation of erase and insert and simplify the deletion of head and tail data

The implementation of erase, the parameter is iterator

iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; prev->_next = next; next->_prev = prev; return iterator(next); }

The implementation of insert, the parameter is the iterator plus data

iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode); }

So can we simplify the deletion and insertion of data?

void push_back(const T& x) {insert(end(), x);} void push_front(const T& x) {insert(begin(), x);} void pop_back() {erase(--end());} void pop_front() {erase(begin());}

# Final list code

template <class T> // Node creation struct __list_node { __list_node* _next; __list_node* _prev; T _val; __list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){} }; template <class T,class Ref,class Ptr> struct __list_iterator { typedef __list_iterator<T> iterator; //iterator typedef __list_node<T> node; //The linked list node has been defined above node* _node; __list_iterator(node* pnode):_node(pnode) {} Ref operator*() //The iterator uses * to get the node value, so it dereferences directly_ Node, and then return { return _node->_val; } Ptr operator->() { return &(_node->_val); } iterator& operator++() //++It means that the iterator moves backward one position, but it is still an iterator after moving, so the return value is still iterator { _node = _node->_next; return *this; } iterator& operator--() //--It means that the iterator moves forward one position, but it is still the iterator after moving, so the return value is still the iterator { _node = _node->_prev; return *this; } bool operator!=(const iterator & target) const //To judge whether the iterators are equal is to judge whether the positions are equal_ node { return _node != target._node; } bool operator==(const iterator & target) const //To judge whether the iterators are equal is to judge whether the positions are equal_ node { return _node == target._node; } }; template <class T> // list structure construction class list { public: list() { _head = new node; // Open up a space for the head node _head->_next = _head; _head->_prev = _head; } template <class InputIterator, class OutputIterator> list(InputIterator input,OutputIterator output) { //Note ~, you can't write list(), mistakenly thinking it's a function call, because list itself is a class, so it's an anonymous object _head = new node; // Open up a space for the head node _head->_next = _head; _head->_prev = _head; while(input != output) { push_back(*input); //This function is used to implement tail interpolation data. Bloggers will explain it below input++; } } iterator begin() { return iterator(_head->_next); } iterator end() {return iterator(_head);} const_iterator begin() const { return iterator(_head->_next); } const_iterator end() const { return iterator(_head); } list(const list<T>& lt) { _head = new Node; // You must first open the header node space ~ ~, because this is a copy structure, not an assignment _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); //This function will be implemented later } } list<T>& operator=(const list<T> lt) // Note that the parameters here deliberately do not use references. In this way lt, the value is obtained through the copy structure { swap(_head, lt._head); //Then exchange the head nodes of the two linked lists return *this; } ~list() { clear(); //Be sure to release the data behind the header node first delete _head; _head = nullptr; } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode); } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; prev->_next = next; next->_prev = prev; return iterator(next); } void push_back(const T& x) {insert(end(), x);} void push_front(const T& x) {insert(begin(), x);} void pop_back() {erase(--end());} void pop_front() {erase(begin());} private: node* _head; };