Table of Contents
1. The structure of a two-way circular linked list
2. Creation of the structure of a two-way circular linked list
3. Initialization of two-way circular linked list
3.1 Printing of doubly linked list
4. Head plug of two-way circular linked list
5. Tail insertion of two-way circular linked list
6. Deletion of two-way circular linked list
6.1 Tail deletion
6.2 Header deletion
Section 6.3 Conclusion
7. Search
8. Insert data before pos position
9. Delete the data of pos position
10. Release the two-way circular linked list
Conclusion:
Foreword:
Doubly linked lists are a very common data structure in practical applications. Doubly linked lists are more complex in structure than singly linked lists. For example, a node in a singly linked list has only one pointer, while in a doubly linked list there are two pointers that jointly maintain the pointer. Node, one pointer points to the next node, and the other pointer points to the previous node. Although its structure is more complex, it is much more convenient than a singly linked list in realizing the function of adding, deleting, checking and modifying.
1. The structure of a two-way circular linked list
The first node head in the above figure is called the head node of the linked list (also called the sentinel node, its role is like a sentinel only responsible for standing guard). The structure of this node is the same as that of other nodes, except that the head node The data in is not valid, that is, when printing data, except the data of the head node, the data of other nodes must be printed.
The advantage of this head node is that there is no need to change the pointer of pilst, because the plist pointer always points to this node. You only need to modify the pointers to the internal members of the node. At the same time, the code can also be simplified, as detailed below.
2. Creation of the structure of the two-way circular linked list
The structure code of the node is as follows:
typedef int DListDataType;//int type redefinition to facilitate modification when using other types
typedef struct DoubleListNode
{
struct DoubleListNode* prev;//prev pointer to the previous node
struct DoubleListNode* next;//next pointer to the next node
DListDataType data;//Stored data
}DLNode;//Redefine the structure type
3. Initialization of two-way circular linked list
Initialization generates a head node, which is the sentinel node, and points to its node with a pointer. Because it is a circular linked list, both pointers of the head node must point to itself during initialization.
Therefore, when the linked list is empty, the head node (sentinel node) still exists, and the head node cannot be deleted when the linked list is deleted.
The initialization code is as follows:
DLNode* DLInit()//Initialization
{
DLNode* phead = BuyNode(-1);//Node creation function
phead->next = phead;//When there is only one head node, it also points to itself.
phead->prev = phead;
return phead;//Return the address of the head node
}
int main()
{
DLNode* plist = DLInit();//There is an external structure pointer to receive the return value
return 0;
}
3.1 Printing of doubly linked list
Print a doubly linked list to observe the results of each function:
void Print(DLNode* phead)//Print
{
assert(phead);
DLNode* cur = phead->next;
printf("Sentinel position<=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
}
4. Head insertion of two-way circular linked list
The idea is very simple, that is, point the next of the newnode node to d1, and the prev of d1 points to the newnode. The prev of newnode points to head, and the next of head points to newnode. But this involves the creation of nodes. Every time a node is inserted, a node needs to be created, so it is encapsulated into a function as follows:
DLNode* BuyNode(DListDataType x)
{
DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));//malloc opens up space
if (newnode == NULL)//Determine whether malloc is successful
{
perror("BuyNode");
return NULL;
}
newnode->data = x; //Assign the value to the created node
newnode->prev = NULL; // Leave it blank
newnode->next = NULL; // Leave blank
return newnode;//Return the address of the node
}
Header code:
void PushFront(DLNode* phead, DListDataType x)//head plug
{
assert(phead);
DLNode* next = phead->next;//Define a pointer next, which points to the next node of phead
DLNode* newnode = BuyNode(x);//Create node
phead->next = newnode;//The next node of phead is newnode
newnode->prev = phead; //The previous node of newnode is phead
newnode->next = next;//The next node of newnode is next
next->prev = newnode; //next previous node is newnode
}
5. Tail insertion of two-way circular linked list
The idea is similar to head insertion, but tail insertion can reflect the advantage of a two-way circular linked list in that there is no need to traverse the entire linked list to find the tail, because the prve of the head points to the tail, so the tail can be found directly, and then the tail insertion operation is performed.
The tail insertion code is as follows:
void PushBack(DLNode* phead, DListDataType x)//Tail insert
{
assert(phead);
DLNode* tail = phead->prev;//Find the tail node
DLNode* newnode = BuyNode(x);//Create node
tail->next = newnode;//Let the next node at the tail be newnode
newnode->prev = tail;//Let the previous node of newnode be tail
phead->prev = newnode;//Let the previous node of phead be newnode
newnode->next = phead;//Let the next node of newnode be phead
}
6. Deletion of two-way circular linked list
6.1 Tail Delete
Idea: From the above, we can know that finding the tail node is very simple, but here we need to define another pointer, which points to the node before tail. Then after releasing the tail, point the next of tailprev to the head node, and update the prev of the head node to point to the tailprev node to complete the tail deletion.
The tail deletion code is as follows:
bool Empty(DLNode* phead)//Determine whether the linked list is empty
{
assert(phead);
return phead->next == phead;//Return true if empty
}
void PopBack(DLNode* phead)//Tail deletion
{
assert(phead);
assert(!Empty(phead));//If true is returned, it means that the linked list is empty, then the result is inverted and the assertion fails.
DLNode* tail = phead->prev;//Define tail pointer
DLNode* tailPrev = tail->prev;//Define tailPrev pointer
tailPrev->next = phead;//The next node of tailPrev is phead
phead->prev = tailPrev;//Let the previous node of phead be tailPrev
free(tail);//Release the tail node
}
6.2 Header deletion
Idea: Connect the head node and the node pointed by second to each other, and then release first.
The header deletion code is as follows:
void PopFront(DLNode* phead)//head deletion
{
assert(phead);
assert(!Empty(phead));//The linked list is empty
DLNode* first = phead->next;//define pointer
DLNode* second = first->next;
phead->next = second;//Connect the head node to the second node
second->prev = phead;
free(first);//Delete the first node
}
Conclusion of Section 6.3
This can reflect an advantage of a doubly linked list over a singly linked list: when the linked list has only one node, it can be deleted directly without setting the plist pointer to empty, because the plist pointer always points to the sentinel node. If a singly linked list is to be deleted, one more judgment must be made, and whether the plist pointer is empty must also be considered.
However, the disadvantage is that if you delete the empty linked list, the sentinel bit will also be deleted. At this time, plist is a wild pointer, and dereferencing pilst will cause illegal access problems. Therefore, it is necessary to assert whether the linked list is empty. If it is empty, it cannot be deleted.
7. Search
The search function is relatively simple. You only need to traverse the linked list and return the address pos of the node you want to find. However, you need to pay attention to one thing here, namely: the conditions for traversing the linked list, because the data of the head node is not valid, so the next one of the head node The node starts to be traversed until it reaches the head node.
Find the code as follows:
DLNode* Seach(DLNode* phead, DListDataType x)//Search
{
assert(phead);
DLNode* cur = phead->next;//Use cur instead of phead to traverse
while (cur != phead)//End the loop when cur points to the head node
{
if (cur->data == x)
return cur;//If equal to return cur address
cur = cur->next;//Traverse cur
}
return NULL;//If there is no data in the linked list, return NULL
}
The search function is usually paired with the middle insertion and middle deletion functions, because the search function returns an address pos, and then this address is directly passed to the middle insertion and middle deletion functions, and the function can be realized very well.
8. Insert data before pos position
Idea: You can get the address of the pos position by searching the function, then define a pointer prev, and then connect the newnode node to the prev node and pos node.
The pos pre-insertion code is as follows:
void PosInsert(DLNode* pos, DListDataType x)//Insert before pos
{
assert(pos);
DLNode* posPrev = pos->prev;//Define posprev pointer, pointing to the node before pos
DLNode* newnode = BuyNode(x);//Create node
newnode->prev = posPrev;//The following operation is to connect the newnode node with the pos and posprev nodes
posPrev->next = newnode;
newnode->next = pos;
pos->prev = newnode;
}
The test code for inserting data and searching data is as follows. You can test the previous interface as you like:
int main()
{
DLNode* plist = DLInit();//Initialization
PushFront(plist, 4);//Head plug
PushFront(plist, 3);
PushFront(plist, 2);
PushFront(plist, 1);
PushBack(plist, 5);//Tail insertion
PushBack(plist, 6);
/*PopFront(plist);
PopBack(plist);*/
Print(plist);//Print
DLNode* pos = Seach(plist, 1);//Search
if(pos)
{
PosInsert(pos, 20);//Insert in the middle
}
printf("\\
");//Newline
Print(plist);//Print
DLNodeFree(plist);//Release the linked list
plist = NULL;//Manually empty the plist
return 0;
}
operation result:
9. Delete data at pos position
Idea: Connect the two nodes posPrev and posNext, and then release pos.
Delete the pos position code as follows:
void PosDestroy(DLNode* pos)//Delete pos location
{
assert(pos);
DLNode* posPrev = pos->prev;//Define two pointers, one pointing to the node before pos and one pointing to the node behind pos
DLNode* posNext = pos->next;
posPrev->next = posNext;//Associate the nodes pointed to by these two pointers together
posNext->prev = posPrev;
free(pos);//Release pos node
}
10. Release the two-way circular linked list
Because each node in the linked list (including the sentinel bit node) is applied for on the heap, these spaces should be released after use.
The release function code is as follows:
void DLNodeFree(DLNode* phead)//Release the linked list
{
assert(phead);//Assert here, otherwise the null pointer will be dereferenced below
DLNode* cur = phead->next;//Use cur pointer instead of phead to traverse
\t
while (cur != phead)
{
//The function of the Next pointer is to remember the position to prevent the next node from being found after releasing cur.
DLNode* Next = cur->next;
free(cur);//Release the node pointed by cur
cur = Next;//Give cur a new position
}
free(phead);//Finally release the sentinel bit (head node)
}
int main()
{
DLNode* plist = DLInit();
DLNodeFree(plist);
plist = NULL;//The wild pointer of the external plist at this time must be manually set empty
return 0;
}
Points to note here: If phead is cleared inside the DLNodeFree function, it will not affect the value of the external plist, because phead is only a temporary copy of the plist, unless the address of pilst is passed to the DLNodeFree function using a secondary pointer. To operate, or manually empty the plist outside, both methods can empty the plist.
Conclusion:
The above is about the implementation and analysis of two-way circular linked lists. If this article is helpful to you, I hope you can like it + follow + collect Oh! If there are any omissions or errors, please feel free to add them in the comment area~! ! thank you all! !
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57517 people are learning the system