• 学习笔记---更进一步的双向链表专题~~



    目录

    1. 双向链表的结构🦊

    2. 实现双向链表🐝

    2.1 要实现的目标🎯

    2.2 创建+初始化🦋

    2.2.1 List.h

    2.2.2 List.c

    2.2.3 test.c

    2.2.4 代码测试运行

    2.3 尾插+打印+头插🪼

    思路分析

    2.3.1 List.h

    2.3.2 List.c

    2.3.3 test.c

    2.3.4 代码测试运行

    2.4 尾删+头删🐊

    2.4.0 思路分析

    2.4.1 List.h

    2.4.2 List.c

    2.4.3 test.c

    2.4.4 代码测试运行

    2.5 查找数据+pos节点后插入+删除pos节点🦩

    2.5.0 思路分析

    2.5.1 List.h

    2.5.2 List.c

    2.5.3 test.c

    2.5.4 代码测试运行

    2.6 销毁☄️

    2.6.0思路分析

    1. 一级指针

    2.6.1 List.h

    2.6.2 List.c

    2.6.3 test.c

    2.6.4 代码测试运行

    2. 二级指针

    2.6.1 List.h

    2.6.2 List.c

    2.6.3 test.c

    2.6.4 代码测试运行

    2.7 完整代码💦

    2.7.1 List.h

    2.7.2 List.c

    2.7.3 test.c

    3. 顺序表和双向链表的分析🍻


    1. 双向链表的结构🦊


    这里的双向链表,准确的说是:带头双向循环链表

    这里的“头节点”指的是“哨兵位”哨兵位节点不存储任何有效元素,只是站在这⾥“放哨

    的”。

    “哨兵位”存在的意义:遍历循环链表避免死循环

    注意⚠️

    双向链表的每一个节点存储一个有效数据+下一个节点的地址+上一个节点的地址

    头节点和尾节点有些特殊:头节点指向的上一个节点的地址是尾节点,尾节点指向的下一个节点的地址是头节点


    2. 实现双向链表🐝

    2.1 要实现的目标🎯

    我们需要多个接口帮助我们实现:创建、一系列具体操作、销毁

    具体操作包括:头部/尾部插入数据、头部/尾部删除数据、打印出双向链表、指定节点之后插入数据、删除指定节点的数据、查找指定节点

    2.2 创建+初始化🦋

    2.2.1 List.h

    1. #include
    2. #include
    3. #include
    4. typedef int LTDataType;
    5. //创建双向链表的结构体
    6. typedef struct ListNode {
    7. LTDataType data;
    8. struct ListNode* prev;
    9. struct ListNode* next;
    10. }ListNode;
    11. //初始化
    12. ListNode* LTInit();//不用传入参数,直接调用接口返回一个头节点

    2.2.2 List.c

    1. #include"List.h"
    2. //初始化
    3. ListNode* LTInit()//不用传入参数,直接调用接口返回一个头节点
    4. {
    5. //为头节点申请空间
    6. ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    7. //判断开辟是否成功
    8. if (phead == NULL)
    9. {
    10. perror("malloc error!\n");
    11. return;
    12. }
    13. //开辟成功--->初始化头节点
    14. phead->data = -1;//头节点不存储有效数据,可以任意赋值
    15. //只有哨兵位的时候,要实现双向链表,不能指向NULL,否则无法双向循环,所以我们指向自己
    16. phead->prev = phead->next = phead;
    17. return phead;
    18. }

    2.2.3 test.c

    1. #include"List.h"
    2. void ListTest()
    3. {
    4. ListNode* plist = LTInit();
    5. }
    6. int main()
    7. {
    8. ListTest();
    9. return 0;
    10. }

    2.2.4 代码测试运行


    2.3 尾插+打印+头插🪼

    思路分析




    2.3.1 List.h

    1. //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
    2. //尾插
    3. void LTPushBack(ListNode* phead, LTDataType x);
    4. //打印
    5. void LTPrint(ListNode* phead);
    6. //头插
    7. void LTPushFront(ListNode* phead, LTDataType x);

    2.3.2 List.c

    1. //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
    2. // 只改变数据,不改变地址
    3. //开辟空间
    4. ListNode* ListBuyNode(LTDataType x)
    5. {
    6. ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    7. if (node == NULL)
    8. {
    9. perror("malloc error!\n");
    10. return;
    11. }
    12. node->data = x;
    13. node->next = node->prev = NULL;
    14. return node;
    15. }
    16. //尾插
    17. void LTPushBack(ListNode* phead, LTDataType x)
    18. {
    19. assert(phead);//注意哨兵位不能为空
    20. //申请空间
    21. ListNode* node = ListBuyNode(x);
    22. //先处理node的前驱指针和后继指针
    23. node->prev = phead->prev;
    24. node->next = phead;
    25. //再处理之前的尾节点和phead
    26. phead->prev->next = node;
    27. phead->prev = node;
    28. }
    29. //打印
    30. void LTPrint(ListNode* phead)
    31. {
    32. //哨兵位不能改变
    33. ListNode* cur = phead->next;
    34. while (cur != phead)//当cur再次指向phead的时候,循环结束
    35. {
    36. printf("%d->", cur->data);
    37. cur = cur->next;
    38. }
    39. printf("\n");
    40. }
    41. //头插
    42. void LTPushFront(ListNode* phead, LTDataType x)
    43. {
    44. assert(phead);//注意哨兵位不能为空
    45. //申请空间
    46. ListNode* node = ListBuyNode(x);
    47. //node插入头节点之后才算头插
    48. //先处理node的前驱指针和后继指针
    49. node->prev = phead;
    50. node->next = phead->next;
    51. //再处理phead和phead->next
    52. phead->next->prev = node;
    53. phead->next = node;
    54. }

    2.3.3 test.c

    1. #include"List.h"
    2. void ListTest()
    3. {
    4. ListNode* plist = LTInit();
    5. LTPushBack(plist, 1);
    6. LTPushBack(plist, 2);
    7. LTPushBack(plist, 3);
    8. LTPushBack(plist, 4);
    9. LTPrint(plist);//1 2 3 4
    10. LTPushFront(plist, 5);
    11. LTPrint(plist);//5 1 2 3 4
    12. }
    13. int main()
    14. {
    15. ListTest();
    16. return 0;
    17. }

    2.3.4 代码测试运行


    2.4 尾删+头删🐊

    2.4.0 思路分析



    2.4.1 List.h

    1. //尾删
    2. void LTPopBack(ListNode* phead);
    3. //头删
    4. void LTPopFront(ListNode* phead);

    2.4.2 List.c

    1. //尾删
    2. void LTPopBack(ListNode* phead)
    3. {
    4. //不能为空链表,只有一个哨兵位不能尾删
    5. assert(phead&&(phead->prev!=phead||phead->next!=phead));
    6. ListNode* del = phead->prev;//phead->prev就是尾节点
    7. //先处理del
    8. del->prev->next = phead;
    9. //再处理phead
    10. phead->prev = del->prev;
    11. free(del);
    12. del = NULL;
    13. }
    14. //头删
    15. void LTPopFront(ListNode* phead)
    16. {
    17. //不能为空链表,只有一个哨兵位不能头删
    18. assert(phead && (phead->prev != phead || phead->next != phead));
    19. ListNode* del = phead->next;
    20. del->next->prev = phead;
    21. phead->next = del->next;
    22. free(del);
    23. del = NULL;
    24. }

    2.4.3 test.c

    1. #include"List.h"
    2. void ListTest()
    3. {
    4. ListNode* plist = LTInit();
    5. LTPushBack(plist, 1);
    6. LTPushBack(plist, 2);
    7. LTPushBack(plist, 3);
    8. LTPushBack(plist, 4);
    9. LTPrint(plist);//1 2 3 4
    10. LTPushFront(plist, 5);
    11. LTPrint(plist);//5 1 2 3 4
    12. LTPopBack(plist);
    13. LTPrint(plist);//5 1 2 3
    14. LTPopFront(plist);
    15. LTPrint(plist);//1 2 3
    16. }
    17. int main()
    18. {
    19. ListTest();
    20. return 0;
    21. }

    2.4.4 代码测试运行


    2.5 查找数据+pos节点后插入+删除pos节点🦩

    2.5.0 思路分析



    2.5.1 List.h

    1. //查找数据
    2. ListNode* LTFind(ListNode* phead, LTDataType x);
    3. //pos节点之后插入
    4. void LTPushAfter(ListNode* pos, LTDataType x);
    5. //删除pos节点
    6. void LTErase(ListNode* pos);

    2.5.2 List.c

    1. //查找数据
    2. ListNode* LTFind(ListNode* phead, LTDataType x)
    3. {
    4. assert(phead);
    5. ListNode* cur = phead->next;
    6. while (cur!= phead)
    7. {
    8. if (cur->data == x)
    9. {
    10. return cur;
    11. }
    12. cur = cur->next;
    13. }
    14. return NULL;
    15. }
    16. //pos节点之后插入
    17. void LTPushAfter(ListNode* pos, LTDataType x)
    18. {
    19. assert(pos);
    20. ListNode* node = ListBuyNode(x);
    21. //node
    22. node->next = pos->next;
    23. node->prev = pos;
    24. //pos
    25. pos->next = node;
    26. node->next->prev = node;
    27. }
    28. //删除pos节点
    29. void LTErase(ListNode* pos)
    30. {
    31. assert(pos);
    32. pos->prev->next = pos->next;
    33. pos->next->prev = pos->prev;
    34. free(pos);
    35. pos = NULL;
    36. }

    2.5.3 test.c

    1. #include"List.h"
    2. void ListTest()
    3. {
    4. ListNode* plist = LTInit();
    5. LTPushBack(plist, 1);
    6. LTPushBack(plist, 2);
    7. LTPushBack(plist, 3);
    8. LTPushBack(plist, 4);
    9. LTPrint(plist);//1 2 3 4
    10. LTPushFront(plist, 5);
    11. LTPrint(plist);//5 1 2 3 4
    12. LTPopBack(plist);
    13. LTPrint(plist);//5 1 2 3
    14. LTPopFront(plist);
    15. LTPrint(plist);//1 2 3
    16. ListNode* find = LTFind(plist, 1);
    17. /*LTPushAfter(find, 4);*/
    18. //LTPrint(plist);//1 4 2 3
    19. LTErase(find);
    20. LTPrint(plist);//2 3
    21. }
    22. int main()
    23. {
    24. ListTest();
    25. return 0;
    26. }

    2.5.4 代码测试运行



    2.6 销毁☄️

    2.6.0思路分析

    一开始的初始化,我们直接调用了接口,返回头节点进行初始化。我们没有考虑一级指针还是二级指针的问题。

    那么,最后的销毁又该怎么办?是一级指针?还是二级指针?下面我们一一来尝试

    1. 一级指针

    2.6.1 List.h
    1. //销毁
    2. void LTDestroy(ListNode* phead);

    2.6.2 List.c
    1. //销毁
    2. void LTDestroy(ListNode* phead)
    3. {
    4. assert(phead);
    5. ListNode* cur = phead->next;
    6. while(cur!=phead)
    7. {
    8. ListNode* next = cur->next;
    9. free(cur);
    10. cur = next;
    11. }
    12. //注意哨兵位还没有释放
    13. free(phead);
    14. phead = NULL;
    15. }

    2.6.3 test.c
    1. #include"List.h"
    2. void ListTest()
    3. {
    4. ListNode* plist = LTInit();
    5. LTPushBack(plist, 1);
    6. LTPushBack(plist, 2);
    7. LTPushBack(plist, 3);
    8. LTPushBack(plist, 4);
    9. LTPrint(plist);//1 2 3 4
    10. //LTPushFront(plist, 5);
    11. //LTPrint(plist);//5 1 2 3 4
    12. //LTPopBack(plist);
    13. //LTPrint(plist);//5 1 2 3
    14. //LTPopFront(plist);
    15. //LTPrint(plist);//1 2 3
    16. //ListNode* find = LTFind(plist, 1);
    17. /*LTPushAfter(find, 4);*/
    18. LTPrint(plist);//1 4 2 3
    19. //LTErase(find);
    20. //LTPrint(plist);//2 3
    21. LTDestroy(plist);
    22. }
    23. int main()
    24. {
    25. ListTest();
    26. return 0;
    27. }

    2.6.4 代码测试运行


    一级指针:
    phead的改变不影响plist,phead释放之后,plist指向已经释放掉的空间——>把plist置为空

    那么置为空之前,还要不要将plist指向的空间再free一次?

    我们尝试一下

    那么再思考一下:一级指针是会导致phead的改变不影响plist,那么plist是什么没有改变?是指plist保存的值没有被改变还是plist的这块空间的地址没有被释放?




    这里报错指的是plist指向无效地址

    注意⚠️
    如果plist的地址没有被释放,那么直接free(plist)是不会报错的

    所以在一级指针的情况下:plist的地址已经被释放了,没有被置为空的可以理解是plist的地址名称

    2.6.5 一级指针的改进---test.c


    2. 二级指针

    2.6.1 List.h
    1. //销毁
    2. //void LTDestroy(ListNode* phead);
    3. void LTDestroy(ListNode** phead);

    2.6.2 List.c
    1. //销毁
    2. void LTDestroy(ListNode** phead)
    3. {
    4. assert(phead && *phead);
    5. ListNode* cur = (*phead)->next;
    6. while (cur != *phead)
    7. {
    8. ListNode* next = cur->next;
    9. free(cur);
    10. cur = next;
    11. }
    12. free(*phead);
    13. *phead = NULL;
    14. }

    2.6.3 test.c
    1. #include"List.h"
    2. void ListTest()
    3. {
    4. ListNode* plist = LTInit();
    5. LTPushBack(plist, 1);
    6. LTPushBack(plist, 2);
    7. LTPushBack(plist, 3);
    8. LTPushBack(plist, 4);
    9. LTPrint(plist);//1 2 3 4
    10. //LTPushFront(plist, 5);
    11. //LTPrint(plist);//5 1 2 3 4
    12. //LTPopBack(plist);
    13. //LTPrint(plist);//5 1 2 3
    14. //LTPopFront(plist);
    15. //LTPrint(plist);//1 2 3
    16. //ListNode* find = LTFind(plist, 1);
    17. ///*LTPushAfter(find, 4);*/
    18. LTPrint(plist);//1 4 2 3
    19. //LTErase(find);
    20. //LTPrint(plist);//2 3
    21. //LTDestroy(plist);
    22. //plist = NULL;
    23. LTDestroy(&plist);
    24. }
    25. int main()
    26. {
    27. ListTest();
    28. return 0;
    29. }

    2.6.4 代码测试运行


    虽然,二级指针不用手动将plist置为空
    但是,更推荐一级指针,因为其他接口基本上都是一级指针——>保持接口的一致性


    2.7 完整代码💦

    2.7.1 List.h

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. typedef int LTDataType;
    8. //创建双向链表的结构体
    9. typedef struct ListNode {
    10. LTDataType data;
    11. struct ListNode* prev;
    12. struct ListNode* next;
    13. }ListNode;
    14. //初始化
    15. ListNode* LTInit();//不用传入参数,直接调用接口返回一个头节点
    16. //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
    17. //尾插
    18. void LTPushBack(ListNode* phead, LTDataType x);
    19. //打印
    20. void LTPrint(ListNode* phead);
    21. //头插
    22. void LTPushFront(ListNode* phead, LTDataType x);
    23. //尾删
    24. void LTPopBack(ListNode* phead);
    25. //头删
    26. void LTPopFront(ListNode* phead);
    27. //查找数据
    28. ListNode* LTFind(ListNode* phead, LTDataType x);
    29. //pos节点之后插入
    30. void LTPushAfter(ListNode* pos, LTDataType x);
    31. //删除pos节点
    32. void LTErase(ListNode* pos);
    33. //销毁
    34. void LTDestroy(ListNode* phead);

    2.7.2 List.c

    1. #include"List.h"
    2. //初始化
    3. ListNode* LTInit()//不用传入参数,直接调用接口返回一个头节点
    4. {
    5. //为头节点申请空间
    6. ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    7. //判断开辟是否成功
    8. if (phead == NULL)
    9. {
    10. perror("malloc error!\n");
    11. return;
    12. }
    13. //开辟成功--->初始化头节点
    14. phead->data = -1;//头节点不存储有效数据,可以任意赋值
    15. //只有哨兵位的时候,要实现双向链表,不能指向NULL,否则无法双向循环,所以我们指向自己
    16. phead->prev = phead->next = phead;
    17. return phead;
    18. }
    19. //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
    20. // 只改变数据,不改变地址
    21. //开辟空间
    22. ListNode* ListBuyNode(LTDataType x)
    23. {
    24. ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    25. if (node == NULL)
    26. {
    27. perror("malloc error!\n");
    28. return;
    29. }
    30. node->data = x;
    31. node->next = node->prev = NULL;
    32. return node;
    33. }
    34. //尾插
    35. void LTPushBack(ListNode* phead, LTDataType x)
    36. {
    37. assert(phead);//注意哨兵位不能为空
    38. //申请空间
    39. ListNode* node = ListBuyNode(x);
    40. //先处理node的前驱指针和后继指针
    41. node->prev = phead->prev;
    42. node->next = phead;
    43. //再处理之前的尾节点和phead
    44. phead->prev->next = node;
    45. phead->prev = node;
    46. }
    47. //打印
    48. void LTPrint(ListNode* phead)
    49. {
    50. //哨兵位不能改变
    51. ListNode* cur = phead->next;
    52. while (cur != phead)//当cur再次指向phead的时候,循环结束
    53. {
    54. printf("%d->", cur->data);
    55. cur = cur->next;
    56. }
    57. printf("\n");
    58. }
    59. //头插
    60. void LTPushFront(ListNode* phead, LTDataType x)
    61. {
    62. assert(phead);//注意哨兵位不能为空
    63. //申请空间
    64. ListNode* node = ListBuyNode(x);
    65. //node插入头节点之后才算头插
    66. //先处理node的前驱指针和后继指针
    67. node->prev = phead;
    68. node->next = phead->next;
    69. //再处理phead和phead->next
    70. phead->next->prev = node;
    71. phead->next = node;
    72. }
    73. //尾删
    74. void LTPopBack(ListNode* phead)
    75. {
    76. //不能为空链表,只有一个哨兵位不能尾删
    77. assert(phead&&(phead->prev!=phead||phead->next!=phead));
    78. ListNode* del = phead->prev;//phead->prev就是尾节点
    79. //先处理del
    80. del->prev->next = phead;
    81. //再处理phead
    82. phead->prev = del->prev;
    83. free(del);
    84. del = NULL;
    85. }
    86. //头删
    87. void LTPopFront(ListNode* phead)
    88. {
    89. //不能为空链表,只有一个哨兵位不能头删
    90. assert(phead && (phead->prev != phead || phead->next != phead));
    91. ListNode* del = phead->next;
    92. del->next->prev = phead;
    93. phead->next = del->next;
    94. free(del);
    95. del = NULL;
    96. }
    97. //查找数据
    98. ListNode* LTFind(ListNode* phead, LTDataType x)
    99. {
    100. assert(phead);
    101. ListNode* cur = phead->next;
    102. while (cur != phead)
    103. {
    104. if (cur->data == x)
    105. {
    106. return cur;
    107. }
    108. cur = cur->next;
    109. }
    110. return NULL;
    111. }
    112. //pos节点之后插入
    113. void LTPushAfter(ListNode* pos, LTDataType x)
    114. {
    115. assert(pos);
    116. ListNode* node = ListBuyNode(x);
    117. //node
    118. node->next = pos->next;
    119. node->prev = pos;
    120. //pos
    121. pos->next = node;
    122. node->next->prev = node;
    123. }
    124. //删除pos节点
    125. void LTErase(ListNode* pos)
    126. {
    127. assert(pos);
    128. pos->prev->next = pos->next;
    129. pos->next->prev = pos->prev;
    130. free(pos);
    131. pos = NULL;
    132. }
    133. //销毁
    134. void LTDestroy(ListNode* phead)
    135. {
    136. assert(phead);
    137. ListNode* cur = phead->next;
    138. while(cur!=phead)
    139. {
    140. ListNode* next = cur->next;
    141. free(cur);
    142. cur = next;
    143. }
    144. //注意哨兵位还没有释放
    145. free(phead);
    146. phead = NULL;
    147. }

    2.7.3 test.c

    1. #include"List.h"
    2. void ListTest()
    3. {
    4. ListNode* plist = LTInit();
    5. LTPushBack(plist, 1);
    6. LTPushBack(plist, 2);
    7. LTPushBack(plist, 3);
    8. LTPushBack(plist, 4);
    9. LTPrint(plist);//1 2 3 4
    10. LTPushFront(plist, 5);
    11. LTPrint(plist);//5 1 2 3 4
    12. LTPopBack(plist);
    13. LTPrint(plist);//5 1 2 3
    14. LTPopFront(plist);
    15. LTPrint(plist);//1 2 3
    16. ListNode* find = LTFind(plist, 1);
    17. /*LTPushAfter(find, 4);*/
    18. //LTPrint(plist);//1 4 2 3
    19. LTErase(find);
    20. LTPrint(plist);//2 3
    21. LTDestroy(plist);
    22. plist = NULL;
    23. }
    24. int main()
    25. {
    26. ListTest();
    27. return 0;
    28. }

    3. 顺序表和双向链表的分析🍻

    不同点顺序表链表(单链表)
    存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
    随机访问支持O(1)不支持:O(N)
    任意位置插入或者删除元素看你需要搬移元素,效率低O(N)只需要改变指针指向
    插入动态顺序表,空间不够的时候需要扩容没有容量的概念
    应用场景元素高效存储+频繁访问任意位置插入和删除频繁

    本次的分享到这里就结束了!!!

    PS:小江目前只是个新手小白。欢迎大家在评论区讨论哦!有问题也可以讨论的!

    如果对你有帮助的话,记得点赞👍+收藏⭐️+关注➕

  • 相关阅读:
    Fiddler/Charles - 夜神模拟器证书安装App抓包
    oracle 还原被覆盖的视图
    libhdfs(hdfs c 接口)配置记录
    leetcode Top100(12)最大子数组和
    论文写作 - CCF会议论文常用表述
    二百零一、Flink——Flink配置状态后端运行后报错:Can not create a Path from an empty string
    LeetCode每日一题(2201. Count Artifacts That Can Be Extracted)
    51单片机实现换能器超声波测水深
    036、目标检测-锚框
    Linux下远程连接MySQL数据库的方法
  • 原文地址:https://blog.csdn.net/2301_79184587/article/details/134088077