Interface Overview

namespace NZB
{
	// Simulation Implementation of list node
	template<class T>
	struct _list_node
	{
		_list_node(const T& val = T()); // Construction node

		//Member variable
		T _val;                 // data
		_list_node<T>* _next;   // Backward pointer
		_list_node<T>* _prev;   // Forward pointer
	};

	// Analog implementation of list iterator
	template<class T, class Ref, class Ptr>
	struct _list_iterator
	{
		typedef _list_node<T> node;// rename
		typedef _list_iterator<T, Ref, Ptr> self;

		_list_iterator(node* pnode);  // Constructor

		// Operator overloading 
		self operator++();
		self operator--();
		self operator++(int);
		self operator--(int);
		bool operator==(const self& s) const;
		bool operator!=(const self& s) const;
		Ref operator*();
		Ptr operator->();

		node* _pnode; // Pointer to node
	};

	// Simulation implementation list
	template<class T>
	class list
	{
	public:
		typedef _list_node<T> node;
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		// Default member function
		list();
		list(const list<T>& lt);
		list<T>& operator=(const list<T>& lt);
		~list();

		// Iterator correlation function
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		// Accessing container related functions
		T& front();
		T& back();
		const T& front() const;
		const T& back() const;

		// Insert and delete functions
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void push_back(const T& x);
		void pop_back();
		void push_front(const T& x);
		void pop_front();

		// Other functions
		size_t size() const;
		void clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		node* _head; //Pointer to the chain header node
	};
}

Simulation Implementation of list node

The bottom layer of list is actually a two-way circular linked list

To implement list, we first need to implement its node class. From the figure, we can see that the member variables of each node are: variables that store data, pointers to the previous node and pointers to the next node.

In order to facilitate the creation of new nodes, member functions are also needed to construct nodes.

template<class T>
struct _list_node
{
	_list_node(const T& val = T()) // Construction node
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}

	//Member variable
	T _val;                 // data
	_list_node<T>* _next;   // Backward pointer
	_list_node<T>* _prev;   // Forward pointer
};

Note: when the construction node does not pass in data, use the value constructed by the list default constructor

Simulation Implementation of list iterator

The function of iterator is to allow users to access the data in the container in a simple and unified way without caring about the underlying implementation of the container.

Unlike string and vector iterators, list iterators store continuous data. Their iterators are similar to pointers, but the data stored in list class is random and cannot be accessed by adding and subtracting pointers.

In order to make the list meet the requirements of the iterator, we encapsulate the list node and overload various operator operations of the node pointer.

Template parameter description of iterator class

Why are there three template parameters in the template parameter list?

template<class T, class Ref, class Ptr>

In the simulated implementation of list, we typedef two iterator types, ordinary iterator and const iterator.

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

Ref and Ptr in the template parameter list of the iterator class represent reference type and pointer type respectively.

When we use ordinary iterators, the compiler instantiates an ordinary iterator object; When we use const iterators, the compiler instantiates a const iterator object.

Constructor

There is only one member variable in the iterator, that is, the node pointer. When constructing, you can directly construct an iterator object for the pointer

_list_iterator(node* node)
:_node(node)
{}

++Overloading of operators

Pre + +:

Point the node pointer to the next node, and then return the node after self increment

self& operator++()
{
	_node = _node->_next;
	return *this;
}

Post + +:

First record the node pointed to by the current pointer, then point the node pointer to the next node, and return the node before self increment

self operator++(int)
{
	self tmp(*this);
	_node = _node->_next;
	return tmp;
}

-- overloading of operators

Front --:

Point the node pointer to the previous node, and then return the node after self subtraction

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

Post --:

First record the node pointed by the current pointer, then point the node pointer to the previous node, and return the node before self subtraction

self operator--(int)
{
	self tmp(*this);
	_node = _node->_prev;
	return tmp;
}

==Overloading of operators

Judge whether two iterator pointers point to the same node
(two nodes will not be modified here. It is better to use const iterator)

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

!= operator overloading

!= Similar to = = writing, one is to judge whether the node pointed by the iterator pointer is different, and the other is to judge whether the node pointed by the iterator pointer is the same

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

*Overloading of operators

This is similar to the pointer de application operation, which directly returns the node pointed to by the iterator pointer. Because the de referenced data may be modified, the reference type is returned.

Ref operator*()
{
	return _node->_data;
}

->Overloading of operators

When the node is stored as a user-defined type, for example, the node storage is also a structure, it is not appropriate to use the * operator. In order to better access the node storage, we introduce the - > operator.

->Just return the address of the data stored in the node

Ptr operator->()
{
	return &_node->_data;
}

Simulation Implementation of list

Default member function

Constructor

List is a leading two-way circular linked list. When constructing, create a header node so that its forward pointer and backward pointer point to itself

list()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}

copy constructor

Create a new node, make its forward pointer and backward pointer point to itself, and then insert the traversal tail of the data to be copied into the node.

list(const list<T>& it)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

	for (const auto& e : it)
	{
		push_back(e);
	}
}

Assignment operator overloaded function

Traditional writing

First use the clear function to clean up the original linked list, leave the header node, and then traverse the tail insert of the new data

list<T>& operator=(const list<T>& lt)
{
	if (this != &lt)
	{
		clear();
		for (const auto& e : lt)
		{
			push_back(e);
		}
	}
	return *this;
}

Modern writing

The amount of code in modern writing is relatively small. First of all, the compiler mechanism is used to deliberately not use the reference parameters, and a list object is constructed by the compiler's automatic copy of the copy constructor of the list. Then the swap function is called to exchange the original container with the list object. The list copied after the process is destroyed.

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

Destructor

First call the clear function to clean up the node and leave the head node, and then release and empty the head node

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

Iterator correlation function

begin and end

From the string and vector classes, we know that the begin function returns the iterator of the first data, the end function returns the iterator of the next position of the last data, in the list class, the begin function returns the iterator of the next node of the header pointer, and the end function returns the iterator of the header node (the next node of the last node is the header node)

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

We also need to construct a pair of iterators for const objects

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

Accessing container related functions

The front and back functions are used to obtain the first valid data and the last valid data respectively, and return the first valid data and the last valid data

T& front()
{
	return *begin(); 
}
T& back()
{
	return *(--end()); 
}

Don't forget to write another const version for const type linked list

const T& front() const
{
	return *begin(); 
}
const T& back() const
{
	return *(--end());
}

Insert and delete functions

insert

Function: inserts data at a specified location.
Implementation idea: first get the node pointer cur at this position according to the given iterator, then find the node pointer prev at the previous position through the cur pointer, then construct a node to be inserted according to the given data x, and then establish the two-way relationship between the new node and cur and prev.

iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);
			
	// Establish a two-way relationship between the new node and cur and prev
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	return iterator(newnode);
}

erase

Function: delete the data at the specified location.
Implementation idea: first get the node pointer cur at this position according to the given iterator, then find the node pointer prev of the previous position and the node pointer next of the latter position through the cur pointer, then release the cur node, and finally establish a two-way relationship between prev and next.

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	delete cur;
	// Establish a two-way relationship between next and prev
	prev->_next = next;
	next->_prev = prev;
	return iterator(next);
}

push_front and push_back

Function: head insertion, tail insertion
Implementation idea: apply the previously implemented insert function, and use the iterator related functions begin and end to insert the header and tail

void push_front(const T& x)
{
	insert(begin(), x);
}

void push_back(const T& x)
{
	insert(end(), x);
}

pop_front and pop_back

Function: head deletion, tail deletion
Implementation idea: apply the previously implemented erase function and use the iterator related functions begin and end to delete the header and tail (Note: tail deletion is to delete the last data, and its previous node is required when using the end iterator).

void pop_back()
{
	erase(--end());
}

void pop_front()
{
	erase(begin());
}

Other functions

size

Function: get the number of valid data in the current container
Implementation idea: set variables, traverse containers, and record the number of valid data

size_t size()
{
	int n = 0;
	iterator it = begin();
	// Traversal container
	while (it != begin())
	{
		++it;
		++n;
	}
	return n;
}

empty

Function: judge whether the container is empty
Implementation idea: judge whether its begin and end iterators point to the same space

bool empty()
{
	return begin() == end();
}

clear

Function: empty container
Implementation idea: traverse and delete nodes, and only keep header nodes

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

swap

Function: exchange linked list
Implementation idea: in fact, only the header pointer of the linked list is stored in the list container. We can exchange the header pointers in the two containers.

void swap(list<T>& lt)
{
	::swap(_head, lt._head);//Swap header pointers between two containers
}