链表的一些形式与结构

链表的话有很多结构，但是学习的话只需要学习几种经典结构就可以了：

1. 单向链表与双向链表。单链表的话，有一个非常不好的地方就在于他只能往后找，但是他找不到前面

2. 有哨兵位头结点链表与没有哨兵位头结点的链表。哨兵位头结点不存储任何有效数据，仅仅就是站岗做标识，好处就在于不用判空，只管链接就可以。一般情况下，也不能随意滥用，尤其是对于单链表而言，一般是不喜欢带头的，因为带头的话价值也不大。你去看看OJ里面带不带头的？没一个带头的吧

3. 循环链表与不循环链表。循环与带环是不一样的，循环是又指向头结点，如果有哨兵位的话，就再指向哨兵位头结点。

所以总共2＊2＊2共八种结构。

以下将介绍双向循环带头链表（我直接简称双向链表）

双向带头循环链表需要注意：没有死角，没有NULL，只管链接

双向链表的节点(结构体)创建

1. 在这里面需要两个指针，一个prev，一个next，这边不能忘记之前结构体创建的知识，结构体创建出来的时候，里面的结构体成员是没有办法进行初始化的。

2. 这个时候双向链表的哨兵位头结点的实体还没有创建(malloc)出来，等到初始化的阶段，我就会去malloc一个哨兵位头结点。

//双向链表的节点(结构体)创建
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;

双向链表的节点新增

1. 首先如果要去新创建一个节点的话，必须得用malloc，也就是说向堆区申请一个结构体大小的内存。然后这个新的节点被开辟出来之后，因为一个节点里面他都带有两个指针，需要先把这两个指针都给它变成空指针NULL。

2. 在增加节点的时候，对于那个新malloc.出来的那个节点的话，它的prev与next指针不要自己指向自己，这样的话是没有意义的，就都给他们初始化成空指针就可以了，就是单纯的为了防止野指针。

//双向链表的节点新增
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("BuyLTNode::Malloc");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}

双向链表的初始化

1. 你会发现之前的单链表就没有初始化，但是顺序标的话也是有初始化的，主要是看你的结构，如果是一个单链表的话，我在一开始去创建一个指向第一个节点的一个指针，但这个指针只有这么一个，因此没有必要对它进行初始化，直接把这个指针指空NULL就完事儿了，没有必要去单独创建一个函数。顺序表之所以需要单独去写一个初始化的函数，因为那个初始化操作不是两三句话就能够搞定，首先比如说要把他的size变为0，然后它的容量有多少也需要去确定好，与此同时还要在初始化的时候去向堆区动态申请一块空间，因此初始化的时候需要有很多操作，所以说需要去单独创建一个函数，但是单链表的话就没有这个必要。

2. 接下来就要去想一想带头双向循环的初始状态应该是怎么样的，首先必须得先有一个哨兵位头结点，然后这个头节点的prev和next都是指向自己当前这个自己的哨兵位头结点，这样子才能代表循环（循环的体现主要在两方面：尾节点的next指针应该要指向哨兵位头结点，哨兵位头结点的prev要指向尾结点）

3. 之前讲的其实还并不是最重要的，因为假设我的参数里面传过来的是一个指针，然后我在函数里面创建了一个新的哨兵位头结点，那么我就需要把函数外头的那个指针指向的位置变成这个刚开辟出来的哨兵位头结点的地址，那么既然要改变这个指针所指向的位置，按道理来说是应该要传入一个二级指针，但是也可以只传入一级指针，然后把这个函数的返回类型改成返回一个地址，这样子，你在函数外头接收一下，你就能够轻而易举的找到那个哨兵位头结点的地址，这时候也不需要传入什么指针了，参数不需要，我给你返回过来哨兵位头结点的地址。

//双向链表的初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

双向链表的打印

1. 刚开始的cur肯定不能指向哨兵位头结点，因为那个节点里面不存储任何有效的数据，而最开始应该指向哨兵位头结点next指向的那个节点

2. 并且在这边必须得控制循环结束的条件，不然的话是死循环。循环结束的条件实际上很简单，就是说当你这个cur的指针一旦走到了哨兵位头结点，那么这时候函数就结束。

//双向链表的打印
void LTPrint(LTNode* phead)
{assert(phead);printf("<=head=>");LTNode* cur = phead->next;while (cur != phead){printf("%d=>", cur->data);cur = cur->next;}printf("\n");
}

双向链表的尾插

1. 以前的单链表而言，如果想要实现尾插的话，首先得必须找到尾巴在哪边，因此需要从头开始，一直往后去循环，但因为现在这边是双向循环链表，尾结点的地址可以轻松的找到，因为哨兵位头结点的prev就是指向尾结点，瞬间找到尾。

2. 在找到尾结点的地址之后，只需要去改动四个指针就可以了，当然因为既然是插入操作，所以说BuyLTNode去新创建一个节点并返回新节点的地址newnode是基本操作，不可少的，这个单链表也一样的。

3. 而且之前的单链表在尾插的时候，还需要注意一个特殊情况，就是说当这个单链表原先是空链表的时候，如果进行尾插的话，这时候还需要去改动phead的指向位置，因此既然要完成这些操作，不传二级指针是没有办法的。然而现在双向链表的话是不存在之前的那些情况，因为就算链表是空的，你还是有一个节点，因为你最初最初你就自带一个哨兵位头结点。

4. 而且最为厉害的一个地方在于什么呢，因为对于现在这个双向链表而言，我们在进行尾插的时候需要改动四个指针，我们发现那个代码逻辑对于链表为空的情形也是完全适用的（此时此刻还有一个哨兵位头结点），因此不需要去额外的对特殊情况进行重新写一段代码。

5. 而且在这个地方的话也并不需要二级指针，因为我们改动的都是结构体里面的成员，所以说只需要传结构体指针就可以了，也就是说，只需要一级指针。

6. 但是断言还是需要的，自己去想一想就OK了。

//双向链表的尾插
void LTPushBack(LTNode* phead,LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

双向链表的头插

//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;first->prev = newnode;newnode->next = first;newnode->prev = phead;phead->next = newnode;
}

双向链表的尾删

1. 现在这种结构的话非常简单，又简单又高效，只要简简单单的两步就可以搞定。

2. 当然这边还有一点是与单链表一模一样的，就是说当你链表是空的时候，是不能够删除的。

3. 然后判断一个双向链表是不是空链表，它也非常的简单。需要去判断phead的next指针指向的位置是不是phead自己，如果说是指向自己的，说明这个链表就是空的。

4. 删除的时候需要自己找到两个指针，一个是tail，一个是tailprev。

//双向链表的尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;
}

双向链表的头删

//双向链表的头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}

双向链表的在pos节点之前插入

1. 注意在双向带头链表当中，每一个节点的每一个两个指针都不可能是空指针，都会指向一个实体，因此判空这种情况是不需要特别考虑的，除非说在删除的时候，去判断一下当前这个链表是不是空链表

2. 当然这时候需要对pos进行判断，我说给我传进来的pos是空指针，还插入个屁呀，到这时候你就发现这种操作都是单纯的去改一下前后关系，因为双向带头链表示没有死角的。因为在任意位置都有前一个与后一个，同时也不可能有空。

3. Insert函数在真正使用的时候需要与find函数进行配合

//双向链表的在pos节点之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}