尧图网页设计 
今天学习双向为了方便理解放个图head带头链表⾥的头结点实际为“哨兵位”哨兵位结点不存储任何有效元素只是站在这⾥“放哨的”双向链表解决单链表的单向痛点一、为什么需要双向链表单链表只有一个next指针只能从头到尾单向遍历。如果想找某个结点的前驱结点或者想从尾部往前倒序访问单链表就只能从头开始遍历时间复杂度直接变成 O (N)在频繁需要双向操作的场景里效率很低。双向链表就是在单链表的基础上给每个结点多加了一个指向前驱的指针让链表可以双向行走补上了单链表的短板。二、双向链表的结构1. 结点组成每个结点包含三部分数据域存储具体的业务数据next指针指向后一个结点prev指针指向前一个结点对应的 C 语言结构体定义typedef int LTDataType; typedef struct ListNode { struct ListNode* next; // 指向后一个结点 struct ListNode* prev; // 指向前一个结点 LTDataType data; // 存储的数据 } LTNode;2. 实际最常用带头双向循环链表工程里几乎不会用裸的双向链表最常用的是带头双向循环链表。这里有两个核心概念带头哨兵位在链表最前面加一个不存有效数据的 “哨兵结点”。它的存在是为了简化边界操作不用单独处理头插、头删时的空指针问题。循环链表尾结点的next指向哨兵位哨兵位的prev指向尾结点整个链表形成一个闭环。这种结构看起来定义更复杂但真正写代码的时候会发现所有位置的插入、删除逻辑都完全统一了不用区分头部、尾部、中间情况反而实现起来更简洁。三、双向链表的核心操作实现下面以带头双向循环链表为例梳理核心接口的实现思路。1. 初始化初始化就是创建一个哨兵位结点让它的next和prev都指向自己形成一个空的循环链表。// 创造结点 listnode* creatnode(type x) { listnode* newnode (listnode*)malloc(sizeof(listnode)); if (newnode NULL) { perror(newnode); exit(1); } newnode-datex; newnode-next newnode-prev newnode; return newnode; }2. 判空判断链表有没有有效数据只需要看哨兵位的next是不是还指向自己。bool LTEmpty(LTNode* phead) { return phead-next phead; }3. 尾部插入因为是循环结构尾结点天然就是哨兵位的prev所以直接在哨兵和原尾结点之间插入新结点即可不需要遍历找尾。void backinsert(listnode* phead, type x) { assert(phead); listnode* newnode creatnode(x); newnode-next phead; newnode-prev phead-prev; phead-prev-next newnode; phead-prev newnode; }头插逻辑同理在哨兵位和第一个有效结点之间插入即可时间复杂度都是 O (1)。4. 指定位置之后插入双向链表的插入核心是修改四个指针新结点的prev和next以及前后两个结点的next和prev。// 在pos结点之后插入x void posback(listnode* pos, type x) { assert(pos); listnode* newnode creatnode(x); newnode-next pos-next; newnode-prev pos; pos-next-prev newnode; pos-next newnode; }有了这个通用插入函数头插、尾插都可以直接复用头插就是在哨兵位之后插尾插就是在哨兵位的prev之后插。5. 删除指定结点删除pos结点只需要把它前后两个结点直接连起来然后释放pos即可。void poserase(listnode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); pos NULL; }同样头删、尾删都可以复用这个函数不用单独写边界逻辑。6. 查找与遍历查找从哨兵位的下一个结点开始遍历直到回到哨兵位即为遍历结束。listnode* find(listnode* phead, type x) { assert(phead); listnode* pcur phead-next; while (pcur ! phead) { if (pcur-date x) { return pcur; } pcur pcur-next; } return NULL; }7. 销毁链表遍历释放所有有效结点最后把哨兵位也释放掉。void destroy(listnode** phead) { listnode* pcur (*phead)-next; while (pcur ! *phead) { listnode* next pcur-next; free(pcur); pcur next; } free(*phead); *phead NULL; }四、双向链表的特点总结优势支持双向遍历找前驱和后继结点都很方便带头循环结构下头尾的插入、删除都是 O (1)无需遍历任意位置的插入删除逻辑统一边界情况少代码更简洁不足每个结点多了一个prev指针相比单链表内存开销更大仍然不支持随机访问按下标查找元素依然需要遍历时间复杂度 O (N)适用场景需要频繁在任意位置插入、删除元素需要双向遍历链表的业务场景对头部、尾部操作效率要求高的场完整代码gittee:https://gitee.com/yang-mianmian-1/doubly-linked-list 双向链表实现
今天学习双向为了方便理解放个图head带头链表⾥的头结点实际为“哨兵位”哨兵位结点不存储任何有效元素只是站在这⾥“放哨的”双向链表解决单链表的单向痛点一、为什么需要双向链表单链表只有一个next指针只能从头到尾单向遍历。如果想找某个结点的前驱结点或者想从尾部往前倒序访问单链表就只能从头开始遍历时间复杂度直接变成 O (N)在频繁需要双向操作的场景里效率很低。双向链表就是在单链表的基础上给每个结点多加了一个指向前驱的指针让链表可以双向行走补上了单链表的短板。二、双向链表的结构1. 结点组成每个结点包含三部分数据域存储具体的业务数据next指针指向后一个结点prev指针指向前一个结点对应的 C 语言结构体定义typedef int LTDataType; typedef struct ListNode { struct ListNode* next; // 指向后一个结点 struct ListNode* prev; // 指向前一个结点 LTDataType data; // 存储的数据 } LTNode;2. 实际最常用带头双向循环链表工程里几乎不会用裸的双向链表最常用的是带头双向循环链表。这里有两个核心概念带头哨兵位在链表最前面加一个不存有效数据的 “哨兵结点”。它的存在是为了简化边界操作不用单独处理头插、头删时的空指针问题。循环链表尾结点的next指向哨兵位哨兵位的prev指向尾结点整个链表形成一个闭环。这种结构看起来定义更复杂但真正写代码的时候会发现所有位置的插入、删除逻辑都完全统一了不用区分头部、尾部、中间情况反而实现起来更简洁。三、双向链表的核心操作实现下面以带头双向循环链表为例梳理核心接口的实现思路。1. 初始化初始化就是创建一个哨兵位结点让它的next和prev都指向自己形成一个空的循环链表。// 创造结点 listnode* creatnode(type x) { listnode* newnode (listnode*)malloc(sizeof(listnode)); if (newnode NULL) { perror(newnode); exit(1); } newnode-datex; newnode-next newnode-prev newnode; return newnode; }2. 判空判断链表有没有有效数据只需要看哨兵位的next是不是还指向自己。bool LTEmpty(LTNode* phead) { return phead-next phead; }3. 尾部插入因为是循环结构尾结点天然就是哨兵位的prev所以直接在哨兵和原尾结点之间插入新结点即可不需要遍历找尾。void backinsert(listnode* phead, type x) { assert(phead); listnode* newnode creatnode(x); newnode-next phead; newnode-prev phead-prev; phead-prev-next newnode; phead-prev newnode; }头插逻辑同理在哨兵位和第一个有效结点之间插入即可时间复杂度都是 O (1)。4. 指定位置之后插入双向链表的插入核心是修改四个指针新结点的prev和next以及前后两个结点的next和prev。// 在pos结点之后插入x void posback(listnode* pos, type x) { assert(pos); listnode* newnode creatnode(x); newnode-next pos-next; newnode-prev pos; pos-next-prev newnode; pos-next newnode; }有了这个通用插入函数头插、尾插都可以直接复用头插就是在哨兵位之后插尾插就是在哨兵位的prev之后插。5. 删除指定结点删除pos结点只需要把它前后两个结点直接连起来然后释放pos即可。void poserase(listnode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); pos NULL; }同样头删、尾删都可以复用这个函数不用单独写边界逻辑。6. 查找与遍历查找从哨兵位的下一个结点开始遍历直到回到哨兵位即为遍历结束。listnode* find(listnode* phead, type x) { assert(phead); listnode* pcur phead-next; while (pcur ! phead) { if (pcur-date x) { return pcur; } pcur pcur-next; } return NULL; }7. 销毁链表遍历释放所有有效结点最后把哨兵位也释放掉。void destroy(listnode** phead) { listnode* pcur (*phead)-next; while (pcur ! *phead) { listnode* next pcur-next; free(pcur); pcur next; } free(*phead); *phead NULL; }四、双向链表的特点总结优势支持双向遍历找前驱和后继结点都很方便带头循环结构下头尾的插入、删除都是 O (1)无需遍历任意位置的插入删除逻辑统一边界情况少代码更简洁不足每个结点多了一个prev指针相比单链表内存开销更大仍然不支持随机访问按下标查找元素依然需要遍历时间复杂度 O (N)适用场景需要频繁在任意位置插入、删除元素需要双向遍历链表的业务场景对头部、尾部操作效率要求高的场完整代码gittee:https://gitee.com/yang-mianmian-1/doubly-linked-list