Shulou(Shulou.com)06/01 Report--

This article mainly introduces how the C language to take the lead in two-way circular linked list, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, let the editor take you to understand it.

Preface

These two kinds of linked lists are most commonly used in real life. Headless one-way acyclic linked list. And take the lead in two-way circular linked lists.

Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more as a substructure of other data structures, such as hash buckets, adjacency tables of graphs, and so on. In addition, this structure appears a lot in written interviews.

Lead two-way circular linked list: the structure is the most complex and is generally used to store data separately. The linked list data structure used in practice is to take the lead in two-way circular linked list. In addition, although the structure of this structure is complex, but the use of code implementation will find that the structure will bring a lot of advantages, but the implementation is simple, we will know after the code implementation.

1. Create a structure

Note: typedef works on line 7. So 5 and 6 also need to write the struct ListNode type.

Typedef int LNDataType;typedef struct ListNode {struct ListNode* prev; struct ListNode* next; LNDataTypeval;} LN;2.malloc New Node

Note: it is necessary to determine whether the newly opened node is empty.

/ / apply for a new node LN* BuynewNode (LNDataType x) {LN* newNode = (LN*) malloc (sizeof (LN)); if (newNode = = NULL) {printf ("malloc fail"); exit (- 1);} newNode- > next = NULL; newNode- > prev = NULL; newNode- > val = x; return newNode;} 3. Create Sentinel Node

Note: because you need to change the content of the plist pointer, that is, change the point of the plist pointer, you need to pass the address of the plist.

In a word: the address of the person whose content needs to be changed.

One thing that is very coincidental and wonderful here is that the successors and forerunners of phead point to themselves (phead), which mimics the sentinel nodes in the C++STL library.

I can only admire the god who came up with these things. If the sentinel node is designed in this way, the subsequent tail insertion and tail deletion are particularly ingenious.

Test.c

LN* plist = NULL; ListNodeInit (& plist)

List.h

/ / initialize node void ListNodeInit (LN** pphead) {LN* newNode = BuynewNode (0); * pphead = newNode; (* pphead)-> next = * pphead; (* pphead)-> prev = * pphead;} 4. Tail insertion

Note: the reason for the assertion is that even if the linked list does not have a node, the linked list at least has a head, so the phead is definitely not empty.

The reason for not passing the address here is that you don't need to change the direction of the plist, you change the value in the structure that the plist points to.

The tail insertion of multiple nodes is shown in the figure.

The tail insertion of a node.

/ / insert void ListNodePushBack (LN* phead, LNDataType x) {assert (phead); LN* newNode = BuynewNode (x); LN* tail = phead- > prev; tail- > next = newNode; newNode- > prev = tail; newNode- > next = phead; phead- > prev = newNode;} 5. Printing

Note: cur starts from the second position because it takes a lead.

/ / print void ListNodePrint (LN* phead) {LN* cur = phead- > next; while (cur! = phead) {printf ("% d", cur- > val); cur = cur- > next;} printf ("\ n");} 6. Tail deletion

Note that the header node cannot be deleted. If the free turns around the node, it will cause a wild pointer and illegal access when you visit it again.

So use assert to assert that it is not the first node.

/ / delete void ListNodePopBack (LN* phead) {assert (phead); assert (phead- > next! = phead); LN* tail = phead- > prev; LN* tailPrev = tail- > prev; free (tail); tail = NULL; phead- > prev = tailPrev; tailPrev- > next = phead;} 7. Head insertion

It is best to record the next node with next. It's convenient and clear.

/ / insert void ListNodePushFront (LN* phead, LNDataType x) {assert (phead); LN* newNode = BuynewNode (x); LN* next = phead- > next; phead- > next = newNode; newNode- > prev = phead; newNode- > next = next; next- > prev = newNode;} 8. Insert in front of the specified location pos

General situation

When there is only one node.

In both cases, the following code applies.

/ / insert before the specified position. The limit is void ListNodeInsert (LN* pos, LNDataType x) {if (pos = = NULL) {printf ("not found\ n"); return;} LN* newNode = BuynewNode (x); LN* tailPrev = pos- > prev; tailPrev- > next = newNode; newNode- > prev = tailPrev NewNode- > next = pos; pos- > prev = newNode;} 9. Delete the specified location pos node

Normal situation

Limit tail deletion

In both cases, the following code applies.

/ / delete void ListNodeErease (LN* phead, LN* pos) {if (pos = = phead | | pos = = NULL) {printf ("pos pointer, or empty\ n"); return;} LN* posPrev = pos- > prev; LN* posNext = pos- > next; posPrev- > next = posNext; posNext- > prev = posPrev; free (pos) Pos = NULL;} 10. Destroy linked list

Note: this is equivalent to the free after malloc is used up. Otherwise, it will cause a memory leak.

Cur can be empty, but it is not very useful, because cur is a formal parameter, a formal parameter is a temporary copy of a parameter, and a blank parameter does not change the argument. External arguments can still illegally access the space pointed to by cur.

/ destroy void ListNodeDestroy (LN* phead) {assert (phead); LN* cur = phead- > next; LN* next = cur- > next; while (cur! = phead) {next = cur- > next; free (cur); cur = NULL; cur = next;} free (phead) Phead = NULL;} Thank you for reading this article carefully. I hope the article "how to take the lead in two-way circular linked list in C language" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.