说明：本笔记依照《王道论坛-数据结构》视频内容整理。
单链表：无法逆向检索，有时候不太方方便。
双链表：可进可退，存储密度更低一点。
一、双链表结点
typedef int ElemType; // 根据实际情况定义
typedef struct lNode{ // 定义单列表结点类型
ElemType data; // 每个结点存放一个数据元素
struct lNode *prior,*next; // prior指向前驱结点，next指向后驱结点
}lNode, *linkList; // lNode 强调是一个结点，linkList 强调是一个链表
二、操作
int initList(linkList *l); // 初始化双链表
int destroyList(linkList *l); // 销毁双链表
int listInsert(linkList *l,int i,ElemType e); // 按位序插入
int listDelete(linkList *l,int i,ElemType *e); // 按位序删除
lNode* locateElem(linkList l,ElemType e); // 按值查找
lNode* getElem(linkList l,int i); // 按位查找
int printfList(linkList l); // 打印链表
int insertNextNode(lNode *p,lNode *s); // 结点后插
int insertPriorNode(lNode *p,lNode *s); // 结点前插
int tailInsert(linkList l,ElemType e); // 尾插法
int headInsert(linkList l,ElemType e); // 头插法
1、InitList(&L)
双链表初始化。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* 备注：带头结点初始化
****************************************/
int initList(linkList *l)
{
*l = (lNode*)malloc(sizeof(lNode)); // 为头结点分配空间
if(*l == NULL) return 1; // malloc 调用失败
(*l)->prior = NULL; // 初始化头结点中 prior 变量
(*l)->next = NULL; // 初始化头结点中 next 变量
(*l)->data = 0; // 初始化头结点中 data 变量
return 0;
}
2、DestroyList(&L)
双链表销毁。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* 备注：带头结点初始化
****************************************/
int destroyList(linkList *l)
{
lNode *d = *l; // d 指向要释放的结点（选择释放结点）
while(d != NULL){ // 判读结点是否全部释放
(*l) = d->next; // 调整列表（去除释放结点后的链表）
printf("d->data = %d\n",d->data); // 做调试使用，查看是否能全部销毁
free(d); // 释放链表
d = *l; // 提取下一个释放结点
}
return 0;
}
3、ListInsert(&L,i,e)
按位序插入。在表 L 中的第 i 个位置插入指定元素 e。
设计思路：找到第 i-1 个节点，将新节点插入其后。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* i - 要插入的位置
* e - 新结点存储的数据
* 备注：带头结点初始化
****************************************/
int listInsert(linkList *l,int i,ElemType e)
{
if(i<1) return 1; // i 值不合法
lNode *p = NULL; // 指针 p 指向当前扫描的结点
int j = 0; // 当前 p 指向是第几个结点
p = *l; // *l 指向头结点，头结点是第 0 个结点，不存在数据
while(p!=NULL && j<i-1){ // p!=NULL 确保在链表有效范围内
p = p->next;
j++;
}
if (p == NULL) return 1; // i 值不合法
lNode *s = (lNode*)malloc(sizeof(lNode)); // 创建新结点
s->data = e; // 给新结点赋值
s->next = p->next; // 调整链表
if(p->next != NULL) p->next->prior = s; // 最后一个结点不需要向前指（要特别注意）
s->prior = p;
p->next = s;
/* 以上赋值代码特变注意，否则会出现链表断裂情况 */
return 0;
}
4、ListDelete(&L,i,&e)
按位序删除。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
设计思路：找到第 i-1 个节点，释放第 i 个结点。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* i - 要删除的位置
* e - 返回删除结点数据
* 备注：带头结点初始化
****************************************/
int listDelete(linkList *l,int i,ElemType *e)
{
if(i < 1) return 1; // i 值不合法
lNode *p = NULL; // p 指向当前扫描的结点
int j = 0; // 当前 p 指向的第几个结点
p = *l; // p 指向头结点，头结点为第 0 个结点，不存放数据
while(p!=NULL && j<i-1){ // p!=NULL - 确保在单链表有效范围内，j<i-1 - 寻找 i-1 个结点
p = p->next;
j++;
}
if(p == NULL) return 1; // i 值不合法
if(p->next == NULL) return 1; // 第 i-1 个结点之后无其他结点（处理最后一个结点）
lNode *s = p->next; // s 指向被删除结点
(*e) = p->data; // 用 e 返回元素的值
p->next = s->next; // 调整链表链接关系
if(s->next!=NULL) s->next->prior = p; // 特别注意
free(s); // 释放结点
return 0;
}
5、LocateElem(L,e)
按值查找操作。在表 L 中查找具有给定关键字值的元素。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* e - 要查找的数据
* 备注：带头结点初始化
****************************************/
lNode* locateElem(linkList l,ElemType e)
{
lNode *p = l->next;
while(p!=NULL && p->data!=e){ // 从第 1 个结点开始查找数据域为 e 的结点
p=p->next;
}
return p; // 返回第一个数据为 e 的结点指针，否则返回 NULL
}
6、GetElem(L,i)
按位查找。返回第 i 个元素。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* i - 要查找的位序
* 备注：带头结点初始化
* 备注：如果 i=0，返回头结点地址，如果 i 超过链表长度，返回NULL
****************************************/
lNode* getElem(linkList l,int i)
{
if(i<0) return NULL; // i 值不在合法范围
lNode *p = NULL; // p 指向当前扫描的结点
int j = 0; // 表示 p 当前指向第几个结点
p = l; // 将 p 值指向头结点（相当于第0个结点，不存在数据）
while(p!=NULL && j<i){
p=p->next;
j++;
}
return p;
}
7、Length(L)
获取链表长度。
未实现。
8、PrintfList(L)
打印链表内容。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* 备注：带头结点初始化
****************************************/
int printfList(linkList l)
{
lNode *p = l;
while(p != NULL){
printf("p->data = %d\n",p->data); // 不同类型，打印语句不同
p = p->next;
}
return 0;
}
9、InsertNextNode(p,s)
/****************************************
* p - 链表中某一结点指针
* s - 要插入的结点
* 备注：带头结点初始化
****************************************/
int insertNextNode(lNode *p,lNode *s)
{
if(p==NULL || s==NULL) return 1; // 非法参数
s->next = p->next; // 调整链表
if(p->next!=NULL) p->next->prior=s; // 要特别注意
s->prior=p;
p->next=s;
return 0;
}
10、InsertPriorNode(p,s)
按结点前插。在 p 结点之前查找结点 s。
/****************************************
* p - 链表中某一结点指针
* s - 要插入的结点
* 备注：带头结点初始化
****************************************/
int insertPriorNode(lNode *p,lNode *s)
{
if(p==NULL || s==NULL) return 1; // 非法参数
s->prior=p->prior; // 调整链表
if(p->prior!=NULL) p->prior->next=s; // 要特别注意
s->next=p;
p->prior=s;
return 0;
}
11、tailInsert(l,e)
链表后插操作。主要用于单链表创建。
链表后插操作单链表建立流程：
1、初始化一个单链表。
2、每次取一个数据插入到表尾。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* e - 要插入的数据
* 备注：带头结点初始化
* 缺点：每插入一个数据，都需要遍历一次链表（时间复杂度高）
****************************************/
int tailInsert(linkList l,ElemType e)
{
// 1、遍历单链表,找到最后一个结点
lNode *s = l;
while(s->next!=NULL){
s = s->next;
}
// 2、创建新结点
lNode *p = (lNode*)malloc(sizeof(lNode));
p->data = e;
// 3、使用结点后插操作进行插入结点
return insertNextNode(s,p);
}
12、headInsert(l,e)
链表头插操作。主要用于单链表创建。
链表头插操作单链表建立流程：
1、初始化一个单链表。
2、每次取一个数据插入到表头。
/****************************************
* l - 要操作的顺序表首地址(l是指针类型)
* e - 要插入的数据
* 备注：带头结点初始化
****************************************/
int headInsert(linkList l,ElemType e)
{
// 1、创建新结点
lNode *p = (lNode*)malloc(sizeof(lNode));
p->data = e;
// 对链表头结点使用结点后插操作
return insertNextNode(l,p);
}
三、总结
1、在更改链表时代码有所区别，单链表操作一个指针，双链表操作两个指针。
2、不涉及链表更改，操作相同