首页 > 代码库 > 双向链表(插入,删除,追加,正反向遍历,查找。。。)

双向链表(插入,删除,追加,正反向遍历,查找。。。)

#include <iostream>
#include <stdexcept>
using namespace std;
class List
{
public:
	List(void) : m_head(NULL), m_tail(NULL), m_size(0){}
	~List(void)
	{
		for(Node* node = m_head; m_head; m_head = node)
		{
			node = m_head->m_next;
			delete m_head;
		}
	}
	//在Index处插入元素
	void insert(int data, size_t index)
	{
		//如果下标超过元素个数,则追加在链表最后
		if(index >= m_size)
		{
			append(data);
			return;
		}
		Node* temp = new Node(data);
		//如果下标为0,则插入在头节点
		if(0 == index)
		{
			temp->m_next = m_head;
			m_head->m_prev = temp;
			m_head = temp;
			++m_size;
			return;
		}
		size_t count = 1;
		//其它情况
		for(Node* node = m_head->m_next; node; node = node->m_next)
		{
			if(index == count)
			{
				temp->m_next = node;
				temp->m_prev = node->m_prev;
				node->m_prev->m_next = temp;
				node->m_prev = temp;
				++m_size;
				return;
			}
			++count;
		}
	}
	//在链表尾部追加元素
	void append(int data)
	{
		Node* node = new Node(data);
		if(!m_head)
			m_head = node;
		else
		{
			node->m_prev = m_tail;
			m_tail->m_next = node;
		}
		m_tail = node;
		++m_size;
	}
	//删除元素
	void erase(size_t index)
	{
		if(!m_head)
			throw UnderFlow();
		//首先查找要删除的元素
		Node*& node = find(index, m_head);
		node->m_prev->m_next = node->m_next;
		node->m_next->m_prev = node->m_prev;
		delete node;
		node = NULL;
	}
	//查找元素
	int& find(size_t index)
	{
		Node*& node = find(index, m_head);
		return node->m_data;
	}
	//正向遍历
	void forward ()const
	{
		if(!m_head)
			throw UnderFlow();
		for(Node* node = m_head; node; node = node->m_next)
		{
			cout << node->m_data << ' ';
		}
		cout << endl;
	}
	//反向遍历
	void backward()const
	{
		if(!m_tail)
			throw UnderFlow();
		for(Node* node = m_tail; node; node = node->m_prev)
		{
			cout << node->m_data << ' ';
		}
		cout << endl;
	}
	//链表元素个数
	size_t size()
	{
		return m_size;
	}
	//重载下标操作符,作为左值
	int& operator[] (size_t index)
	{
		if(index >= m_size)
			throw OverFlow();
		Node*& node = find(index, m_head);
		return node->m_data;
	}
	//重载下标操作符,作为右值
	const int& operator[] (size_t index)const
	{
		//去常属性后,调用上面下标重载
		return const_cast<List&>(*this) [index];
	}
private:
	//链表每个节点
	class Node
	{
	public:
		Node(int data=http://www.mamicode.com/0, Node* prev=NULL, Node* next=NULL):>

双向链表(插入,删除,追加,正反向遍历,查找。。。)