在学习双链表之前，可先复习巩固一下单链表，双链表这个删改查原理与单链表大致相同。
原文博客如下 单链表的增删改查
一、双链表的特点
与单链表不同是，单链表指针域中只有next指针，而双链表有两个指针，前驱指针prior和后继指针next。但是思路与单链表基本类似，不同的是指针指向必须是双向的，a->b,b->a。
二、双链表的组成
prior前驱指针+数据域data+next后继指针。
三、代码实现
结构体
typedef int ElemType;
typedef struct DNode{
ElemType data; // 数据域
struct DNode* prior; // 前驱
struct DNode* next; // 后继
}DNode,*DLinkList;
1.头插法
// 头插法
DLinkList DLinkList_head_insert(DLinkList& DL) {
// 申请空间，带头结点的链表
DL = (DLinkList)malloc(sizeof(DNode));
DL->prior = NULL;
DL->next = NULL;
DLinkList s;
int x;
scanf("%d", &x);
while (x != 9999) {
// 给这个元素申请空间
s = (DLinkList)malloc(sizeof(DNode));
s->data = x; // 将输入的值赋给数据域
s->next = DL->next;
if (DL->next != NULL) { // 注意这个判断，即后边有元素
DL->next->prior = s;
}
s->prior = DL;
DL->next = s;
scanf("%d", &x); // 输入下一个元素
}
return DL;
}
2.尾插法
// 尾插法
DLinkList DLinkList_tail_insert(DLinkList& DL) {
// 申请空间，带头结点的链表
DL = (DLinkList)malloc(sizeof(DNode));
DL->prior = NULL;
DL->next = NULL;
DLinkList s, r = DL;
int x;
scanf("%d", &x);
while (x != 9999) {
// 申请空间
s = (DLinkList)malloc(sizeof(DNode));
s->data = x;
r->next = s;
s->prior = r;
r = s; // r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL;
return DL;
}
3.按序号查找
// 按序号查找元素
DLinkList GetElem(DLinkList DL, ElemType& e) {
if (0 == e) {
return DL;
}
if (e < 0) {
return NULL; // e是负值
}
DLinkList p = DL->next; // 因为头指针为空，要指向有元素的，即第一个结点
for (int i = 1; i < e; i++) {
p = p->next;
}
return p;
}
4.按值查找
// 按值查找
DLinkList LocateElem(DLinkList DL, ElemType e) {
DLinkList p = DL->next; //头指针为空，要指下第一个结点
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}
5.某个位置插入元素
// 某个位置插入元素
bool InsertDList(DLinkList& DL, ElemType e, int i) {
// 先找到要插入元素的上一元素
e = e - 1;
DLinkList p = GetElem(DL, e);
if (p == NULL) {
return false;
}
// 给要插入的元素申请空间
DLinkList s = (DLinkList)malloc(sizeof(DNode));
s->data = i; // 将值赋给data域
s->next = p->next;
if (p->next != NULL) {
p->next->prior = s;
}
s->prior = p;
p->next = s;
return true;
}
6.某个位置删除元素
// 某个位置删除元素
bool DelDList(DLinkList& DL, ElemType e) {
// 获取这个元素的上一位置
e = e - 1;
DLinkList p = GetElem(DL, e);
if (p == NULL) {
return false;
}
DLinkList q = p->next; // 要删除的元素
p->next = q->next;
if (q->next != NULL) {
q->next->prior = p;
}
free(q);
q = NULL;
return true;
}
打印链表
// 打印链表
void PrintDLinkList(DLinkList DL) {
DL = DL->next;
while (DL != NULL) {
printf("%3d", DL->data);
DL = DL->next;
}
printf("\n");
}
芜湖~今日学习也有好好打卡呢）