数据结构笔记第3篇：双向链表

1、双向链表的结构

注意：这里的 "带头" 跟前面我们说的 "头结点" 是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表里的头结点，实际为 "哨兵位" ，哨兵位节点不存储任何有效元素，只是站在这里 "放哨的"。

"哨兵位" 存在的意义：

遍历循环链表避免死循环。

注意：双向链表中，哨兵位的下一个节点是链表的第一个节点(头结点)。哨兵位的前一个节点是链表的最后一个节点(尾结点)。所以双向链表的头插是在哨兵位的后面插入数据。尾插则是在哨兵位之前插入数据。

哨兵位是作为头结点和尾结点的中点，是头结点的起点也是尾节点的终点。这样解释更容易理解。

2、双向链表的实现

List.h 链表函数和链表节点类型的声明：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct ListNode
{SLDataType data;//存储数据struct ListNode* prve;//存储前一个节点的地址struct ListNode* next;//存储下一个节点的地址
}SList;
SList* SLInit();void SLPushBack(SList* phead, SLDataType x);//尾插
void SLPrint(SList* phead);//显示链表数据
void SLPustFront(SList* phead, SLDataType x);//头插
void SLPopBack(SList* phead);//尾删
void SLPopFront(SList* phead);//头删
void SLInsert(SList* pos, SLDataType x);//指定位置插入
SList* SLfind(SList* phead, SLDataType x);//查找节点
void SLEarse(SList* pos);//指定位置删除
void SLDestory(SList** pphead);//链表销毁

List.c 链表函数的实现:

#include "List.h"
//链表初始化
SList* SLInit()
{SList* phead = (SList*)malloc(sizeof(SList));if (phead == NULL){perror("malloc error");return NULL;}phead->data = -1;//因为是循环链表，所以初始化要遵循循环格式phead->next = phead;phead->prve = phead;return phead;
}
//创建链表节点
SList* ListBuyNode(SLDataType x)
{SList* retNode = (SList*)malloc(sizeof(SList));if (retNode == NULL){perror("malloc error");return NULL;}retNode->data = x;retNode->prve = retNode;retNode->next = retNode;return retNode;
}
//链表尾插
void SLPushBack(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->prve = phead->prve;Node->next = phead;phead->prve->next = Node;phead->prve = Node;
}
//链表数据显示
void SLPrint(SList* phead)
{assert(phead);SList* pcur = phead->next;while (pcur != phead)//哨兵位作为结束标识{printf("%d", pcur->data);if (pcur->next != phead)printf("->");pcur = pcur->next;}printf("\n");
}
//链表头插
void SLPustFront(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->next = phead->next;Node->prve = phead;phead->next->prve = Node;phead->next = Node;
}
//链表尾删
void SLPopBack(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->prve;del->prve->next = phead;phead->prve = del->prve;free(del);del = NULL;
}
//链表头删
void SLPopFront(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->next;del->next->prve = phead;phead->next = del->next;free(del);del = NULL;
}
//指定位置插入
void SLInsert(SList* pos, SLDataType x)
{assert(pos);SList* Node = ListBuyNode(x);Node->next = pos->next;Node->prve = pos;pos->next = Node;Node->next->prve = Node;
}
//查找节点
SList* SLfind(SList* phead, SLDataType x)
{assert(phead);SList* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//指定位置删除
void SLEarse(SList* pos)
{assert(pos);pos->prve->next = pos->next;pos->next->prve = pos->prve;free(pos);pos = NULL;
}
//链表销毁
void SLDestory(SList** pphead)
{assert(pphead && *pphead);SList* pcur = (*pphead)->next;while (pcur != *pphead){SList* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}

test.c 函数的调用:

#include "List.h"void SLtest()
{SList* plist = NULL;plist = SLInit();//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//打印:1->2->3->4//头插SLPustFront(plist, 5);SLPustFront(plist, 6);SLPustFront(plist, 7);SLPrint(plist);//打印:7->6->5->1->2->3->4//尾删SLPopBack(plist);SLPrint(plist);//打印:7->6->5->1->2->3//头删SLPopFront(plist);SLPrint(plist);//打印:6->5->1->2->3//指定位置插入SList* find = SLfind(plist, 5);SLInsert(find, 11);SLPrint(plist);//打印:6->5->11->1->2->3//指定位置删除find = SLfind(plist, 1);SLEarse(find);SLPrint(plist);//打印:6->5->11->2->3//链表销毁SLDestory(&plist);
}
int main()
{SLtest();return 0;
}

3、顺序表和双向链表的优缺点分析

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需要修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁