一、什么是双向链表

双向链表（Doubly Linked List），又称为双链表，是链表的一种，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。双向链表既可以从头结点向后遍历，也可以从尾结点向前遍历，这样使得查找更加方便，操作也更加灵活。

二、C++双向链表实现

（1）定义结点类：双向链表的结点类有三个成员变量，分别是数据域data、指向前驱结点的指针prior和指向后继结点的指针next，如下代码所示：

template <class T>struct DNode{T data;DNode *prior;DNode *next;};

（2）定义双向链表类：双向链表类有两个成员变量，分别是头结点指针head和尾结点指针tail，如下代码所示：

template <class T>class DoublyLinkedList{private:DNode<T> *head;DNode<T> *tail;public:DoublyLinkedList();~DoublyLinkedList();};

（3）定义构造函数：构造函数初始化头结点指针head和尾结点指针tail，如下代码所示：

template <class T>DoublyLinkedList<T>::DoublyLinkedList(){head = new DNode<T>;tail = new DNode<T>;head->next = tail;tail->prior = head;}

（4）定义插入函数：插入函数实现在双向链表中插入结点的功能，如下代码所示：

template <class T>void DoublyLinkedList<T>::Insert(int i, T x){DNode<T> *p = head;int j = 0;while (p && j < i){p = p->next;j++;}if (p == NULL || j > i)return;DNode<T> *s = new DNode<T>;s->data = x;s->prior = p->prior;s->next = p;p->prior->next = s;p->prior = s;}

三、总结

C++双向链表实现的基本思路是：定义结点类，定义双向链表类，定义构造函数，定义插入函数等，具体实现步骤如上所述。双向链表的操作比单链表复杂，但其优点是可以从头结点向后遍历，也可以从尾结点向前遍历，查找更加方便，操作也更加灵活。