1, Basic cognition
What is a cycle
The last node of the linked list points to the head node, forming a ring. Therefore, any other node can be found from any node in the circular linked list.
What is a double linked list
Two pointers are stored in the structure of the linked list, one pointing to the predecessor node and the other pointing to the successor node.
Basic structure
As shown in the figure, data is the stored number, prev and next point to the predecessor node and the successor node respectively.
2, Realize
1. Initialization
Initialization is to create a head node and return the head node.
Since it is a double linked list, initialization is to create this head node. Even if there is only one head node, it must abide by the rules and point to itself. Here I spent a picture to make it easy for everyone to understand.
Only one head node
The following is the code directly!
LTNode* SLTInit()
6 {
7 LTNode* phead= (LTNode*)malloc(sizeof(LTNode));
8 phead->next = phead;
9 phead->prev = phead;
10 return phead;
11 }
12
2. Head insertion method
First, create a new node to store data. Here, call the "create node" function. I put the "create node" function on the last side. Students who don't know it will go on to look.
Here, insert one end to the front of the list.
void LTPushFront(LTNode* phead, LTDataType x)
51 {
52 assert(phead != NULL);
53 LTNode* newnode = BuyLTNode(x);
54 LTNode* next = phead->next;
55
56
57
58 phead->next = newnode;
59 newnode->next = next;
60 newnode->prev = phead;
61 next->prev = newnode;
62
63 }
64
3. Tail insertion method
void LTPhshBack(LTNode* phead, LTDataType x)
21 {
22 assert(phead != NULL);
23 LTNode* newnode=BuyLTNode(x);
24 LTNode* tail = phead->prev;
25
26
27 tail->next = newnode;
28 newnode->prev = tail;
29
30 newnode->next = phead;
31 phead->prev = newnode;
32
33 }
34
4. Head deletion method
void LTPopFront(LTNode* phead)
81 {
82 assert(phead != NULL);
83 assert(phead->next != NULL);
84
85 LTNode* next = phead->next;
86 LTNode* nextNext= next->next;
87 phead->next = nextNext;
88 nextNext->prev = phead;
89 free(next);
90 next = NULL;
91
92 }
93
4. Tail deletion method
void LTPopBack(LTNode* phead)
66 {
67 assert(phead != NULL);
68 //Cannot delete sentinel position
69 assert(phead->next != phead);
70 LTNode* tail = phead->prev;
71 LTNode* cur = tail->prev;
72 cur->next = phead;
73 phead->prev = cur;
74
75 tail = NULL;
76 free(tail);
77 }
78
5. Search function
LTNode* LTFind(LTNode* phead, LTDataType x)
96 {
97 assert(phead != NULL);
98 LTNode* cur = phead->next;
99 while (cur!=phead)
100 {
101 if (cur->data == x)
102 {
103 return cur;
104 }
105 cur = cur->next;
106 }
107 return NULL;
108 }
109
110
6. Insert a number in a certain position
This function can be reused for head interpolation and tail interpolation.
void LTInsert(LTNode* pos, LTDataType x)
113 {
114 assert(pos != NULL);
115 LTNode* newnode = BuyLTNode(x);
116 LTNode* posPrev = pos->prev;
117
118 posPrev->next = newnode;
119 newnode->prev = posPrev;
120
121 newnode->next = pos;
122 pos->prev = newnode;
123
124 }
125
7. Delete the number in a certain position
This function can be reused to the head deletion method and the tail deletion method.
void LTErease(LTNode* pos)
127 {
128 assert(pos != NULL);
129 LTNode* posPrev = pos->prev;
130 LTNode* posNext = pos->next;
131
132 posPrev->next = posNext;
133 posNext->prev = posPrev;
134 free(pos);
135 pos = NULL;
136
137
8. Create node
LTNode* BuyLTNode(LTDataType x)
13 {
14 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
15 newnode->data = x;
16 }
17
summary
When inserting or deleting, you must remember to assert, otherwise there may be errors, but you can't find the error.
Double linked list is a storage structure that is updated on the basis of sequential list. Its advantages are that it is efficient to insert at any position, and it can apply for space on demand, without causing space waste.