数据结构——双链表C语言

目录

编辑

 双链表的初始化：

 双链表的打印：

双链表的尾插：

双链表的头插： 

双链表的尾删：

双链表的头删：

双链表pos位置之前的插入：

双链表pos位置的删除：

关于顺序表和链表的区别：

1. 上篇文章给大家讲解了无头单向循环链表，它的特点：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构子结构，如哈希桶、图的邻接表等等。但是呢，单链表在笔试中还是很常见的。
2. 今天我给大家讲解一下带头双向链表，它的特点：结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然复杂，但是使用代码实现以后会发现结构会带来很多优势。

如图，这就是今天我为大家讲解的双链表结构了。下面跟随我的思路走下去，希望让你对链表有新的理解。

 双链表的初始化：

• 今天我给大家带来另一种方式改变链表的结构，如果想了解双指针来改变链表的结构，可以参考参考我的上一篇单链表的博客。
• 思路：我创建了一个节点，然后把节点赋给了phead，再让它的上一个位置和下一个位置分别指向它自己，最后返回phead就是我们要的哨兵位的头节点了。

1.  
   ListNode* ListCreate(ListDateType x)
2.  
   {
3.  
   ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
4.  
   if (newnode == NULL)
5.  
   {
6.  
   perror("malloc fail");
7.  
   exit(-1);
8.  
   }
9.  
    
10.  
    newnode->val = x;
11.  
    newnode->next = NULL;
12.  
    newnode->prev = NULL;
13.  
     
14.  
    return newnode;
15.  
    }

1.  
   ListNode* ListInit()
2.  
   {
3.  
   ListNode* phead = ListCreate(0);
4.  
   phead->next = phead;
5.  
   phead->prev = phead;
6.  
    
7.  
   return phead;
8.  
   }

 双链表的打印：

• 因为要让终端出现下面的样子，我就用到了打印的函数。
• 首先，还是老套路，我先断言了一下，防止传的参数有问题。
• 因为这里的phead是一个哨兵位，存放着无效的数据，所以，我就定义了一个cur的节点，用循环打印链表中的所有值，并标明他们的方向。

1.  
   void ListPrint(ListNode* phead)
2.  
   {
3.  
   assert(phead);
4.  
    
5.  
   printf("phead<->");
6.  
   ListNode* cur = phead->next;
7.  
   while (cur != phead)
8.  
   {
9.  
   printf("%d<->", cur->val);
10.  
    cur = cur->next;
11.  
    }
12.  
    printf("\n");
13.  
    }

双链表的尾插：

• 在双链表尾插的时候，它的优势就体现出来了，如果是单链表，要尾插的话，是只有遍历找尾节点的，但是呢，如果是双向链表，phead的前一个节点就是尾节点，它就不用找尾，也不需要遍历了。这也是双链表的优势之一。
• 尾插思路：先断言一下，然后用tail保存尾节点，创建一个新节点，然后改变尾节点和头节点链接关系，让newnode为新的尾节点。

1.  
   void ListPushBack(ListNode* phead,ListDateType x)
2.  
   {
3.  
   assert(phead);
4.  
   ListNode* tail = phead->prev;
5.  
   ListNode* newnode = ListCreate(x);
6.  
    
7.  
   tail->next = newnode;
8.  
   newnode->prev = tail;
9.  
    
10.  
    newnode->next = phead;
11.  
    phead->prev = newnode;
12.  
     
13.  
     
14.  
    }

双链表的头插： 

• 思路：头插的话，就是先保存一下头节点的位置，然后创建一个新节点，然后改变他们的链接关系就可以了。因为我是先保存了它们的位置，所以谁先链接先都可以，如果没有保存的话，要向好逻辑，不要出现找不到头节点的位置了。

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

双链表的尾删：

• 思路：尾删的话，就要记录一下尾节点的前一个节点了，然后去改变一下phead和尾节点前一个节点的链接关系。

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

双链表的头删：

• 思路：头删的思路，其实和尾删的思路差不多，只不过这里保存的是phead之后的第二个节点了。然后就是改变链接关系。

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

双链表pos位置之前的插入：

• 思路：如果是插入的话，是不是和尾插和头插差不多呢，我在这里是保存的pos之前的节点，然后创建一个新的节点，让pos之前的节点指向新节点，让新节点和pos再建立连接关系。

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

双链表pos位置的删除：

• 思路：pos位置要删除的话，保存pos上一个节点和pos下一个节点，然后free掉pos位置，再改变他们的链接关系。

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

大家看了pos位置的删除和pos之前的插入，是不是感觉和前面的尾插尾删和头插头删差不多呢，其实呢，最后的两个函数是可以进行对函数的复用的。

•  尾插：其实就是在ListInsert函数传phead就可以了，这样就实现了尾插。

	ListInsert(phead, x);

• 头插：头插是改变phead之后的位置，所以直接传phead->next就可以了。

	ListInsert(phead->next, x);

• 头删和尾删：因为我写的删除的函数是删除pos位置，所以传要删除的位置就可以了。

	ListErase(phead->prev);

	ListErase(phead->next);

关于顺序表和链表的区别：

•  存储空间上：顺序表在物理上是连续的，而链表逻辑上是连续的，而物理上是不一定连续的。
• 随机访问上：顺序表是支持随机访问的，而链表是不支持的，向要访问链表中的节点，是需要遍历的。
• 任意位置的插入和删除：在这里链表就有很大的优势了，链表只需要改变指向就可以实现对任意位置的插入和删除。但是对于顺序表，它可能需要搬运元素，效率太低了。
• 插入：顺序表因为是连续的，所以在插入的上面，可能会有malloc扩容，但是呢malloc是有消耗的，如果一次扩二倍，但是用的不多，就会造成对空间的浪费，如果一次扩的空间是 1，可能局面临着多次扩容，而malloc的消耗并不低，所以这是不可取的。而链表并没有容器的概念，在这方面有优势。
• 缓存利用率：顺序表的缓存命中率高，而链表低。

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

什么是缓存利用率：

关于“Cache Line” ，缓存是把数据加载到离自己进的位置，对于CPU来说，CPU是一块一块存储的。而这就叫“Chche Line”。

我们所写的程序，其实都是会形成不同的指令，然后让CPU执行，但是呢，CPU执行速度快，内存跟不上，所以CPU一般都是把数据放到缓存中，对于小的字节来说，直接由寄存器来读取，大的字节会用到三级缓存。

简而言之，数据先被读取，然后运算，最后放到主存中，如果没有命令，就继续。

而顺序表呢，它的物理结构是连续的，它可能一开始没有命中，但是一旦缓存命中了，它可能就会被连续命中，所以这也是顺序表缓存利用率高的原因，而链表也是因为他的物理结构，导致缓存利用率低。

下面是双链表的源码：

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

1.  
   #pragma once
2.  
   #include <stdio.h>
3.  
   #include <assert.h>
4.  
   #include <stdlib.h>
5.  
    
6.  
   typedef int ListDateType;
7.  
    
8.  
   typedef struct ListNode
9.  
   {
10.  
    ListDateType val;
11.  
    struct ListNode* next;
12.  
    struct ListNode* prev;
13.  
    }ListNode;
14.  
     
15.  
    ListNode* ListCreate(ListDateType x);
16.  
    void ListPrint(ListNode* phead);
17.  
    ListNode* ListInit();
18.  
    void ListPushBack(ListNode* phead,ListDateType x);
19.  
    void ListPushFront(ListNode* phead, ListDateType x);
20.  
    void ListPopBack(ListNode* phead);
21.  
    void ListPopFront(ListNode* phead);
22.  
    int ListSize(ListNode* phead);
23.  
    void ListInsert(ListNode* pos, ListDateType x);
24.  
    void ListErase(ListNode* pos);

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