双向链表实现

链表结点定义

双向链表节点定义由一个数据域和两个指针域组成。

template<typename T>
class List_Node
{
public:
	typedef List_Node<T>* link_node;
public:
	T data;
	link_node next;
	link_node prev;
};

链表结构实现

初始化定义

将其定义为一个循环的双向链表可以节约大量的头插和尾插的时间复杂度，且在查找是可以根据查询节点的位置，选择是通过next指针查找还是通过prev指针查找。

故我们可以写出如下的基本格式

template<typename T>
class List
{
public:
	typedef List_Node<T>* link_node;
public:
	List();
	~List();
private:
	link_node _head;
	int _size;
};

其初始化代码如下：

template<typename T>
inline List<T>::List()
{
	// 创建头节点
	_head = new node();
	_head->data = -1;
	_head->next = _head;
	_head->prev = _head;
	_size = 0;
}

完成上述步骤我们就已经拥有了一个头节点，通过这个头节点我们可以对链表进行添加、修改、删除、查找。

定义头节点的优点：

一、使第一个元素的操作与后面的元素操作一致。如果我们并未定义头节点，那么我们使用第一个元素就需要通过头指针去获得，而我们访问其他元素是通过.next的方式访问的。

二、方便实现循环链表的实现

链表的操作

查找操作

根据传入的下标index来判断是使用那种指针去指向目标。

注意：不论是使用next指针还是使用prev指针最终都能够到达指定的目标位置，他们之间的区别仅仅只是执行次数不同。

// 找到对应位置的节点，返回内存地址。查找的效率决定程序的优劣
template<typename T>
inline List_Node<T>* List<T>::find(int index) 
{
	if(index < 0 || index > size() + 1) return NULL;

	link_node node = _head;
	// 判断 index 位置 决定使用那个指针去查找
	if(index < (size() / 2)) 
	{
		// 使用头指针
		while(index > 0){
			node = node->next;
			--index;
		}
	} else {
		// 使用尾指针 
		index = _size - index + 1;
		while(index > 0){
			node = node->prev;
			--index;
		}
	} 
	return node;
}

插入操作

首先我们通过find方法找到插入位置的节点，将新节点插入该位置。

该示例以，尾插法进行图示。

template<typename T>
inline void List<T>::insert(T data, int index)
{
	link_node p = find(index); 
	if(p){ // p != NULL
		try {
			link_node new_node = new node();
			new_node->data = data;

			new_node->prev = p->prev;
			p->prev->next = new_node;

			new_node->next = p;
			p->prev = new_node;

			++_size;
		} catch (const std::exception &) {
			// 内存空间不足，分配内存失败
		}
	}
}

节点的删除

由于在C++标准库中提供的List并未提供随机删除操作，故这里我仅提供了一个私有的成员函数作为pop_back和pop_fron的底层实现。

template<typename T>
inline void List<T>::pop_back()
{
	deleteNode(_head->prev);
}

template<typename T>
inline void List<T>::pop_front()
{
	deleteNode(_head->next);
}

template<typename T>
inline void List<T>::deleteNode(link_node node)
{
	link_node next = node->next;
	link_node prev = node->prev;
	free(node);
	next->prev = prev;
	prev->next = next;
}

节点的修改

对于节点的修改我们可以采用同样的思路，即通过index调用find函数找到目标节点，在对目标进行修改。

由于这里我使用了模板作为类的数据，故针对修改操作，我并没有定义但是通过find函数可以找到目标节点，使得使用者可以通过find函数进行自己想要的修改操作。

链表的销毁

由于链表是一个环形链表，所以为了避免内层的重复释放，我们必须要有一个指针去保存结束位置。

释放内存时，我们通过指针p去保存_head的地址，然后使 _head指向它的next，在释放p保存的地址，这样不断循环直到 _head又回到了它原来指向的位置。

template<typename T>
inline List<T>::~List()
{
	link_node p = _head;
	link_node __head = _head;
	_head = _head->next;
	while(_head != __head){
		delete p;
		p = _head;
		_head = _head->next;
	}
}

如此我们便实现对链表数据的创建、添加元素、删除元素、查找元素、修改元素以及销毁链表。