【数据结构初阶】--- 双链表

本文主要是介绍【数据结构初阶】--- 双链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

双链表你要了解的

双链表：

带头双链表
循环双链表
带头循环双链表
今天我们学习的，就是最强双链表 — 带头循环双链表
下图就是带头循环双链表，所谓带头，就是有哨兵位，那么最左边的节点就是哨兵位，是不计入链表的节点数，并且不存储数据，那用来做什么呢？同学们可以提前猜想它的作用，后面我会解答的

在这里插入图片描述

带头循环双链表的特点

从三个维度分析：

带头：所谓带头就是有哨兵位，
- 先试想，在学单链表的时候，如果这个单链表没有哨兵位，还想进行头插，此时新的结点已经成为链表的头结点，那么此时若没有将函数外的头指针的地址传入进来，那么头指针指向的还是原来的结点，所以要传头指针的地址作为实参传入进来，再通过解引用使这个头指针指向新的结点。
- 当你现在有了哨兵位，哨兵位是个结点，类型是个结构体，将哨兵位的地址传递过来，是可以在函数内部更改这个哨兵位的指向，头插时将哨兵位中的指针指向新的结点。
- 优点：不难看出，有了哨兵位就不再需要传递指针的地址，更不用在函数内部用二级指针接收，实在方便
循环：尾结点的next指针指向哨兵位，哨兵位的prev指针指向尾结点
- 优点：当你想进行尾插、尾删这类操作时，不用再将链表从头遍历到尾。此时进行各类操作时，结束操作的条件，从找NULL变为了找哨兵位
双链表：一个结点存一个数据，和两个指针，分别为：指向前一个结点的指针prev，指向后面一个结点的指针next
- 优点：当你想对链表进行插入或删除操作时，通常需要记录前一个结点的位置，这样在实际操作中并不方便，而双链表中的指针prev就好像为解决这个而生，专门来存放前一个结点的地址

双链表的结构

typedef int LTDataType;//存放数据的类型
typedef struct LTNode
{struct LTNode* prev;//指向前一个结点的指针struct LTNode* next;//指向后一个结点的指针LTDataType data;
}LTNode;

双链表的操作

了解了双链表的特点，也该真实体会下双链表的方便，帮我们省去了很多要分类讨论的情况

初始化

思路：
初始化的时候我们就要创建一个哨兵位，对这个哨兵位进行初始化，哨兵位的prev和next指针都指向自己，里面的data实际上用不上，可以赋值也可以不管，最后返回哨兵位的地址，函数外面实际早已经创建好一个头指针，用来存放这个哨兵位的地址

LTNode* LTInit( )
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc fail");return;}phead->prev = phead;phead->next = phead;phead->data = -1;return phead;
}

打印

思路：
遍历结束的条件与单链表不同，结束条件是遇到哨兵位

void LTPrint(LTNode* phead)
{assert(phead != NULL);LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}
}

创建一个结点

思路：
创建一个新节点，注意将里面的指针置空，避免成为野指针

LTNode* LTNodeCreat(LTDataType x)
{LTNode* new_node = (LTNode*)malloc(sizeof(LTNode));if (new_node == NULL){perror("malloc fail");return;}new_node->prev = NULL;new_node->next = NULL;new_node->data = x;return new_node;
}

头插

思路：
申请一个临时指针指向当前的头结点，方便修改哨兵位、新节点、老头结点（插入前的头结点）的指针指向

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead != NULL);LTNode* nxt = phead->next;LTNode* new_node = LTNodeCreat(x);phead->next = new_node;new_node->prev = phead;new_node->next = nxt;nxt->prev = new_node;}

尾插

思路：
和头插思路一样，申请一个临时指针指向尾结点，方便修改哨兵位、新节点、老的尾结点（插入前的尾结点）的指针指向

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead != NULL);LTNode* tail = phead->prev;LTNode* new_node = LTNodeCreat(x);phead->prev = new_node;new_node->next = phead;new_node->prev = tail;tail->next = new_node;}

头删

思路：
要考虑只有哨兵位的时候就不能删了
申请两个指针，一个指针head指向当前的头结点，一个指针head_next指向头节点的下一个节点（即将成为新的头结点），在进行头删操作会方便些，而且代码的可读性很好
不申请也行，就是可读性不强

void LTPopFront(LTNode* phead)
{assert(phead != NULL);assert(phead->next != phead);//只有哨兵位的时候就不能删了LTNode* head = phead->next;LTNode* head_next = head->next;phead->next = head->next;head_next->prev = phead;free(head);head = NULL;}

尾删

思路：
与头插的思路一致

void LTPopBack(LTNode* phead)
{assert(phead != NULL);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tail_prev = tail->prev;tail_prev->next = phead;phead->prev = tail_prev;free(tail);tail = NULL;
}

查找结点并返回

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead != NULL);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

在pos之前插入

在指定位置前插入节点，插入的思路已将在前面讲过，不变，只是多了个寻找pos位置的遍历操作

void LTInsert(LTNode* phead, LTNode* pos, LTDataType x)
{assert(phead != NULL);assert(pos != NULL);LTNode* new_node = LTNodeCreat(x);LTNode* cur = phead->next;LTNode* cur_prev = phead;while (cur != phead){if (cur == pos){cur_prev->next = new_node;new_node->prev = cur_prev;new_node->next = cur;cur->prev = new_node;}cur_prev = cur;cur = cur->next;}
}

删除pos位置的值

void LTErase(LTNode* phead, LTNode* pos)
{assert(phead != NULL);assert(pos != NULL);LTNode* cur = phead->next;while (cur != phead){if (cur = pos){cur->prev->next = cur->next;cur->next->prev = cur->prev;free(cur);cur = NULL;return;}cur = cur->next;}
}

销毁双链表

注意：

哨兵位也要销毁，函数执行完虚手动将头指针置空

void LTDestory(LTNode* phead)
{assert(phead != NULL);LTNode* cur = phead->next;while (cur != phead){LTNode* nxt = cur->next;free(cur);cur = nxt;}//哨兵位也要销毁free(cur);cur = NULL;
}