1.链表的分类
链表的分类
① 单向或者双向
② 带头或者不带头
③ 循环或者非循环
常用的链表：
根据上面的分类我们可以细分出8种不同类型的链表，这么多链表我们一个个讲解这并没有意义。我们实际中最常用的链表是 "无头单向非循环链表" 和 "带头双向循环链表" ，至于 "无头单项非循环链表" 我们在前面已经讲述过了，我们下面将讲解其反面： "带头双向循环列表" ！
解读：
① 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。此外，在笔试中单链表的出现频率较多。
② 带头双向循环链表：结构最复杂，但是实现反而简单。一般用来单独存储数据，实际中使用的链表数据结构都是带头双向循环链表。另外，这个结构虽然结构复杂，但是使用代码实现后会发现结构会带来很多优势。双向链表严格来说只需要快速的实现两个接口，insert 和 earse ，头尾的插入和删除就可以搞定了，这就是结构的优势！链表的接口函数
2.双向链表分步实现：
（List.h）
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DLNodeDataType; typedef struct DoubleListNode { DLNodeDataType data; struct DoubleListNode* next; // 指向后继节点的指针 struct DoubleListNode* prev; // 指向前驱节点的指针 }DLNode; DLNode* DListInit(); void DListPushBack(DLNode* pHead, DLNodeDataType x); void DListPrint(DLNode* pHead); void DListPopBack(DLNode* pHead); void DListPushFront(DLNode* pHead, DLNodeDataType x); void DListPopFront(DLNode* pHead); DLNode* DListFind(DLNode* pHead, DLNodeDataType x); void DListInsert(DLNode* pos, DLNodeDataType x); void DListEarse(DLNode* pos);
DListInit初始化函数：
DLNode* DListInit() { DLNode* pHead = (DLNode*)malloc(sizeof(DLNode)); if (pHead == NULL) { printf("malloc failed!\n"); exit(-1); } pHead->next = pHead; pHead->prev = pHead; return pHead; //这里我们使用 malloc 函数开辟一块空间作为 "哨兵位" pHead ， //最后将其进行一个初始化。最后再将 pHead 作为结果返回回去，外面就可以接收到了。 //这就是返回值的方法，当然这里也可以采用二级指针的方法来完成。 }
CreateNewNode创建新节点函数：
DLNode* CreateNewNode(DLNodeDataType x) { DLNode* newNode = (DLNode*)malloc(sizeof(DLNode)); if (newNode == NULL) { printf("malloc failed!\n"); exit(-1); } newNode->data = x; newNode->next = NULL; newNode->prev = NULL; return newNode; }
DListPushBack尾插函数：
哨兵位头节点的好处：不用分情况处理
//因为不用改变 pList，所以不需要使用二级指针 void DListPushBack(DLNode* pHead, DLNodeDataType x) { assert(pHead != NULL); DLNode* tail = pHead->prev; DLNode* newNode = CreateNewNode(x); tail->next = newNode;//原尾指向新尾 newNode->prev = tail;//新尾指回原尾 pHead->prev = newNode;//哨兵指到新尾 newNode->next = pHead;//新尾指回哨兵 }
DListPrint打印函数：
void DListPrint(DLNode* pHead) { //用结构体指针 pHead 接收， 这里的 pHead 表示哨兵位。 assert(pHead != NULL); DLNode* cur = pHead->next; //遍历链表就需要从 pHead->next 开始（即第一个有效数据节点） //当 cur 等于 pHead 就相当于全部走了一遍了，这时就结束。 while (cur != pHead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
DListPopBack尾删函数：
void DListPopBack(DLNode* pHead) { assert(pHead != NULL); assert(pHead->next != pHead);//防止删掉哨兵位头节点 DLNode* tali = pHead->prev;//记录原尾等下释放 pHead->prev = pHead->prev->prev;//头链接到新尾 pHead->prev->next = pHead;//新尾链接到头 free(tali); tali = NULL;//不置空也行 }
测试1
void TestList1() { DLNode* pList = DListInit(); DListPushBack(pList, 1); DListPushBack(pList, 2); DListPushBack(pList, 3); DListPushBack(pList, 4); DListPrint(pList); DListPopBack(pList); DListPopBack(pList); DListPrint(pList); }
DListPushFront头插函数：
void DListPushFront(DLNode* pHead, DLNodeDataType x) { assert(pHead != NULL); DLNode* newNode = CreateNewNode(x); pHead->next->prev = newNode;//原一指回新一 newNode->next = pHead->next;//新一指向原一 pHead->next = newNode;//哨兵指向新一 newNode->prev = pHead;//新一指回哨兵 //只有哨兵位头结点也能头插 }
DListPopFront头删函数：
void DListPopFront(DLNode* pHead) { assert(pHead != NULL); assert(pHead->next != pHead);//防止删掉哨兵位头节点 DLNode* head = pHead->next;//记录原一等下释放 pHead->next = head->next;//哨兵头指向原二 head->prev = pHead;//原二指回哨兵头 free(head); head = NULL;//不置空也行 }
测试2
void TestList2() { DLNode* pList = DListInit(); DListPushFront(pList, 1); DListPushFront(pList, 2); DListPushFront(pList, 3); DListPushFront(pList, 4); DListPrint(pList); DListPopFront(pList); DListPopFront(pList); DListPrint(pList); }
DListFind查找函数：
DLNode* DListFind(DLNode* pHead, DLNodeDataType x) { assert(pHead != NULL); DLNode* cur = pHead->next; //遍历链表就需要从 pHead->next 开始（即第一个有效数据节点）（和打印一样） //当 cur 等于 pHead 就相当于全部走了一遍了，这时就结束。 while (cur != pHead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
DListInsert指定位置之前插入函数：
void DListInsert(DLNode* pos, DLNodeDataType x)//在pos之前插入 { assert(pos != NULL); DLNode* newNode = CreateNewNode(x); DLNode* posPrev = pos->prev;//记录pos前节点 posPrev->next = newNode;//pos前节点指向新节点 newNode->prev = posPrev;//新节点指回pos前节点 newNode->next = pos;//新节点指向pos pos->prev = newNode;//pos指回新节点 }
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现（下）：https://developer.aliyun.com/article/1513386
