史上最强数据结构----双向循环链表的实现（带哨兵位）

史上最强数据结构----双向循环链表的实现（带哨兵位）

1、双向链表的基本结构

图示：

2、双向链表的基本结构实现

代码：

typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;//存储的数据
    struct ListNode* next;//存储下一个节点的地址
    struct ListNode* prev;//存储上一个节点的地址
}ListNode;

3、双向链表的初始化

图示：

代码：

第一种：传二级指针的

void ListInit(ListNode** phead);//初始化函数的声明
void ListInit(ListNode** phead)//为什么要传二级指针，因为改变的是结构体的指针，所以要传结构体的指针
{
    assert(phead);
    *phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点，存储的是无效数据，-1也是随便给的
    (*phead)->next = (*phead);
    (*phead)->prev = (*phead);
    //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己，形成双向循环结构
}
//下面是main函数中调用初始化函数的地方，为了方便理解二级指针
int main()
{
    ListNode*phead = NULL;//初始化之后，phead就会指向哨兵位，即NULL发生了改变，即改变的是结构体的指针，所以要传二级指针
    ListNode(&phead);
    return 0;
}

第二种：不传二级指针的

ListNode* ListInit(ListNode* phead);//初始化函数的声明
ListNode* ListInit()//此处为什么不传二级指针，因为在函数中会将开辟的哨兵位的地址作为返回值返回
{
    ListNode*phead = NULL;
    phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点，存储的是无效数据，-1也是随便给的
    phead->next = phead;
    phead->prev = phead;
    //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己，形成双向循环结构
}
int main()
{
    ListNode*phead = ListInit();
    return 0;
}

4、双向链表的尾插

图示：

代码：

void ListPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);//哨兵位不可为空
    ListNode* newnode = BuyListNode(x);
    ListNode* tail = phead->prev;
    tail->next = newnode;//(1)
    newnode->prev = tail;//(2)
    newnode->next = phead;//(3)
    phead->prev = newnode;//(4)
}

5、双向链表的尾删

图示：

代码：

void ListPopBack(ListNode* phead)
{
    assert(phead);
    assert(phead->next == phead);//链表为空
    ListNode* tail = phead->prev;
    ListNode* tailPrev = tail->prev;

    free(tail);
    tail = NULL;

    tailPrev->next = phead;//(1)
    phead->prev = tailPrev;//(2)
}

6、双向链表的头插

图示：

代码：

void ListPushFront(ListNode* phead,LTDataType x)
{
    assert(phead);
    ListNode* next = phead->next;
    ListNode* newnode = BuyListNode(x);
    phead->next = newnode;//(1)
    newnode->prev = phead;//(2)

    next->prev = newnode;//(3)
    newnode->next = next;//(4)
}

7、双向链表的头删

图示：

代码：

void ListPopFront(ListNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    ListNode* nextNext = phead->next->next;
    free(phead->next);
    phead->next = nextNext;//(1)
    nextNext->prev = phead;//(2)
}

8、双向链表的打印

代码：

void ListPrint(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)//当cur = phead的时候说明已经遍历完一遍了
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

9、双向链表元素的查找

代码：

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

注意：为什么要在最开始将cur置为phead->next？

1. 因为phead作为哨兵位中存储的不是有效数据，所以不能从这个开始查找。
2. 同时phead作为查找的终止条件，不能从这个元素开始，如果从这个元素开始遍历查找的话在一开始查找就停止了。

10、双向链表特定元素的删除

图示：

代码：

void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* next = pos->next;
    ListNode* prev = pos->prev;
    free(pos);
    pos = NULL;//此处可以置空也可以不置空，因为pos只是函数中的局部变量
    prev->next = next;//(1)
    next->prev = prev;//(2)
}

驼峰法命名规则：

1. 函数名和类型名所有单词首字母大写
2. 变量：第一个单词小写，后续单词首字母大写

11、双向链表特定元素的前插

图示：

代码：

void ListInsertBefore(ListNode* phead, ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* newnode = BuyListNode(x);
    ListNode* prev = pos->prev;
    prev->next = newnode;//(1)
    newnode->prev = prev;//(2)
    pos->prev = newnode;//(3)
    newnode->next = pos;//(4)
}

12、双向链表的销毁

图示：

代码：

第一种：传二级指针的，此时会将哨兵位的空间进行释放。

void ListDestory(ListNode** phead)
{
    assert(phead);
    ListNode* cur = (*phead)->next;
    while (cur!=(*phead))//结束条件就是不等于头节点
    {
        ListNode* next = cur->next;//存储当前释放节点的下一个节点的地址
        free(cur);//释放当前节点
        cur = next;//将节点向后推移
    }
    free(*phead);//释放哨兵位节点
    *phead = NULL;//防止内存泄漏
}

第二种：不传二级指针的，此时不将哨兵位的空间进行释放。

void ListDestory(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = cur->next;
    }
    cur = NULL;
}