[数据结构与算法]《数据结构》线性表之双链表（C语言）

?目录

💨回顾单链表

💨双链表

💨双链表结构体的定义

💨接口函数的实现

🎈开辟节点函数

🎈初始化链表

🎈打印链表

🎈查找

🎈在某位置前插入数据

重点注意

🎈删除某位置的值

🎈尾插

🎈头插

🎈尾删

🎈头删

🌹单链表可以看这篇博客：《数据结构》线性表之单链表（C语言）_Perfectkn的博客-CSDN博客

本篇博客只讲：带头双向循环链表

💨回顾单链表

之前在博客中讲过单链表，但单链表的缺陷很明显。它无法找到前驱（即前一个节点）。

单链表结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,
如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

💨双链表

带头双向循环链表:结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

有了单链表的讲述，我们就直接进行双链表的结构体定义和一些接口实现。

💨双链表结构体的定义

typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prve;
    LTDataType  data;
}ListNode;

1. 把int重命名为LTDataType （为了增强代码可维护性）
2. 结构体的成员变量里，我定义了两个结构体指针，next和prve，双链表有两个指针域一个数据域，next指针指向下一个节点，prve指针指向前一个节点，data就是当前节点的数据域，存的数据类型就是LTDataType（int）。
3. 把结构体变量重命名为ListNode，不然每次使用都要带上struct。

💨接口函数的实现

🎈开辟节点函数

ListNode* BuyListNode(LTDataType x)
{
    ListNode * newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

我们无论是初始化链表，还是头插尾插时，一定会使用到新开辟一个节点，所以单门拿出来写成一个函数。

带返回值的目的是为了初始化链表的时候，避免使用二级指针，因为带头节点的链表我们就是可以避免使用二级指针的现象。

🎈初始化链表

ListNode* ListInit() //初始化
{
    ListNode* phead = BuyListNode(0);
    phead->next = phead;
    phead->prve = phead;

    return phead;
}

同样，为了避免使用二级指针，加入了返回值，当初始化完成时，直接把头节点指针返回给主函数，这样，一个带有头节点的双向循环链表就初始化完成了。

主函数接收如下

ListNode * plist = ListInit();

• ?初始化的时候，那个BuyListNode()括号里的任填，只要是L只是为了头插尾插而准备，一般不会用到头节点的数据域。只要数据类型是LTDataType（int）就行。
• 初始化的时候，头节点的指针域肯定都指向自己。

🎈打印链表

void ListPrint(ListNode* phead) //打印
{
    ListNode * cur = phead->next;
    while (cur != phead)
    {
        printf("%d ",cur->data);
        cur = cur->next;
    }
    printf("\n");
}

定义一个结构体指针cur，从头节点的下一个节点开始打印，直到cur再次指向头节点结束。

🎈查找

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;
}

1. 查找时把链表和你要查找的内容传过来。
2. assert判断你传的链表是否为空
3. 建一个结构体指针cur从头节点phead的下一个节点开始找，一直再次到头节点为止。
4. 如果中途找到返回指针，没找到等循环结束返回空指针

?主函数接收如下

ListNode * pos = ListFind(plist,3);

?因为我写的时候，初始化链表时，主函数用ListNode* plist接收，插入了一个3。

🎈在某位置前插入数据

//pos位置之前插入x
void ListInsert(ListNode* pos , LTDataType x)
{
    assert(pos);
    ListNode * prve = pos->prve;
    ListNode * newnode = BuyListNode(x);

    prve->next = newnode;
    newnode->prve = prve;
    newnode->next = pos;
    pos->prve = newnode;
}

1. 先判断链表是否为空
2. 先创建一个结构体指针prve指向当前位置的前一个节点（一定要先查找再用此函数，不然程序怎么知道你在哪个位置前插入）
3. 创建一个newnode指针作为你要插入的新节点
4. prve的next指针域指向newnode
5. newnode的prve指针域指向prve（注意prve指针域是结构体的成员变量，指向的prve是我定义的结构体指针，别弄混了）
6. newnode的next指针域指向pos
7. pos的prve指针域指向newnode

重点注意

🌹这种先创建一个结构体指针指向pos位置前一个节点的方法，好处是为了避免你写指针时需要注意顺序问题，有了指针，你就不用担心顺序写的对不对。

🎈删除某位置的值

//删除pos位置的值
void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode * prve = pos->prve;
    ListNode * next = pos->next;
    prve->next = next;
    next->prve = prve;
    free(pos);

1. 定义一个结构体指针prve指向当前位置的前一个节点
2. 定义一个结构体指针next指向当前位置的后一个节点
3. 前一个节点的next域指向后一个节点
4. 后一个节点的prve域指向前一个节点
5. 再释放掉此节点

🎈尾插

void ListPushBack(ListNode* phead , LTDataType x) //尾插
{
    assert(phead);
    ListNode * tail = phead->prve;
    ListNode * newnode = BuyListNode(x);

    tail->next = newnode;
    newnode->prve = tail;
    newnode ->next = phead;
    phead->prve = newnode;

   // ListInsert(phead,x);
}

1. assert判断链表是否为空
2. 新开一个tail指针指向头节点的前一个（原因开上面的重点注意）
3. 建一个newnode就代表你要插入的节点
4. 接下来就是更换本来的尾节点和next域指向和头节点prve域的指向就行
5. 然后newnode新节点的指向也要定义

上面我们写了在某个位置前插入的函数，可以直接调用他 ListInsert(phead,x)

🎈头插

void ListPushFront(ListNode* phead , LTDataType x) //头插
{
    assert(phead);
    ListNode * first = phead->next;
    ListNode * newnode = BuyListNode(x);

    phead->next = newnode;
    newnode->prve = phead;
    newnode->next = first;
    first->prve = newnode;

//    ListInsert(phead->next,x);


/*
  另一种写法需要注意顺序
   ListNode * newnode = BuyListNode(x);
    newnode->next = phead->next;
    phead->next->prve = newnode;
    phead->next = newnode;
    newnode->prve = phead;
 */

}

• 同样也可以直接调用上面的那个函数，具体实现和尾插差不多，只要更改指针域的指向即可
• 下面我又写了另一种写法，这种写法就是不创建指针，但要注意顺序。

🎈尾删

void ListPopBack(ListNode* phead) //尾删
{
    assert(phead);
    assert(phead->next != phead);
    ListNode * tail = phead->prve;
    ListNode * prev = tail->prve;
    prev->next = phead;
    phead->prve = prev;

    free(tail);
    tail = NULL;

    //ListErase(phead->prev);
}

?尾删，头删也可以调用之前我们写的删除某个位置的函数。

🎈头删

void ListPopFront(ListNode* phead) //头删
{
    assert(phead);
    assert(phead->next != phead);
    ListNode * first = phead->next;
    ListNode * second = phead->next->next;
    phead->next = second;
    second->prve = phead;

    free(first);
    first = NULL;


    //ListErase(phead->next);
}