当我们学习完单链表后，双向链表就简单的多了，双向链表中的头插，尾插，头删，尾删，以及任意位置插，任意位置删除比单链表简单，今天就跟着小张一起学习吧！！
双向链表的分类
双向不带头链表
双向带头循环链表
还有双向带头不循环链表，双向不带头循环链表，着重使用双向带头循环链表，带头也就是有哨兵位。
双向带头循环链表
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
双向循环链表的接口实现
ListNode* ListCreate(int x)//创建新结点 ListNode* createhead()//创建哨兵位 void ListPushBack(ListNode* phead, int x)//尾插 void SListPrint(ListNode* phead)//打印链表 void SListPushFront(ListNode* phead, int x)//头插 void SListPopBack(ListNode* phead)//尾删 void SListPopFront(ListNode* phead)//头删 void SListInsert(ListNode* pos, int x)//pos前插 void SListErase(ListNode* pos)//删除pos; ListNode* SListFind(ListNode* phead,int x)//查找链表中第一个x
0.结点结构体创建
typedef struct ListNode { int data;//数据 struct ListNode* next;//下个结点地址 struct ListNode* prev;//上个结点地址 }ListNode;
1.创建一个新结点
ListNode* ListCreate(int x)//创建新结点 { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//给新结点申请空间 if (newnode == NULL) { perror("malloc error");//没申请到，malloc返回NULL给newnode } newnode->data = x;//新结点的数据给x newnode->next = NULL;//新结点的下一个结点地址为空 newnode->prev = NULL;//新结点的上一个结点地址为空 return newnode;//新结点的地址返回回去 }
2.创建哨兵位
该哨兵位作为链表的头结点，不存数据
ListNode* createhead() { ListNode* head = ListCreate(-1);//哨兵位结点的数据随便给个-1 head->next = head; head->prev = head; return head;//返回哨兵位的头结点地址 }
当没有带数据的新结点时，先让他上一个结点地址，和下一关结点地址都存入head自己的地址
3.尾插
void ListPushBack(ListNode* phead, int x)//尾插 { ListNode* newnode = ListCreate(int x); ListNode* tail = phead->prev;//记录尾结点的地址 newnode->prev =tail;//新结点的prev存放尾结点的地址-1 newnode->next = phead;//新结点的next存放头结点哨兵位的地址->2 phead->prev = newnode;//头结点的prev存放新结点的地址->4 tail->next = newnode;//尾结点的next存放新节点的地址->3 }
分析：
由于使用tail记录了尾结点的地址，所以1，2，3，4可以任意切换顺序，如果没有记录，记得先将新结点的prev,next,先保存，然后在修改head->prev, head->prev->next;防止修改过程中，尾结点的地址丢失。
同样适用于在哨兵位后插新结点
4.打印双链表
void SListPrint(ListNode* phead)//打印链表 { ListNode* cur = phead->next; while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); }
分析：定义一个指针cur遍历整个链表，由于是循环链表，肯定会指向哨兵位，哨兵位结点的数据不使用，所以cur指针从头节点哨兵位的下一个结点开始遍历，直到cur==phead,循环结束，每次打印cur->data,然后移动cur到下一个结点。
5.头插
void SListPushFront(ListNode* phead, int x)//头插 { ListNode* newnode = ListCreate(x); newnode->next = phead->next; phead->next->prev = newnode; newnode->prev = phead; phead->next = newnode; }
分析：
注意：先保存newnode->next;和newnode->prev;
此时如果先进行4的话，phead->next的地址就变成了newnode,之前的phead->next地址丢失掉。
还有一种方法是先保存* next=phead->next;然后1，2，3，4，顺序可以调换。
6.尾删
void SListPopBack(ListNode* phead)//尾删 { ListNode* last = phead->prev->prev;//记录尾结点的上一个结点的地址 phead->prev = last;//头节点哨兵位的prev存入last的地址 last->next = phead;//last的next存入phead的地址 }
分析：
当要删除尾结点，我们可以先记录尾结点的上一个结点的地址，因为要删除尾结点，改变就是将尾结点的上一个结点last的next存phead的地址，phead的prev存入的是last的地址
除哨兵位还有一个结点的尾删剩下一个哨兵位头结点，同样适用上面的代码
7.头删
void SListPopFront(ListNode* phead)//头删 { ListNode* next = phead->next; phead->next = next->next; next->next->prev = phead; }
分析：
先保存哨兵位的下一个结点地址到next,然后将phead的next中存入next->next;将next->next->prev存入phead的首地址
8.pos指针指向的结点前插
void SListInsert(ListNode* pos, int x)//pos前插 { ListNode* newnode = ListCreate(x);//申请新结点将地址存放在newnode变量中 newnode->next = pos;//新结点的下一个结点保存pos指针指向节点的地址 newnode->prev = pos->prev;//新结点的prev保存pos指针指向的节点的上一个节点的地址 pos->prev->next=newnode;//pos指针指向的节点的前一个结点的next保存newnode指针指向的结点 pos->prev = newnode;//pos指针指向的结点的prev保存newnode指针指向结点的地址 }
分析：
9.删除pos指针指向的结点
void SListErase(ListNode* pos)//删除pos; { ListNode* last = pos->prev;//记录pos指针指向结点的前一个结点地址 ListNode* next = pos->next;//记录pos指针指向结点的后一个结点地址 last->next = next;//操作1 next->prev = last;//操作2 }
分析：
10.查找链表第一个出现的x
ListNode* SListFind(ListNode* phead,int x) { ListNode* cur = phead->next;//cur指针先指向phead的下一个结点的位置 while (cur != phead)//循环遍历 { if (cur->data == x)//第一次找到 { return cur;返回结点数据等于x的地址 } cur = cur->next;//cur指针指向下一个结点 } return NULL; }
分析：类似于打印打印链表，遍历循环，从phead->next开始遍历，当cur不等于phead继续循环，如果cur->datax,就return cur的内容，也就是datax的结点地址，循环结束没有找到的话，就是该链表没有等于x的结点返回NULL;
11.双向链表的销毁
void Destroy(ListNode* phead) { ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); }
分析，定义一个指针cur先指向phead的下一个结点，开始遍历，先保存cur指向结点的下一个结点的地址到next,然后释放掉cur指针指向的空间，然后让cur指向已经保存在next中下一个结点的地址，依次循环释放掉所有的结点，循环结束，释放掉哨兵位。
12.完整源码
#include <stdio.h> #include <stdlib.h> typedef struct ListNode { int data; struct ListNode* next; struct ListNode* prev; }ListNode; ListNode* ListCreate(int x)//创建新结点 { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc error"); //return; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode* createhead() { ListNode* head = ListCreate(-1); head->next = head; head->prev = head; return head; } void ListPushBack(ListNode* phead, int x)//尾插 { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = x; ListNode* tail = phead->prev; newnode->prev =tail; phead->prev = newnode; tail->next = newnode; newnode->next = phead; } void SListPrint(ListNode* phead)//打印链表 { ListNode* cur = phead->next; while (cur != phead) { printf("%d->",cur->data); cur = cur->next; } printf("\n"); } void SListPushFront(ListNode* phead, int x)//头插 { ListNode* newnode = ListCreate(x); newnode->next = phead->next; phead->next->prev = newnode; newnode->prev = phead; phead->next = newnode; } void SListPopBack(ListNode* phead)//尾删 { ListNode* last = phead->prev->prev; phead->prev = last; last->next = phead; } void SListPopFront(ListNode* phead)//头删 { ListNode* next = phead->next; phead->next = next->next; next->next->prev = phead; } void SListInsert(ListNode* pos, int x)//pos前插 { ListNode* newnode = ListCreate(x); newnode->next = pos; newnode->prev = pos->prev; pos->prev->next=newnode; pos->prev = newnode; } void SListErase(ListNode* pos)//删除pos; { ListNode* last = pos->prev; ListNode* next = pos->next; last->next = next; next->prev = last; } ListNode* SListFind(ListNode* phead,int x) { ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //双链表的销毁 void Destroy(ListNode* phead) { ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); } int main() { ListNode* list; list = createhead(); printf("尾插:"); ListPushBack(list,1); ListPushBack(list,2); ListPushBack(list,3); ListPushBack(list,4); SListPrint(list); printf("头插:"); SListPushFront(list, 8); SListPushFront(list, 7); SListPushFront(list, 6); SListPushFront(list, 5); SListPrint(list); printf("尾删:"); SListPopBack(list); SListPopBack(list); SListPrint(list); printf("头删:"); SListPopFront(list); SListPopFront(list); SListPopFront(list); SListPrint(list); printf("插入pos指向结点前面:"); SListInsert(list->next->next, 1000); SListPrint(list); printf("删除pos指向的结点:"); SListErase(list->next->next); SListPrint(list); printf("查找第一个x的位置并打印出来:"); ListNode* p=SListFind(list, 8); printf("%d", p->data); printf("修改查找到的结点:\n"); p->data = 10000; SListPrint(list); printf("销毁打印销毁后哨兵位的下一个结点的数据,如果为随机值说明已经被销毁："); Destroy(list); printf("%d",list->data); }
13.编译运行
