目录
1. 双向链表的结构
2.双向链表的实现
2.1 初始化
2.2 增
2.2.1 尾插
编辑
2.2.2 头插
3.删
2.3.1 尾删
2.3.2 头删
4. 找
5.任意位置插入
5.1 任意位置前插入
编辑
5.2 任意位置后插入
编辑
6. 任意位置删除
编辑
7. 改
8. 链表的销毁
3. 顺序表和双向链表的优缺点分析
4.完整代码
1. 双向链表的结构
这是带头双向链表
2.双向链表的实现
首先来定义节点的结构
typedef int typedata;struct ListNode
{typedata val;struct ListNode* prev;//后节点struct ListNode* next;//前节点
};typedef struct ListNode LNO;
2.1 初始化
在前面的文章中,一开始拿到的单链表多为空
双链表为空时,此时只剩下一个头节点
那么在初始化的时候,是否可以将哨兵位指向为空呢
此时看上文中的图,可以知道是不行的,这样他并没有循环起来
那么应该让他指向自身,使他自循环
那么干脆让每次申请的节点都先自循环
//申请节点
LNO* BuyNode(typedata X)
{LNO* newnode = (LNO*)malloc(sizeof(LNO));if (!newnode){perror("malloc fail!");exit(1);}newnode->val = X;newnode->prev = newnode;newnode->next = newnode;//自循环return newnode;
}LNOInit()
{LNO* pphead = BuyNode(-1);return pphead;
}//初始化链表
测试一下头节点初始化是否符合预期
#include"List.h"void test01()
{LNO* plist = LNOInit();
}
int main()
{test01();return 0;
}
可以看到是符合预期的
接下来要实现的就是增删查改
2.2 增
在进行增的操作时
要注意:哨兵位的节点不能删除,也不能被改变
所以,为了避免修改哨兵位,在函数传参中我们采用一级指针形式
2.2.1 尾插
在双向链表的末尾插入数据
那么首先,得找到双向链表的末尾
那么因为这里是循环链表肯定不能像之前的单链表那样通过判空来找尾节点
从图中不难发现尾节点就是plist->prev
进行数据的插入时,需要将原尾节点的next指向插入的节点,
新插入节点的prev指向原尾节点,next指针指向头节点
头节点的prev指针指向插入的节点
void LNOinsertback(LNO* phead, typedata X)
{LNO* newtail = BuyNode(X);LNO* ptail = phead->prev;ptail->next = newtail;//原节点指向新的尾节点phead->prev = newtail;//哨兵位的prev指向新节点newtail->prev = ptail;newtail->next = phead;
}
定义一个打印函数方便测试
从哨兵位后一个节点开始才是链表的有效数据,所以从哨兵位后一个节点开始打印
一次遍历下去打印完后再回到哨兵位就不用打印了
void printLNO(LNO* phead)
{assert(phead && phead->next);LNO* pres = phead->next;while (pres != phead){printf("%d->", pres->val);pres = pres->next;}
}
测试一下
void test02()
{LNO* plist = LNOInit();LNOinsertback(plist, 1);printLNO(plist);LNOinsertback(plist, 2);printLNO(plist);LNOinsertback(plist, 3);printLNO(plist);LNOinsertback(plist, 4);printLNO(plist);}
int main()
{test02();return 0;
}
可以看到是符合预期的
2.2.2 头插
这里需要注意的是这个头插中的头指的是哪个节点
如果是头节点
此时,让尾节点的next指向插入的节点,然后让插入的节点的next指向plist,prev指向尾节点
但是,这种插入方法不就是尾插吗
所以这里的“头”肯定不是指的头节点
而应该是第一个有效数据所在的节点前插入
让新插入节点的next指向原首个有效数据所在的节点,prev指向plist
原首个有效数据所在的节点的prev指向新插入的节点
让plist的next指向新插入的节点
void LNOinsertfront(LNO* phead, typedata X)
{LNO* newhead = BuyNode(X);LNO* pcur = phead->next;newhead->next = pcur;newhead->prev = phead;//让新插入节点的next指向原首个有效数据所在的节点,prev指向头节点pcur->prev = newhead; //原首个有效数据所在的节点的prev指向新插入的节点phead->next = newhead;//让头节点的next指向新插入的节点
}
测试一下
void test03()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);}
int main()
{test03();return 0;
}
测试一下
是可行的
3.删
2.3.1 尾删
删除尾节点,即删除plist->prev
删除后将原尾节点前一个节点的next指针指向plist
plist->prev指向原尾节点前一个节点
void LNOdelback(LNO* phead)
{assert(phead && phead->next);LNO* pcur = phead;LNO* del = pcur->prev;//原尾节点LNO* newtail = del->prev;//新的尾节点newtail->next = phead;//原尾节点前一个节点的next指针指向头节点pcur->prev = newtail; //头节点的prev指向原尾节点前一个节点free(del);del = NULL;
}
测试一下
void test04()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNOdelback(plist);printLNO(plist);LNOdelback(plist);printLNO(plist);LNOdelback(plist);printLNO(plist);LNOdelback(plist);printLNO(plist);}
int main()
{test04();return 0;
}
可以看到是可行的
2.3.2 头删
删除第一个有效数据节点,即plist->next
删除后第二个有效数据节点成为新首节点,新首节点的prev指向plist
plist->next指向新首节点
void LNOdelfront(LNO* phead)
{assert(phead && phead->next);LNO* pcur = phead;LNO* del = phead->next;LNO* newhead = del->next;//新首节点newhead->prev = pcur;//新首节点的prev指向头节点pcur->next = newhead;//头节点的next指向新首节点free(del);del = NULL;
}
测试一下
void test05()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNOdelfront(plist);printLNO(plist);LNOdelfront(plist);printLNO(plist);LNOdelfront(plist);printLNO(plist);LNOdelfront(plist);printLNO(plist);}
int main()
{test05();return 0;
}
是可行的
4. 找
查找某个数据是否存在表中,找到了返回对应节点的地址,找不到返回NULL
LNO* Find(LNO*phead,typedata X)
{LNO* pcur = phead->next;while (pcur != phead){if (pcur->val == X){return pcur;}pcur = pcur->next;}return NULL;
}
5.任意位置插入
要用到查找方法,所以放在这里说
5.1 任意位置前插入
使用查找方法查找要插入的位置pos
插入节点newnode
newnode的next指向pos,prev指向pos的前一个节点
让pos前一个节点的next指向newnode,pos的prev指向这个newnode
//任意位置前插入
void LNOinsertbefore(typedata X, LNO* pos)
{assert(pos);LNO* newnode = BuyNode(X);LNO* temp = pos->prev;newnode->next = pos;newnode->prev = temp;//newnode的next指向pos,prev指向pos的前一个节点temp->next = newnode;pos->prev = newnode;//让pos前一个节点的next指向newnode,pos的prev指向这个newnode
}
测试一下
void test06()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNO* find = Find(plist, 4);LNOinsertbefore( 5, find);printLNO(plist);find = Find(plist, 1);LNOinsertbefore(6, find);printLNO(plist);find = Find(plist, 3);LNOinsertbefore(7, find);printLNO(plist);
}
int main()
{test06();return 0;
}
符合预期
5.2 任意位置后插入
使用查找方法查找要插入的位置pos
插入节点newnode
newnode的prev指向pos,next指向pos的后一个节点
让pos的next指向newnode,pos后一个节点的prev指向这个newnode
//任意位置后插入
void LNOinsertafter(typedata X, LNO* pos)
{assert(pos);LNO* newnode = BuyNode(X);LNO* temp = pos->next;newnode->next = temp;newnode->prev = pos; //newnode的prev指向pos, next指向pos的后一个节点temp->prev = newnode;pos->next = newnode;//让pos的next指向newnode,pos后一个节点的prev指向这个newnode
}
测试一下
void test07()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNO* find = Find(plist, 4);LNOinsertafter(5, find);printLNO(plist);find = Find(plist, 1);LNOinsertafter(6, find);printLNO(plist);find = Find(plist, 3);LNOinsertafter(7, find);printLNO(plist);
}
int main()
{test07();return 0;
}
是可行的
6. 任意位置删除
要用到查找方法,所以放在这里说
先通过查找函数找到要删除的节点del
del前的节点的next指向del后节点
del后节点的prev指向del前节点
void LNOdel(LNO* del)
{LNO* temp1 = del->prev;//前节点LNO* temp2 = del->next;//后节点temp1->next = temp2;temp2->prev = temp1;//del前的节点的next指向del后节点del后节点的prev指向del前节点free(del);del = NULL;
}
测试
void test08()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNOinsertfront(plist, 5);printLNO(plist);LNO* find = Find(plist, 5);LNOdel(find);printLNO(plist);find = Find(plist, 3);LNOdel(find);printLNO(plist);find = Find(plist, 1);LNOdel(find);printLNO(plist);}int main()
{test08();return 0;
}
可行
7. 改
使用查找方法查找要修改的位置pos
把对应的节点值修改就行了
void LNOmodify(LNO* pos, typedata X)
{pos->val = X;
}void test09()
{LNO* plist = LNOInit();LNOinsertback(plist, 1);printLNO(plist);LNOinsertback(plist, 2);printLNO(plist);LNOinsertback(plist, 3);printLNO(plist);LNOinsertback(plist, 4);printLNO(plist);LNO* find = Find(plist, 4);LNOmodify(find, 5);printLNO(plist);find = Find(plist, 3);LNOmodify(find, 6);printLNO(plist);find = Find(plist, 2);LNOmodify(find, 7);printLNO(plist);find = Find(plist, 1);LNOmodify(find, 8);printLNO(plist);
}int main()
{test09();return 0;
}
8. 链表的销毁
因为是动态申请过来的空间,不使用后要将他释放
//链表的销毁
void LNOdestory(LNO* phead)
{LNO* pcur = phead->next;while (pcur != phead){LNO* save = pcur->next;LNOdel(pcur);pcur = save;//挨个挨个销毁}free(phead);phead = NULL;
}
测试
void test10()
{LNO* plist = LNOInit();LNOinsertback(plist, 1);printLNO(plist);LNOinsertback(plist, 2);printLNO(plist);LNOinsertback(plist, 3);printLNO(plist);LNOinsertback(plist, 4);printLNO(plist);LNOdestory(plist);plist = NULL;
}int main()
{test10();return 0;
}
通过调试看出,这里除了plist,都释放了
手动给plist置空
LNOdel和LNOdestory为什么不传二级指针
前文的函数中形参都是采用的一级指针
为了保持接口的一致性才传的一级,存在的问题就是形参phead释放置空后,实参plist不会置空,
因此要手动置空
更严谨来说在前文中任意位置删除的测试中,每删除一个位置都需要将find置空
void test08()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNOinsertfront(plist, 5);printLNO(plist);LNO* find = Find(plist, 5);LNOdel(find);find = NULL;printLNO(plist);find = Find(plist, 3);LNOdel(find);find = NULL;printLNO(plist);find = Find(plist, 1);LNOdel(find);find = NULL;printLNO(plist);}
3. 顺序表和双向链表的优缺点分析
不同点 | 顺序表 | 单链表 |
存储空间上 | 物理上连续 | 逻辑上连续,物理上不一定连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或删除 | 可能需要搬移元素,效率低O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够是需要扩容 | 没有容量的概念 |
应用场景 | 元素高效储存+频繁访问 | 任意位置插入或删除 |
4.完整代码
//List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义双向链表节点的结构typedef int typedata;
struct ListNode
{typedata val;struct ListNode* prev;//后节点struct ListNode* next;//前节点
};typedef struct ListNode LNO;LNO* BuyNode(typedata X);//申请节点LNO* LNOInit();//初始化void printLNO(LNO* phead);//打印函数void LNOinsertback(LNO* phead,typedata X);//尾插void LNOinsertfront(LNO* phead,typedata X);//头插void LNOdelback(LNO* phead);//尾删void LNOdelfront(LNO* phead);//头删LNO* Find(LNO*phead,typedata X);//查找void LNOinsertbefore(typedata X, LNO* pos);//任意位置前插入void LNOinsertafter(typedata X, LNO* pos);//任意位置后插入void LNOdel(LNO* pos);//任意位置删除void LNOmodify(LNO* pos, typedata X);//修改void LNOdestory(LNO* phead);//链表的销毁
//List.c
#include "List.h"//申请节点
LNO* BuyNode(typedata X)
{LNO* newnode = (LNO*)malloc(sizeof(LNO));if (!newnode){perror("malloc fail!");exit(1);}newnode->val = X;newnode->prev = newnode;newnode->next = newnode;//自循环return newnode;
}LNO*LNOInit()
{LNO* pphead = BuyNode(-1);return pphead;
}//初始化链表void printLNO(LNO* phead)
{assert(phead && phead->next);LNO* pres = phead->next;while (pres != phead){printf("%d->", pres->val);pres = pres->next;}printf("\n");
}void LNOinsertback(LNO* phead, typedata X)
{LNO* newtail = BuyNode(X);LNO* ptail = phead->prev;ptail->next = newtail;//原节点指向新的尾节点phead->prev = newtail;//哨兵位的prev指向新节点newtail->prev = ptail;newtail->next = phead;//新插入节点的prev指向原尾节点,next指针指向头节点
}//尾插void LNOinsertfront(LNO* phead, typedata X)
{LNO* newhead = BuyNode(X);LNO* pcur = phead->next;newhead->next = pcur;newhead->prev = phead;//让新插入节点的next指向原首个有效数据所在的节点,prev指向头节点pcur->prev = newhead; //原首个有效数据所在的节点的prev指向新插入的节点phead->next = newhead;//让头节点的next指向新插入的节点
}//头插//尾删
void LNOdelback(LNO* phead)
{assert(phead && phead->next);LNO* pcur = phead;LNO* del = pcur->prev;//原尾节点LNO* newtail = del->prev;//新的尾节点newtail->next = phead;//原尾节点前一个节点的next指针指向头节点pcur->prev = newtail; //头节点的prev指向原尾节点前一个节点free(del);del = NULL;
}//头删
void LNOdelfront(LNO* phead)
{assert(phead && phead->next);LNO* pcur = phead;LNO* del = phead->next;LNO* newhead = del->next;//新首节点newhead->prev = pcur;//新首节点的prev指向头节点pcur->next = newhead;//头节点的next指向新首节点free(del);del = NULL;
}LNO* Find(LNO*phead,typedata X)
{LNO* pcur = phead->next;while (pcur != phead){if (pcur->val == X){return pcur;}pcur = pcur->next;}return NULL;
}//任意位置删除
void LNOdel(LNO* del)
{LNO* temp1 = del->prev;//前节点LNO* temp2 = del->next;//后节点temp1->next = temp2;temp2->prev = temp1;//del前的节点的next指向del后节点del后节点的prev指向del前节点free(del);del = NULL;
}//任意位置前插入
void LNOinsertbefore(typedata X, LNO* pos)
{assert(pos);LNO* newnode = BuyNode(X);LNO* temp = pos->prev;newnode->next = pos;newnode->prev = temp;//newnode的next指向pos,prev指向pos的前一个节点temp->next = newnode;pos->prev = newnode;//让pos前一个节点的next指向newnode,pos的prev指向这个newnode
}//任意位置后插入
void LNOinsertafter(typedata X, LNO* pos)
{assert(pos);LNO* newnode = BuyNode(X);LNO* temp = pos->next;newnode->next = temp;newnode->prev = pos; //newnode的prev指向pos, next指向pos的后一个节点temp->prev = newnode;pos->next = newnode;//让pos的next指向newnode,pos后一个节点的prev指向这个newnode
}//修改
void LNOmodify(LNO* pos, typedata X)
{pos->val = X;
}//链表的销毁
void LNOdestory(LNO* phead)
{LNO* pcur = phead->next;while (pcur != phead){LNO* save = pcur->next;LNOdel(pcur);pcur = save;//挨个挨个销毁}free(phead);phead = NULL;
}
//test.c
#include"List.h"void test01()
{LNO* plist = LNOInit();
}void test02()
{LNO* plist = LNOInit();LNOinsertback(plist, 1);printLNO(plist);LNOinsertback(plist, 2);printLNO(plist);LNOinsertback(plist, 3);printLNO(plist);LNOinsertback(plist, 4);printLNO(plist);
}void test03()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);}void test04()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNOdelback(plist);printLNO(plist);LNOdelback(plist);printLNO(plist);LNOdelback(plist);printLNO(plist);LNOdelback(plist);printLNO(plist);}void test05()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNOdelfront(plist);printLNO(plist);LNOdelfront(plist);printLNO(plist);LNOdelfront(plist);printLNO(plist);LNOdelfront(plist);printLNO(plist);}void test06()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNO* find = Find(plist, 4);LNOinsertbefore( 5, find);printLNO(plist);find = Find(plist, 1);LNOinsertbefore(6, find);printLNO(plist);find = Find(plist, 3);LNOinsertbefore(7, find);printLNO(plist);
}void test07()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNO* find = Find(plist, 4);LNOinsertafter(5, find);printLNO(plist);find = Find(plist, 1);LNOinsertafter(6, find);printLNO(plist);find = Find(plist, 3);LNOinsertafter(7, find);printLNO(plist);
}void test08()
{LNO* plist = LNOInit();LNOinsertfront(plist, 1);printLNO(plist);LNOinsertfront(plist, 2);printLNO(plist);LNOinsertfront(plist, 3);printLNO(plist);LNOinsertfront(plist, 4);printLNO(plist);LNOinsertfront(plist, 5);printLNO(plist);LNO* find = Find(plist, 5);LNOdel(find);find = NULL;printLNO(plist);find = Find(plist, 3);LNOdel(find);find = NULL;printLNO(plist);find = Find(plist, 1);LNOdel(find);find = NULL;printLNO(plist);}void test09()
{LNO* plist = LNOInit();LNOinsertback(plist, 1);printLNO(plist);LNOinsertback(plist, 2);printLNO(plist);LNOinsertback(plist, 3);printLNO(plist);LNOinsertback(plist, 4);printLNO(plist);LNO* find = Find(plist, 4);LNOmodify(find, 5);printLNO(plist);find = Find(plist, 3);LNOmodify(find, 6);printLNO(plist);find = Find(plist, 2);LNOmodify(find, 7);printLNO(plist);find = Find(plist, 1);LNOmodify(find, 8);printLNO(plist);
}void test10()
{LNO* plist = LNOInit();LNOinsertback(plist, 1);printLNO(plist);LNOinsertback(plist, 2);printLNO(plist);LNOinsertback(plist, 3);printLNO(plist);LNOinsertback(plist, 4);printLNO(plist);LNOdestory(plist);plist = NULL;
}int main()
{test10();return 0;
}