（C语言）双向链表

目录

链表的分类

双向链表的实现

1）定义链表

2）初始化双向链表

3）申请节点

4）尾插

5）头插

6）打印链表

7）尾删

8）头插

9）查找

10）指定位置删除

11）在指定位置后删除

12）销毁链表

---

链表的分类

根据链表的三个特点（带头/不带头，单向/双向，循环/不循环），可以将链表分为8种。常见的有两种：单链表（单向不带头不循环链表），双链表（双向带头循环链表）。是否带头指的是有没有头节点。链表（全网最详细）-CSDN博客。单链表已经写过了，此处我们将双链表。

双向链表的实现

1）定义链表

typedef int SLDateType;//定义双向链表
typedef struct ListNode
{SLDateType date;   //节点中的邮箱有效数据struct ListNode* next;  //保存下一个节点地址struct ListNode* prev;   //保存上一个节点的有效地址
}LN;

2）初始化双向链表

双链表的初始化，主要是创建头节点，即哨兵位。

//双链表的初始化
void List_start(LN** head)
{*head = (LN*)malloc(sizeof(LN));(*head)->date = -1;//给哨兵位一个数据，但是它其实是无效数据//注意因为是循环链表，所以当只有一个哨兵位的时候，要让它指向它自己；(*head)->next = (*head)->prev = (*head);
}

3）申请节点

//申请节点
LN* ListBuyNode(SLDateType x)
{LN* newnode = (LN*)malloc(sizeof(LN));newnode->date = x;//因为是双向循环链表，永远不会走到空，所以将新节点也指向其自己newnode->next = newnode->prev = newnode;return newnode;
}

4）尾插

注意：除了双向链表的初始化以及销毁要传二级指针，其他函数均采用一级指针，因为哨兵位在被定义后就不能再对他进行修改了。

//双向链表的尾插
void SLpushback(LN* head, SLDateType x)
{LN* newnode = ListBuyNode(x);//对头节点head，尾节点head->prev，新节点newnodenewnode->next = head;newnode->prev = head->prev;head->prev->next = newnode;head->prev = newnode;
}

5）头插

头插是指查到烧饼位的后面。

//双向链表的头插
void SLpushfront(LN* head, SLDateType x)
{LN* newnode = ListBuyNode(x);//对head newnode head->next进行修改newnode->next = head->next;newnode->prev = head;head->next->prev = newnode;head->next = newnode;
}

6）打印链表

//打印双向链表
void SLPrint(LN* head)
{LN* pcur = head->next;while (pcur != head){printf("%d ", pcur->date);pcur = pcur->next;}
}

7）尾删

//双链表尾删
void SLDelback(LN* head)
{//对head head->prev head->prev->prevLN* del = head->prev;head->prev = del->prev;del->prev->next = head;free(del);del = NULL;
}

8）头插

//双链表的头插
void SLDelfront(LN* head)
{//对head head->next head->next->next进行调整LN* del = head->next;head->next = del->next;del->next->prev = head;
}

9）查找

找双向链表中查找数据，并返回节点；

//双链表的查找
LN* SLFind(LN* head,SLDateType x)
{LN* pcur = head->next;while (pcur != head){if (pcur->date == x)return pcur;pcur = pcur->next;}return NULL;
}

10）指定位置删除

//指定位置删除
void SLDEL(LN* head, LN* pos)
{//删除pos节点//对pos->prev pos pos->next进行操作pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

11）在指定位置后删除

//在指定位置后插入
void LInsert(LN* pos, SLDateType x)
{LN* newnode = ListBuyNode(x);//对pos  newnode  pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

12）销毁链表

//销毁链表
void LDestory(LN** head)
{//循环删除节点LN* pcur = (*head);while (pcur != *head){LN* next = pcur->next;free(pcur);pcur = next;}free(*head);*head = NULL;
}