C语言类的双向链表详解
前言
链表（linked list)是一种这样的数据结构，其中的各对象按线性排列。数组的线性顺序是由数组下标决定的，然而于数组不同的是，链表的各顺序是由链表中的指针决定的。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双向链表的定义
双链表（doubly linked list)的每一个元素都是一个对象，每一个对象都有一个数据域和两个指针front和tail。对象中还可以包含其他辅助数据。设L为链表的一个元素，L.front指向他在链表中的后继元素，L.tail指向他的前继元素。
我们可以定义一个结构体封装这些数据
typedef struct Node
{
int data;
struct Node* front;
struct Node* tail;
}NODE, * LPNODE;
双向链表的创建
在C++中，我们以类的形式封装了双向链表。在类中，我们定义了两个指针，一个是指向链表的头部 frontNode，一个是指向了链表的尾部 tailNode，另外我们还加入了 curSize属性，记录节点的个数。在对象创建的过程就是链表创建的过程，我们只需要在类的构造函数中初始化参数即可。
class duplexHead {
public:
duplexHead() {
frontNode = NULL;
tailNode = NULL;
curSize = 0;
}
LPNODE createNode(int data);
LPNODE seachNode(int data);
void push_front(int data);
void push_back(int data);
void push_appoin(int posData, int data);
void pop_front();
void pop_back();
void pop_appoin(int posData);
void printByFront();
void printByTail();
protected:
LPNODE frontNode;
LPNODE tailNode;
int curSize;
};
节点的创建
在上面，我们已经知道双向链表的单体长啥样了，我们只需要给他的单体分配空间然后初始化他的参数即可。
LPNODE duplexHead::createNode(int data)
{
LPNODE newNode = new NODE;
assert(newNode);
newNode->front = nullptr;
newNode->tail = nullptr;
newNode->data = data;
return newNode;
}
双向链表节点查找
链表的查找我们可以定义一个函数LPNODE seachNode（int data)，当满足查找条件时，我们就返回当前节点的链表。在实际操作过程中，链表的数据域可能会有多个数据，可能要比较int 类型，可能要比较string类型等多种变化，这是我们可以在参数列表预留一个函数指针 (int) (*comparData)(LPNODE data),以应对多种需求。当然，在这里为了演示方便，我们就用一个int 类型的数据代替了。
LPNODE duplexHead::seachNode(int data)
{
if (!curSize)
{
printf("链表为空，无法查找");
return;
}
LPNODE preNode = frontNode;
LPNODE curNode = frontNode;
while (curNode != NULL && curNode->data != data)
{
preNode = curNode;
curNode = preNode->tail;
}
if (curNode == nullptr)
{
printf("链表中没有该数据");
return nullptr;
}
return curNode;
}
双向链表的插入
插入节点，我们分为头部插入和尾部插入以及指定位置插入。而这三种插入，都可分为3步。
（1）创建新节点
（2）找到插入位置
（3）插入
我们就以制定位置插入为例，如图所示，我们只需把原来相连的两个节点断开，然后再分别用指针拼接起来，当然我们也可以调用我们的seachNode来查找位置，这样就更方便一些了。
void duplexHead::push_appoin(int posData, int data)
{
if (curSize == 0)
return;
if (frontNode->data == posData)
{
push_front(data);
}
else
{
LPNODE preNode = frontNode;
LPNODE curNode = frontNode;
while (curNode != NULL && curNode->data != posData)
{
preNode = curNode;
curNode = preNode->tail;
}
if (curNode == NULL)
{
printf("未找到指定位置，无法插入！\n");
}
else
{
LPNODE newNode = createNode(data);
preNode->tail = newNode;
newNode->tail = curNode;
curNode->front = newNode;
newNode->front = preNode;
curSize++;
}
}
}
双向链表的节点删除
删除节点我们也可以分为头部删除，尾部删除，指定数据删除。他与插入节点几乎是一样的
（1）找到删除位置
（2）删除
我们就以指定数据删除为例，我们通过while或者seachNode来查找到要删除的节点，然后把他的front 指向的位置和tail指向的位置记住，就可以直接删除节点了。删除完了节点要记得把前后段的链表连接上即可。
void duplexHead::pop_appoin(int posData)
{
if (frontNode == NULL || curSize == 0)
{
printf("链表为空无法删除！");
return;
}
if (frontNode->data == posData)
{
pop_front();
return;
}
LPNODE preNode = frontNode;
LPNODE curNode = frontNode;
while (curNode != NULL && curNode->data != posData)
{
preNode = curNode;
curNode = preNode->tail;
}
if (curNode == NULL)
{
printf("未找到指定位置无法删除！\n");
}
else
{
if (tailNode == curNode)
{
pop_back();
}
else
{
preNode->tail = curNode->tail;
//curNode->tail是不是不空
//当删除的表尾时候，curNode->tail等于空
curNode->tail->front = preNode;
free(curNode);
curNode = NULL;
curSize--;
}
}
}
双向链表的删除
于双向链表的创建一样，我们可以把双向链表的删除放在析构函数中，实现创建和删除自动化，当对象被创建，双向链表就被创建，当对象消亡，双向链表就删除了。
duplexHead::~duplexHead()
{
if (!frontNode)return;
LPNODE pmove ;
while (!pmove)
{
pmove = frontNode->tail;
delete frontNode->tail;
frontNode = pmove;
}
}
