数据结构入门指南带头双向循环链表

前言

        链表一共有8种结构，但最常用的就是无头单向链表、和带头双向循环链表。单链表的结构存在着很多的缺陷，但它是许多数据结构的子结构，在刷题中经常见到，而带头双向循环链表弥补了单链表所有的缺陷，可以说是一个完美结构，虽然相对于单链表来说结构更复杂，但它的特性使它的实现逻辑较为简单，今天我就向大家一个一个地介绍。

---

1.结构与优势

结构：

优势：

1. 可以实现快速的插入和删除操作：由于链表的特性，插入和删除节点的时间复杂度为O(1)，不需要像数组一样需要移动其他元素。
2. 可以实现快速的遍历操作：双向链表可以通过前向或后向的指针进行遍历，而不需要像单向链表那样只能从头节点开始遍历。
3. 可以实现双向遍历：双向链表可以通过前向和后向的指针进行双向遍历，可以方便地从任意一个节点开始向前或向后遍历。
4. 可以实现循环遍历：由于链表的循环性质，可以通过不断移动指针进行循环遍历，不需要额外的循环条件判断。
5. 可以实现更多高级功能：带头双向循环链表可以实现更多高级功能，如反转链表、查找倒数第k个节点等。

总结，带头双向循环链表具有灵活性和高效性，适用于需要频繁插入、删除和遍历操作的场景。

2.链表实现      

 2.1 定义链表

        步入正题，带头双向循环链表，首先它是双向的，什么是双向呢？在单链表定义时会有指向下一个节点的指针，而双向链表有两个指针，一个指向下一个节点，一个指向上一个节点，可以实现前后双向遍历。

1.  
   typedef struct ListNode
2.  
   {
3.  
   int data;
4.  
   struct ListNode* next;//指向下一个节点的指针
5.  
   struct ListNode* prev;//指向上一个节点的指针
6.  
   }LN;

 2.2 创建头节点

         和无头单向链表不同，带头双向循环链表它有头节点，所以在开始执行各操作之前，我们先创建一个头节点并初始化。

        创建头节点需要新建一个节点，在其他插入接口中也需要新建节点，那我们就封装一个创建新节点的函数，最后返回新建节点的地址。

1.  
   LN* BuyListNode(Datatype x)
2.  
   {
3.  
   LN* newnode = (LN*)malloc(sizeof(LN));
4.  
   if (newnode == NULL)
5.  
   {
6.  
   perror("malloc");
7.  
   exit(-1);
8.  
   }
9.  
   newnode->data = x;
10.  
    newnode->next = NULL;
11.  
    newnode->prev = NULL;
12.  
    return newnode;
13.  
    }

         和无头单链表不同，这里带有头节点，就需要对头节点进行初始化一下，虽然在创建节点时就已经对节点进行了初始化，但头节点的初始化与新建节点初始化需求不同，所有这里需要单独进行初始化初始化节点时可以使用双指针，也可以直接返回头节点地址。

1.  
   LN* InItNode()
2.  
   {
3.  
   LN* phead = BuyListNode(-1);
4.  
   phead->next = phead;
5.  
   phead->prev = phead;
6.  
   return phead;
7.  
   }

         头节点进行初始化时，只需将两个指针指向自己，然后返回头节点的地址即可。

 2.3 尾插

        建好头节点后要怎么链接节点呢？我们先写一个尾插来体验一下它的便捷。在单链表中想要进行尾插，还需要遍历一遍链表找到尾节点，而带头双向循环链表就不需要，可以通过头节点直接找到尾节点：tail  =  phead -> prev ;头节点的前一个节点就是尾节点。

我们新建一个节点：

         要想插入就需要把尾节点的next改为新节点的地址，新节点的prev改为尾节点tail的地址

        再把新节点的next改为头节点的地址，把头节点的prev改位新节点的地址。

 

 整体逻辑就是这样，具体代码如下：

1.  
   void PushBack(LN* phead, Datatype x)
2.  
   {
3.  
   assert(phead);
4.  
   LN* tail = phead->prev;
5.  
   LN* newnode = BuyListNode(x);
6.  
    
7.  
   tail->next = newnode;
8.  
   newnode->prev = tail;
9.  
   newnode->next = phead;
10.  
    phead->prev = newnode;
11.  
    }

2.4 输出链表

        为了便于后续的测试，我们先写一个函数用于输出链表数据。输出函数很简单。

1.  
   void PrintList(LN* phead)
2.  
   {
3.  
   assert(phead);
4.  
   LN* cur = phead->next;//有效节点不包含头节点
5.  
   printf("phead <->");
6.  
   while (cur != phead)
7.  
   {
8.  
   printf(" %d <->", cur->data);
9.  
   cur = cur->next;
10.  
    }
11.  
    }

         这里需要注意的是遍历链表时的循环条件，由于它是循环链表，所有结束条件有所变化。其次是输出数据时不需要输出头节点的数据，头节点的下一个节点才是有效数据。

我们可以来测试一下：

1.  
   void test1()
2.  
   {
3.  
   LN* plist = InItNode();
4.  
   PushBack(plist, 1);
5.  
   PushBack(plist, 2);
6.  
   PushBack(plist, 3);
7.  
   PushBack(plist, 4);
8.  
   PushBack(plist, 5);
9.  
   PrintList(plist);
10.  
    }
11.  
     
12.  
    int main()
13.  
    {
14.  
    test1();
15.  
    return 0;
16.  
    }

 输出效果如下：

 2.5 尾删

        基本逻辑理解后，可以先自主尝试写一下尾删。思路也是非常的简单，但要注意的是，有效节点为0的情况。把尾节点的前一个节点next改为头节点地址，头节点的prev改为尾节点的前一个节点，最后释放掉尾节点的空间。

1.  
   void PopBack(LN* phead)
2.  
   {
3.  
   assert(phead);
4.  
   assert(phead->next != phead);
5.  
   LN* tail = phead->prev;
6.  
   LN* tailprev = tail->prev;
7.  
    
8.  
   tailprev->next = phead;
9.  
   phead->prev = tailprev;
10.  
    free(tail);
11.  
    }

2.6 头插

        接下来我们进行头插操作，我们使用的是带头的形式，所有这里进行头插时，不像单链表那样需要使用二级指针，我们需要改的是头节点中的内容，所有使用一级指针就可以解决。

         此外头插时一定要注意操作的次序，避免后续操作有误。例如：

        如果不提前保存第一个节点的地址， 就会导致新节点链接后续节点时找节点麻烦或出现错误。

 正确的顺序如下图：

 代码实现：

1.  
   void PushFront(LN* phead,Datatype x)
2.  
   {
3.  
   assert(phead);
4.  
   LN* newnode = BuyListNode(x);
5.  
   newnode->next = phead->next;
6.  
   phead->next->prev = newnode;
7.  
    
8.  
   newnode->prev = phead;
9.  
   phead->next = newnode;
10.  
     
11.  
    }

         当然新手不建议这样写，这样写很容易把人搞晕，我们可以先保存第一个节点的地址，这样就不会搞错。代码如下：

1.  
   void PushFront(LN* phead,Datatype x)
2.  
   {
3.  
   assert(phead);
4.  
   LN* newnode = BuyListNode(x);
5.  
   LN* first = phead->next;
6.  
    
7.  
   phead->next = newnode;
8.  
   newnode->prev = phead;
9.  
    
10.  
    newnode->next = first;
11.  
    first->prev = newnode;
12.  
     
13.  
    }

2.7头删

        这里头删也是非常简单，为了避免出错，我们可以额外创建两个指针，记录第一个节点和第二个节点，逻辑较为简单，就不再画逻辑图，代码如下：

1.  
   void PopFront(LN* phead)
2.  
   {
3.  
   assert(phead);
4.  
   assert(phead->next != phead);
5.  
    
6.  
   LN* first = phead->next;
7.  
   LN* second = first->next;
8.  
    
9.  
   free(first);
10.  
     
11.  
    phead->next = second;
12.  
    second->prev = phead;
13.  
     
14.  
    }

需要额外注意链表为空的情况。

2.8 节点个数

        统计节点个数很简单，和输出链表数据一样遍历一下链表统计链表个数代码如下：

1.  
   int Listsize(LN* phead)
2.  
   {
3.  
   assert(phead);
4.  
   int sz = 0;
5.  
   LN* cur = phead->next;
6.  
   while (cur != phead)
7.  
   {
8.  
   sz ;
9.  
   cur = cur->next;
10.  
    }
11.  
    return sz;
12.  
    }

         有人可能会想：用头节点统计不也可以吗？还不用额外的去写一个函数。初始时把头节点的data初始化为0，每次插入data 。这种方式严格来说是不可以的，我们在写链表时每个节点不一定存储的是整形，也可能是字符型，虽然也能计数，但如果节点是1000呢？数据就溢出了，所以不建议那样写。

 2.9 查找

        查找也比较简单，不再多说，代码如下：

1.  
   LN* ListFind(LN* phead, Datatype x)
2.  
   {
3.  
   assert(phead);
4.  
   LN* cur = phead->next;
5.  
   while (cur!=phead)
6.  
   {
7.  
   if (cur->data == x)
8.  
   return cur;
9.  
   cur = cur->next;
10.  
    }
11.  
    return NULL;
12.  
    }

 2.10 位置插入

         带头双向循环链表在位置插入时没有像单链表那样有位置前插入，位置后插入。这里的位置插入都是位置前插入，由于它是循环双向的链表，不像单链表那样不可以向前遍历，双向循环链表可以任意插入，所以位置后插入也并没有什么意义，就统一默认位置前插入。

        位置插入操作和上述的插入操作很类似，推荐额外创建一个指针保存节点信息，就可以避免操作时次序不当造成程序错误，代码如下：

1.  
   void ListInsert(LN* pos, Datatype x)
2.  
   {
3.  
   assert(pos);
4.  
   LN* newnode = BuyListNode(x);
5.  
   LN* posprev = pos->prev;
6.  
    
7.  
   posprev->next = newnode;
8.  
   newnode->prev = posprev;
9.  
    
10.  
    newnode->next = pos;
11.  
    pos->prev = newnode;
12.  
     
13.  
    }

2.11 位置删除

        位置删除也一样很简单，我们多创建两个指针变量存储节点信息，就可以有效避免次序不当导致程序错误的问题。代码如下：

1.  
   void PosErase(LN* pos)
2.  
   {
3.  
   assert(pos);
4.  
   LN* posprev = pos->prev;
5.  
   LN* posnext = pos->next;
6.  
    
7.  
   free(pos);
8.  
    
9.  
   posprev->next = posnext;
10.  
    posnext->prev = posprev;
11.  
    }

 2.12 销毁链表

        在链表使用完以后就要销毁，销毁也比较简单，代码如下：

1.  
   void DestoryList(LN* phead)
2.  
   {
3.  
   assert(phead);
4.  
   LN* cur = phead->next;
5.  
   while (cur != phead)
6.  
   {
7.  
   LN* next = cur->next;
8.  
   free(cur);
9.  
   cur = next;
10.  
    }
11.  
    free(phead);
12.  
    }

         这样还需要注意的一点，在销毁链表的这个函数里虽然销毁了头节点，但是在头节点创建之初使用了结构体指针，在后续操作中都是通过这个指针将链表传递给函数，所以最后在调用销毁链表函数之后要将指向头节点的指针置为NULL，避免出现野指针。当然这里也可以使用二级指针在函数里将这个指针置为NULL。

 3. 源码

List.c

1.  
   #include"List.h"
2.  
   LN* BuyListNode(Datatype x)
3.  
   {
4.  
   LN* newnode = (LN*)malloc(sizeof(LN));
5.  
   if (newnode == NULL)
6.  
   {
7.  
   perror("malloc");
8.  
   exit(-1);
9.  
   }
10.  
    newnode->data = x;
11.  
    newnode->next = NULL;
12.  
    newnode->prev = NULL;
13.  
    return newnode;
14.  
    }
15.  
    LN* InItNode()
16.  
    {
17.  
    LN* phead = BuyListNode(-1);
18.  
    phead->next = phead;
19.  
    phead->prev = phead;
20.  
    return phead;
21.  
    }
22.  
    void PrintList(LN* phead)
23.  
    {
24.  
    assert(phead);
25.  
    LN* cur = phead->next;
26.  
    printf("phead <->");
27.  
    while (cur != phead)
28.  
    {
29.  
    printf(" %d <->", cur->data);
30.  
    cur = cur->next;
31.  
    }
32.  
    printf("\n");
33.  
    }
34.  
    void PushBack(LN* phead, Datatype x)
35.  
    {
36.  
    assert(phead);
37.  
    LN* tail = phead->prev;
38.  
    LN* newnode = BuyListNode(x);
39.  
     
40.  
    tail->next = newnode;
41.  
    newnode->prev = tail;
42.  
    newnode->next = phead;
43.  
    phead->prev = newnode;
44.  
    }
45.  
    void PopBack(LN* phead)
46.  
    {
47.  
    assert(phead);
48.  
    assert(phead->next != phead);
49.  
    LN* tail = phead->prev;
50.  
    LN* tailprev = tail->prev;
51.  
     
52.  
    tailprev->next = phead;
53.  
    phead->prev = tailprev;
54.  
    free(tail);
55.  
    }
56.  
    void PushFront(LN* phead,Datatype x)
57.  
    {
58.  
    assert(phead);
59.  
    /*LN* newnode = BuyListNode(x);
60.  
    newnode->next = phead->next;
61.  
    phead->next->prev = newnode;
62.  
     
63.  
    newnode->prev = phead;
64.  
    phead->next = newnode;*/
65.  
    LN* newnode = BuyListNode(x);
66.  
    LN* first = phead->next;
67.  
    phead->next = newnode;
68.  
    newnode->prev = phead;
69.  
     
70.  
    newnode->next = first;
71.  
    first->prev = newnode;
72.  
     
73.  
    }
74.  
    void PopFront(LN* phead)
75.  
    {
76.  
    assert(phead);
77.  
    assert(phead->next != phead);
78.  
     
79.  
    LN* first = phead->next;
80.  
    LN* second = first->next;
81.  
     
82.  
    free(first);
83.  
     
84.  
    phead->next = second;
85.  
    second->prev = phead;
86.  
     
87.  
    }
88.  
    int Listsize(LN* phead)
89.  
    {
90.  
    assert(phead);
91.  
    int sz = 0;
92.  
    LN* cur = phead->next;
93.  
    while (cur != phead)
94.  
    {
95.  
    sz ;
96.  
    cur = cur->next;
97.  
    }
98.  
    return sz;
99.  
    }
100.  
     LN* ListFind(LN* phead, Datatype x)
101.  
     {
102.  
     assert(phead);
103.  
     LN* cur = phead->next;
104.  
     while (cur!=phead)
105.  
     {
106.  
     if (cur->data == x)
107.  
     return cur;
108.  
     cur = cur->next;
109.  
     }
110.  
     return NULL;
111.  
     }
112.  
     void ListInsert(LN* pos, Datatype x)
113.  
     {
114.  
     assert(pos);
115.  
     LN* newnode = BuyListNode(x);
116.  
     LN* posprev = pos->prev;
117.  
      
118.  
     newnode->next = pos;
119.  
     pos->prev = newnode;
120.  
      
121.  
     newnode->prev = posprev;
122.  
     posprev->next = newnode;
123.  
     }
124.  
     void PosErase(LN* pos)
125.  
     {
126.  
     assert(pos);
127.  
     LN* posprev = pos->prev;
128.  
     LN* posnext = pos->next;
129.  
      
130.  
     free(pos);
131.  
      
132.  
     posprev->next = posnext;
133.  
     posnext->prev = posprev;
134.  
     }
135.  
     void DestoryList(LN* phead)
136.  
     {
137.  
     assert(phead);
138.  
     LN* cur = phead->next;
139.  
     while (cur != phead)
140.  
     {
141.  
     LN* next = cur->next;
142.  
     free(cur);
143.  
     cur = next;
144.  
     }
145.  
     free(phead);
146.  
     }

 List.h

1.  
   #include<stdio.h>
2.  
   #include<stdlib.h>
3.  
   #include<assert.h>
4.  
    
5.  
   typedef int Datatype;
6.  
   typedef struct ListNode
7.  
   {
8.  
   int data;
9.  
   struct ListNode* next;
10.  
    struct ListNode* prev;
11.  
    }LN;
12.  
     
13.  
    LN* BuyListNode(Datatype x);
14.  
    LN* InItNode();
15.  
    void PrintList(LN* phead);
16.  
    void PushBack(LN* phead,Datatype x);
17.  
    void PopBack(LN* phead);
18.  
    void PushFront(LN* phead, Datatype x);
19.  
    void PopFront(LN* phead);
20.  
    LN* ListFind(LN* phead, Datatype x);
21.  
    int Listsize(LN* phead);
22.  
    void ListInsert(LN* pos, Datatype x);
23.  
    void PosErase(LN* pos);
24.  
    void DestoryList(LN* phead);

 test.c

1.  
   #include"List.h"
2.  
   void test1()
3.  
   {
4.  
   LN* plist = InItNode();
5.  
   PushBack(plist, 1);
6.  
   PushBack(plist, 2);
7.  
   PushBack(plist, 3);
8.  
   PushBack(plist, 4);
9.  
   PushBack(plist, 5);
10.  
    PushFront(plist, 0);
11.  
    PopBack(plist);
12.  
    ListInsert(plist, 10);
13.  
    LN* pos = ListFind(plist, 10);
14.  
     
15.  
    ListInsert(pos, 11);
16.  
     
17.  
    PosErase(pos);
18.  
    PrintList(plist);
19.  
    DestoryList(plist);
20.  
    plist = NULL;
21.  
    }
22.  
    void test2()
23.  
    {
24.  
    LN* plist = InItNode();
25.  
    PushBack(plist, 1);
26.  
    PushBack(plist, 2);
27.  
    PushBack(plist, 3);
28.  
    PushBack(plist, 4);
29.  
    PushBack(plist, 5);
30.  
    //PushFront(plist, 0);
31.  
     
32.  
    PopFront(plist);
33.  
    PrintList(plist);
34.  
    }
35.  
     
36.  
    int main()
37.  
    {
38.  
    test1();
39.  
    return 0;
40.  
    }

---

总结

        带头双向循环链表作为一种数据结构，在解决问题时展现了其独特的优势。通过快速的插入和删除操作，以及灵活的双向遍历和循环遍历能力，它为我们提供了一种高效、灵活的数据组织方式。在实际应用中，我们可以充分发挥带头双向循环链表的特性，优化算法设计，提高程序的效率和可维护性。通过深入学习和掌握带头双向循环链表，我们可以更好地解决实际问题，提升自己的编程能力。希望本文能够帮助读者对带头双向循环链表有更深入的理解，并在实践中得到应用。最后，感谢阅读！

这篇好文章是转载于：学新通技术网