链表的结构⾮常多样，主要分为带头与不带头、单向与双向、循环与不循环。三个种类可以任意搭配，所以总共可以形成八种链表，但是最常用的是单向不带头不循环链表和双向带头循环链表。

        1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。

        前者即单链表，在前一篇文章中已经讲过了，所以我们再来看看双向链表。

双向链表的实现

文件:DoubleListNode.h

//双链表结构体创建
typedef int slDataType;
typedef struct DoubleList
{slDataType data;struct DoubleList* next;struct DoubleList* prev;
}DLN;//双向链表的初始化
void DbleInit(DLN** pphead);//双向链表打印
void DLNPrint(DLN* phead);//双向链表尾插函数
void DbleTailAdd(DLN* phead,int data);//双向链表头插函数
void DbleHeadAdd(DLN* phead, slDataType data);//双向链表头删函数
void DbleHeadDel(DLN* phead);//双向链表尾删函数
void DbleTailDel(DLN* phead);//双向链表查找
DLN* DbleSearch(DLN* phead);//双向链表修改函数
void DbleModify(DLN* phead);//双向链表销毁函数
void DbleStroy(DLN* phead);

文件DoubleListNode.c

//申请新节点
DLN* ListByNode(slDataType data)
{DLN* newnode = (DLN*)malloc(sizeof(DLN));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = data;return newnode;
}//双向链表的初始化
void DbleInit(DLN** pphead)
{*pphead = (DLN*)malloc(sizeof(DLN));if (*pphead == NULL){perror("malloc fail");exit(1);}(*pphead)->data = -1;(*pphead)->next = (*pphead);(*pphead)->prev = (*pphead);
}//双向链表打印
void DLNPrint(DLN* phead)
{assert(phead);DLN* pcur = phead->next;while (pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;}printf("\n");
}//双向链表尾插函数
void DbleTailAdd(DLN* phead, slDataType data)
{assert(phead);DLN* newnode = ListByNode(data);newnode->data = data;//尾插新节点newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//双向链表头插函数
void DbleHeadAdd(DLN* phead, slDataType data)
{assert(phead);DLN* newnode = ListByNode(data);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//双向链表头删函数
void DbleHeadDel(DLN* phead)
{assert(phead);DLN* pcur = phead->next;if (pcur == phead){printf("删除失败，不存在有效节点\n");}else{phead->next = pcur->next;pcur->next->prev = phead;free(pcur);pcur = NULL;}
}//双向链表尾删函数
void DbleTailDel(DLN* phead)
{assert(phead);DLN* pcur = phead->next;while (pcur->next != phead){pcur = pcur->next;}phead->prev = pcur->prev;pcur->prev->next = phead;free(pcur);pcur = NULL;
}//双向链表查找
DLN* DbleSearch(DLN* phead,slDataType pos)
{assert(phead);DLN* pcur = phead->next;while (pcur != phead){if (pcur->data == pos){printf("找到了\n");return pcur;}pcur = pcur->next;}printf("没找到\n");return NULL;
}//双向链表修改函数
void DbleModify(DLN* phead,slDataType pos,slDataType data)
{DLN* find = DbleSearch(phead,pos);if (find != NULL){find->data = data;printf("修改成功\n");return;}else{printf("修改失败，未找到该节点\n");}
}//双向链表销毁函数
void DbleStroy(DLN* phead)
{assert(phead);DLN* pcur = phead->next;DLN* next = pcur->next;while (pcur != phead){free(pcur);pcur = next;next = next->next;}printf("销毁成功\n");
}

        这里单独讲解一个点，我们在创建“哨兵位”的时候使用的参数是一级指针的地址，并用二级指针接收，目的是创建一个节点的地址用作节点的链表头部，之后的其他函数均使用一级指针是为了防止头节点被修改。

        测试代码由各位自行书写，我们下期间。