单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据元素将极其低效。

双链表是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

template <typename T>class DualLinkedList:public List<T>{protected: struct Node:public Object { T value;//数据域 Node* next;//后继指针域 Node* pre;//前驱 }; mutable struct:public Object { char reserved[sizeof(T)];//占位空间 Node* next; Node* pre; }m_header; int m_length; int m_step; Node* m_current;}二、双向链表的操作1、双向链表的插入操作

bool insert(int index, const T& value) { //判断目标位置是否合法 bool ret = (0 <= index) && (index <= m_length); if(ret) { //创建新的结点 Node* node = createNode(); if(node != NULL) { //当前结点定位到目标位置 Node* current = position(index); //当前结点的下一个结点 Node* next = current->next; //修改插入结点的值 node->value = value; //将当前位置的下一个结点作为插入结点的下一个结点 node->next = next; //将要插入结点作为当前结点的下一个结点 current->next = node; if(current != reinterpret_cast<Node*>(&m_header)) { node->pre = current; } else { node->pre = NULL; } if(next != NULL) { next->pre = node; } m_length++;//链表结点长度加1 } else { THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory..."); } } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid..."); } return ret; } bool insert(const T& value) { return insert(m_length, value); }2、双向链表的删除操作

bool remove(int index) { //判断目标位置是否合法 bool ret = (0 <= index) && (index < m_length); if(ret) { //当前结点指向头结点 Node* current = position(index); //使用toDel指向要删除的结点 Node* toDel = current->next; Node* next = toDel->next; if(m_current == toDel) { m_current = next; } //将当前结点的下一个结点指向要删除结点的下一个结点 current->next = next; if(next != NULL) next->pre = current; m_length--;//链表结点长度减1 destroy(toDel);//释放要删除的结点的堆空间 } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid..."); } return ret; }三、双向链表的实现

template <typename T> class DualLinkedList:public List<T> { protected: struct Node:public Object { T value;//数据域 Node* next;//后继指针域 Node* pre;//前驱 }; mutable struct:public Object { char reserved[sizeof(T)];//占位空间 Node* next; Node* pre; }m_header; int m_length; int m_step; Node* m_current; protected: Node* position(int index)const { //指针指向头结点 Node* ret = reinterpret_cast<Node*>(&m_header); //遍历到目标位置 for(int i = 0; i < index; i++) { ret = ret->next; } return ret; } public: DualLinkedList() { m_header.next = NULL; m_header.pre = NULL; m_length = 0; m_step = 1; m_current = NULL; } virtual ~DualLinkedList() { clear(); } bool insert(int index, const T& value) { //判断目标位置是否合法 bool ret = (0 <= index) && (index <= m_length); if(ret) { //创建新的结点 Node* node = createNode(); if(node != NULL) { //当前结点定位到目标位置 Node* current = position(index); //当前结点的下一个结点 Node* next = current->next; //修改插入结点的值 node->value = value; //将当前位置的下一个结点作为插入结点的下一个结点 node->next = next; //将要插入结点作为当前结点的下一个结点 current->next = node; if(current != reinterpret_cast<Node*>(&m_header)) { node->pre = current; } else { node->pre = NULL; } if(next != NULL) { next->pre = node; } m_length++;//链表结点长度加1 } else { THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory..."); } } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid..."); } return ret; } bool insert(const T& value) { return insert(m_length, value); } bool remove(int index) { //判断目标位置是否合法 bool ret = (0 <= index) && (index < m_length); if(ret) { //当前结点指向头结点 Node* current = position(index); //使用toDel指向要删除的结点 Node* toDel = current->next; Node* next = toDel->next; if(m_current == toDel) { m_current = next; } //将当前结点的下一个结点指向要删除结点的下一个结点 current->next = next; if(next != NULL) next->pre = current; m_length--;//链表结点长度减1 destroy(toDel);//释放要删除的结点的堆空间 } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid..."); } return ret; } bool set(int index, const T& value) { //判断目标位置是否合法 bool ret = (0 <= index) && (index < m_length); if(ret) { //将当前结点指向头结点 Node* current = position(index); //修改目标结点的数据域的值 current->next->value = value; } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid..."); } return ret; } bool get(int index, T& value)const { //判断目标位置是否合法 bool ret = (0 <= index) && (index < m_length); if(ret) { //当前结点指向头结点 Node* current = position(index); //遍历到目标位置 //获取目标结点的数据域的值 value = current->next->value; } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid..."); } return ret; } //重载版本 T get(int index)const { T ret; if(get(index, ret)) return ret; } int length()const { return m_length; } int find(const T& value)const { int ret = -1; //指向头结点 Node* node = m_header.next; int i = 0; while(node) { //找到元素，退出循环 if(node->value == value) { ret = i; break; } else { node = node->next; i++; } } return ret; } void clear() { //遍历删除结点 while(m_header.next) { //要删除的结点为头结点的下一个结点 Node* toDel = m_header.next; //将头结点的下一个结点指向删除结点的下一个结点 m_header.next = toDel->next; m_length--; destroy(toDel);//释放要删除结点 } } virtual bool move(int pos, int step = 1) { bool ret = (0 <= pos) && (pos < m_length) && (0 < step); if(ret) { m_current = position(pos)->next; m_step = step; } return ret; } virtual bool end() { return m_current == NULL; } virtual T current() { if(!end()) { return m_current->value; } else { THROW_EXCEPTION(InvalidOperationException, "Invalid Operation..."); } } virtual bool next() { int i = 0; while((i < m_step) && (!end())) { m_current = m_current->next; i++; } return (i == m_step); } virtual bool pre() { int i = 0; while((i < m_step) && (!end())) { m_current = m_current->pre; i++; } return (i == m_step); } virtual Node* createNode() { return new Node(); } virtual void destroy(Node* node) { delete node; } };