1. Basic Framework

At the bottom of list is the leading bidirectional loop chain table, whose basic functions need to be implemented by three class templates (node class, iterator class, and list class).

1. Complete framework of node classes

template<class T>
struct ListNode
{
	// default constructor
	ListNode(const T& x = T())
		:_val(x)
		, _prev(nullptr)
		, _next(nullptr)
	{}

	T _val;             // Stored data
	ListNode<T>* _prev; // Point to the previous node
	ListNode<T>* _next; // Point to the next node
};

2. Basic framework of iterator classes

The iterator of the list class is no longer a native pointer like the string or vector s class, because each node of the list is not continuous in physical space and cannot directly ++ or - - get the iterator of the front and back positions. Because its data is stored in the data domain of the node, it is not possible to get the data directly from the pointer dereference of the node. So we want to encapsulate the pointer of the node to form an iterator class, overloading operators * and operator++ of this class to simulate pointer-like behavior.

template<class T, class Ref, class Ptr>
struct ListIterator
{
	// These template classes are also used in classes, so for brevity, let's redefine the class name here
	typedef ListNode<T> ListNode;
	typedef ListIterator<T, Ref, Ptr> self;

	ListIterator(ListNode* pnode)
	:_node(pnode)  // Initialization list for initialization
	{}

	ListNode* _node;
}

Several explanations of template parameters

3. Basic framework of list class

Because the bottom level of the list class is the leading bidirectional loop chain table, So we just need to know the head node (that is, the data field is invalid, the node with valid pointer field) can get the first node through its _next and the last node through its _prev, which makes it easy to traverse and insert the list. We create a list object whose member variable is the pointer to a header node through which all subsequent operations on the list are done.

template<class T>
class list
{
public:
	typedef ListNode<T> ListNode;
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;

private:
	ListNode* _head;// Save the header node of a list class object
}

Why are member variables of iterator templates and list class templates pointers to nodes and not directly resulting in nodes?

2. list class

1. Related interfaces related to iterator classes

1.1 begin

Function Prototype
iterator begin();
const_iterator begin() const;
Effect
Returns the iterator for the first node of the list class object

// Non-const object returns non-const iterator
iterator begin()
{
    //Construct an iterator object with the first node (that is, the next node of the head node) to return
	return iterator(_head->_next);
}

// A const object returns a const iterator
const_iterator begin() const
{
	return const_iterator(_head->_next);
}

Some explanations of begin

1.2 end

Function Prototype
iterator end();
const_iterator end() const;
Effect
Iterator that returns the head node of a list class object

iterator end()
{
	return iterator(_head);
}

const_iterator end() const
{
	return const_iterator(_head);
}

Supplement: A comparison of being/rbegin and end/rend

2. list Modified Operational Interface

2.1 insert

Function Prototype
iterator insert (iterator position, const value_type& val);
Effect
Insert a node with val ue at the pos iterator position and return the iterator for that node

iterator insert(iterator pos, const T& x)
{
	// Create a new node
	ListNode* pnewnode = new ListNode(x);
	// Gets the address of the node at the iterator location
	ListNode* cur = pos._node;
	// Get the address of the previous node
	ListNode* prev = cur->_prev;
	// Insert New Node
	prev->_next = pnewnode;
	pnewnode->_prev = prev;
	pnewnode->_next = cur;
	cur->_prev = pnewnode;
	// Construct an iterator for this new node and copy the construction to return
	return iterator(pnewnode);
}

• A few notes about insert
  
• Multiplex insert for push_back

void push_back(const T& x)
{
	// Write 1 (Multiplex insert for tail insertion)
	insert(end(), x);

	// Writing II (General Writing)
	ListNode* pnewnode = new ListNode(x);
	ListNode* tail = _head->_prev;
	tail->_next = pnewnode;
	pnewnode->_prev = tail;
	_head->_prev = pnewnode;
	pnewnode->_next = _head;
}

2.2 erase

Function Prototype
iterator erase (iterator position);
Effect
Deletes the specified location node and returns the iterator for the next node

iterator erase(iterator pos)
{
	// Getting the address of a node through an iterator
	ListNode* cur = pos._node;
	// Record before and after nodes to delete
	ListNode* prev = cur->_prev;
	ListNode* next = cur->_next;
	// Delete Node
	delete cur;
	// Connect the original front and back nodes
	prev->_next = next;
	next->_prev = prev;
	// Construct the iterator object for the next node and return
	return iterator(next);
}

• Iterator Failure Analysis for erase and insert
  
• Multiplexing erase for pop_back

void pop_back()
{
	// end is to get to the first node, - - section gets to the last node
	erase(--end());
}

3. Default member functions

3.1 Constructor

list()

Role: Construct an empty list, that is, create only one header node without valid data

A list class member variable has only one pointer to the header node. To create a list class object is to make its member variable_ The header points to a space of node classes that we have manually developed with new. Since there are several forms of constructors, let _ head points to a space, and we have this step implemented in the GreatHeadNode() function.

list()
{
	CreatHeadNode();
}

list (InputIterator first, InputIterator last)

Role: This is a function template that constructs a list from elements in the iterator [first, last] interval (left closed right open) of other list classes.

template <class InputIterator>
list(InputIterator first, InputIterator last)
{
    // Space of the first node
	CreatHeadNode();
	// End element after head node
	while (first != last)
	{
		push_back(*first);// The implementation of the dereferencing operation here is
		++first;
	}
}

3.2 Destructor

// clear is also a member function that cleans up valid nodes of list objects
void clear()
{
	iterator it = begin();
	// Traverse and delete each valid node
	while (it != end())
	{
		delete (it++)._node;
	}
	// Update the header node after all valid nodes have been cleaned up
	_head->_prev = _head;
	_head->_next = _head;
}

// Destructor, reuse clear
~list()
{
	clear();
	// Head Node Release
	delete _head;
	// Make _of list object head points to nullptr
	_head = nullptr;
}

3.3 Copy Construction

list(const list& lt)
:_head(nullptr)
{
	// First Start Node Space
	CreatHeadNode();
	// Construct a temporary object
	list<T> tmp(lt.begin(), lt.end());
	// swap exchange header node using std
	::swap(_head, tmp._head);
}

Some Explanations on Copy Construction

3.4 Assignment overload

list<T>& operator=(list<T> lt)
{
	::swap(_head, lt._head);
	return *this;
}

Some explanations about assigning overloads

3. Iterator class

Let's take a look at the basic framework of iterator classes

template<class T, class Ref, class Ptr>
struct ListIterator
{
	// These template classes are also used in classes, so for brevity, let's redefine the class name here
	typedef ListNode<T> ListNode;
	typedef ListIterator<T, Ref, Ptr> self;

	ListNode* _node;
}

1. Default member function

1.1 Constructor

Only one member variable of the iterator class is a pointer variable to the address of the node_ Node, construct an iterator object to pass the address of the node so that _ Node points to the address of the node.

ListIterator(ListNode* pnode)
:_node(pnode)  // Initialization list for initialization
{}

1.2 Copy Construction

ListIterator(const self& it)
	:_node(it._node)  //Initialize List Initialization
{}

Some Explanations on Copy Construction

2. Pointer Operating Interface

Because of the discontinuity in physical space, the iterator is not a native pointer, and can not get the address of the node to directly dereference, increase or decrease. To accomplish these functions, we encapsulate the pointer to the node, which is now the iterator class.

Before that, let's look at the framework of the node class

template<class T>
struct ListNode
{
	// default constructor
	ListNode(const T& x = T())
		:_val(x)
		, _prev(nullptr)
		, _next(nullptr)
	{}

	T _val;             // Stored data
	ListNode<T>* _prev; // Point to the previous node
	ListNode<T>* _next; // Point to the next node
};

2.1 Unquotation (*)

Returns a reference to a value in a node

Ref operator*()
{
	// Return data from node directly
	return _node->_val;
}

Several explanations for dereferencing

2.2 Arrow Interface (->)

Is the pointer that returns the value in the node

//Readable or not writable depending on the iterator type (determines whether Ptr is const T* or T*)
Ptr operator->()
{
	return &(operator*());
}

2.3 Self-increasing and self-decreasing

// Pre++ (lets the member variable of the iterator object point to the next node and return itself)
self& operator++()
{
	_node = _node->_next;
	return *this;
}

// Postpone ++ (constructs an iterator of it, pointing itself to the next node)
self operator++(int)
{
	self tmp(_node);
	_node = _node->_next;
	return tmp;
}

// Front -.
self& operator--()
{
	_node = _node->_prev;
	return *this;
}

// Rear -.
self operator--(int)
{
	self tmp(_node);
	_node = _node->_prev;
	return tmp;
}

A few explanations about the front and rear

3. Understand the list iterator again

Distinguish the two objects

• Node* pnode
• iterator it

When they all point to the same node, they all store the address of that node in physical memory, which is physically the same. However, if they are of different types, their meanings will also be different, because they determine the right to use space.
For example:
*pnode is a pointer dereference and gets the value of the node itself.

*it is the operator *() that calls this iterator, and the returned value is a reference to the value in this node.

4. Differences between vector s and list s

• vector

Bottom level: dynamically growing arrays
Increase capacity: Open new space, copy data, point to new space

Advantage:

1. Support random access (because it is physically continuous)

Disadvantages:

1. Insertions and deletions in the head or middle require moving the data.
2. Increasing capacity is expensive (opening new space, copying data, freeing up old space, pointing to new space)

• list
  Bottom Level: Lead Two-way Cyclic Chain List
  Compatibility: A node is needed to open a node on the link list.

Advantage:

1. The insertion and deletion time complexity at any location is O(1)
2. Compatibility cost is small

Disadvantages:

1. Random access is not supported and the time complexity to access the node is O(N)