数据结构(3) - 双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

代码如下：
double-list.c

1.   1 /**
2.   2  * C data structure double linked list example.
3.   3  *
4.   4  * License - MIT.
5.   5 */
6.   6
7.   7 #include "double-list.h"
8.   8
9.   9
10. 10 /**
11. 11  * doulist_empty - Determine if the list is empty.
12. 12 */
13. 13 bool doulist_empty(LPDOUBLELIST lpHead)
14. 14 {
15. 15     return (lpHead == lpHead->next);
16. 16 }
17. 17
18. 18
19. 19 /**
20. 20  * doulist_show - Display list data.
21. 21 */
22. 22 int doulist_show(LPDOUBLELIST lpHead)
23. 23 {
24. 24     LPDOUBLELIST tmp;
25. 25
26. 26     for (tmp = lpHead->next; tmp != lpHead; tmp = tmp->next)
27. 27         printf("%d ", tmp->data);
28. 28
29. 29     printf("\n");
30. 30
31. 31     return 0;
32. 32 }
33. 33
34. 34
35. 35 /**
36. 36  * doulist_insert - Add the specified data at specified node next location.
37. 37 */
38. 38 int doulist_insert(LPDOUBLELIST lpHead, LPDOUBLELIST lpNode)
39. 39 {
40. 40     lpNode->next        = lpHead->next;
41. 41     lpHead->next->prev  = lpNode;
42. 42     lpNode->prev        = lpHead;
43. 43     lpHead->next        = lpNode;
44. 44
45. 45     return 0;
46. 46 }
47. 47
48. 48
49. 49 /**
50. 50  * doulist_insert_tail - Insert data to list tail.
51. 51 */
52. 52 int doulist_insert_tail(LPDOUBLELIST lpHead, LPDOUBLELIST lpNode)
53. 53 {
54. 54     lpNode->prev        = lpHead->prev;
55. 55     lpHead->prev->next  = lpNode;
56. 56     lpNode->next        = lpHead;
57. 57     lpHead->prev        = lpNode;
58. 58
59. 59     return 0;
60. 60 }
61. 61
62. 62
63. 63 /**
64. 64  * doulist_del - Deletes the specified data by specified node next location.
65. 65 */
66. 66 int doulist_del(LPDOUBLELIST lpNode)
67. 67 {
68. 68     lpNode->prev->next = lpNode->next;
69. 69     lpNode->next->prev = lpNode->prev;
70. 70
71. 71     return 0;
72. 72 }
73. 73
74. 74
75. 75 /**
76. 76  * doulist_init - Initialize double linked list.
77. 77 */
78. 78 int doulist_init(LPDOUBLELIST *lpHead)
79. 79 {
80. 80     *lpHead = (LPDOUBLELIST) malloc(sizeof(DOUBLELIST));
81. 81     if (NULL == *lpHead) {
82. 82         return -1;
83. 83     }
84. 84
85. 85     (*lpHead)->next = *lpHead;
86. 86     (*lpHead)->prev = *lpHead;
87. 87
88. 88     return 0;
89. 89 }
90. 90
91. 91
92. 92 /**
93. 93  * doulist_clear - clear double linked list.
94. 94 */
95. 95 int doulist_clear(LPDOUBLELIST lpHead)
96. 96 {
97. 97     LPDOUBLELIST tmp;
98. 98
99. 99     if (!doulist_empty(lpHead)) {
100. 100         for (tmp = lpHead->next; tmp != lpHead; tmp = tmp->next) {
101. 101             doulist_del(tmp);
102. 102             free(tmp);
103. 103         }
104. 104     }
105. 105
106. 106     tmp = NULL;
107. 107
108. 108     free(lpHead);
109. 109     lpHead = NULL;
110. 110
111. 111     return 0;
112. 112 }

复制代码

 
double-list.h

1. 1 /**
2. 2  * C data structure double linked list example.
3. 3  *
4. 4  * License - MIT.
5. 5 */
6. 6
7. 7 #ifndef __DOUBLE_LIST_H__
8. 8 #define __DOUBLE_LIST_H__
9. 9
10. 10
11. 11 #include <stdio.h>
12. 12 #include <stdlib.h>
13. 13 #include <stdbool.h>
14. 14
15. 15 typedef struct _DOUBLELIST{
16. 16     int data;
17. 17     struct _DOUBLELIST *prev, *next;
18. 18 } DOUBLELIST, *LPDOUBLELIST;
19. 19
20. 20
21. 21 bool doulist_empty      (LPDOUBLELIST lpHead);
22. 22 int doulist_show        (LPDOUBLELIST lpHead);
23. 23 int doulist_insert      (LPDOUBLELIST lpHead, LPDOUBLELIST lpNode);
24. 24 int doulist_insert_tail (LPDOUBLELIST lpHead, LPDOUBLELIST lpNode);
25. 25 int doulist_del         (LPDOUBLELIST lpNode);
26. 26 int doulist_init        (LPDOUBLELIST *lpHead);
27. 27 int doulist_clear       (LPDOUBLELIST lpHead);
28. 28
29. 29
30. 30 #endif /* __DOUBLE_LIST_H__ */

复制代码

 
main.c

1. 1 /**
2. 2  * C data structure double linked list example.
3. 3  *
4. 4  * License - MIT.
5. 5 */
6. 6
7. 7 #include <stdio.h>
8. 8
9. 9 #include "double-list.h"
10. 10
11. 11
12. 12 #define MAX_TEST_NUM                10
13. 13
14. 14
15. 15 /**
16. 16  * test_sort - Sort the data.
17. 17 */
18. 18 int test_sort(LPDOUBLELIST lpHead)
19. 19 {
20. 20     LPDOUBLELIST pos, tmp;
21. 21
22. 22     pos = lpHead->prev;
23. 23
24. 24     while (pos != lpHead)
25. 25     {
26. 26         if (1 == (pos->data % 2)) {
27. 27             pos = pos->prev;
28. 28         }
29. 29         else {
30. 30             tmp = pos;
31. 31             pos = pos->prev;
32. 32
33. 33             doulist_del(tmp);
34. 34             doulist_insert_tail(lpHead, tmp);
35. 35         }
36. 36     }
37. 37
38. 38     return 0;
39. 39 }
40. 40
41. 41
42. 42 /**
43. 43  * test_create - Create single list example.
44. 44 */
45. 45 int test_create(LPDOUBLELIST lpHead)
46. 46 {
47. 47     int i;
48. 48     LPDOUBLELIST newNode;
49. 49
50. 50     for (i = 0; i < MAX_TEST_NUM; i++) {
51. 51         newNode = (LPDOUBLELIST) malloc(sizeof(DOUBLELIST));
52. 52         if (NULL == newNode) {
53. 53             return -1;
54. 54         }
55. 55
56. 56         newNode->data = i + 1;
57. 57         doulist_insert_tail(lpHead, newNode);
58. 58     }
59. 59
60. 60     return 0;
61. 61 }
62. 62
63. 63
64. 64 /**
65. 65  * Main function.
66. 66 */
67. 67 int main(void)
68. 68 {
69. 69     LPDOUBLELIST lphead = NULL;
70. 70
71. 71     doulist_init(&lphead);
72. 72
73. 73     test_create(lphead);
74. 74     doulist_show(lphead);
75. 75
76. 76     test_sort(lphead);
77. 77     doulist_show(lphead);
78. 78
79. 79     doulist_clear(lphead);
80. 80
81. 81     return 0;
82. 82 }

复制代码

 
Makefile

1. 1 # Makefile
2. 2 CC = gcc
3. 3 CFLAGS = -Wall -g -O0
4. 4
5. 5 SRC = main.c double-list.c
6. 6
7. 7 OBJ = doulist-test
8. 8
9. 9 $(OBJ) : $(SRC)
10. 10     $(CC) $(CFLAGS) -o $@ $^
11. 11
12. 12 clean:
13. 13     $(RM) $(OBJ) *.o *.*.sw?

复制代码

 
完整代码请参考Github: [Link] [https://github.com/Phoebus-Ma/C-Helper/tree/main/Class-1/List.C]

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！