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

This article mainly introduces the relevant knowledge of how C language realizes the leading two-way circular linked list in the linear table, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe that you will gain something after reading this article on how to achieve the leading two-way circular linked list in the linear table in C language. Let's take a look.

I. the key points of this chapter

Lead the introduction of two-way circular linked list

Common interface implementation of leading two-way circular linked list

Implement interface summary

Online oj training and detailed explanation

Second, lead the two-way circular linked list introduction 2.1 what is the leading two-way circular linked list?

Lead: there is a header node of the sentinel bit, which is an invalid node and does not store any valid information, but it makes it easy for us to insert and delete head and tail without judging whether the header node is pointing to NULL. At the same time, there is no need to change the direction of the header pointer, so there is no need to pass the secondary pointer.

Bidirectional: each structure has two pointers to the previous structure and the latter structure.

Loop: the pointer to the last structure no longer points to NULL, but to the first structure. (one-way)

The front pointer of the first structure points to the last structure, and the back pointer of the last structure points to the first structure (bi-directional).

Graphic illustration

2.2 the two most commonly used linked list structures

It also has 8 kinds of structures, such as headless, one-way and two-way, whether the cycle is combined or not, but the longest one is headless unidirectional non-cyclic linked list and leading two-way cyclic linked list

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.

3. Initialization of typedef int DataType;typedef struct DListNode {DataType data; DListNode* prev; DListNode* next;} DListNode;3.2 lead two-way circular linked list void DListInint (DListNode** pphead) {* pphead = (DListNode*) malloc (sizeof (DListNode)); (* pphead)-> next = (* pphead) (* pphead)-> prev = (* pphead);}

Or you can initialize it by using the method that returns the node.

DListNode* DListInit () {DListNode* phead = (DListNode*) malloc (sizeof (DListNode)); phead- > next = phead; phead- > prev = phead; return phead;} 3.3.Create a new node DListNode* BuyDListNode (DataType x) {DListNode* temp = (DListNode*) malloc (sizeof (DListNode)) If (temp = = NULL) {printf ("malloc fail\ n"); exit (- 1);} temp- > prev = NULL; temp- > next = NULL; temp- > data = x; return temp;} 3.4 insert void DListPushBack (DListNode* phead,DataType x) {DListNode* newnode = BuyDListNode (x); DListNode* tail = phead- > prev Tail- > next = newnode; newnode- > prev = tail; newnode- > next = phead; phead- > prev = newnode;} 3.5 print linked list void DListNodePrint (DListNode* phead) {DListNode* cur = phead- > next; while (cur! = phead) {printf ("% d->", cur- > data); cur = cur- > next } printf ("NULL\ n");} 3.6 insert void DListNodePushFront (DListNode* phead, DataType x) {DListNode* next = phead- > next; DListNode* newnode = BuyDListNode (x); next- > prev = newnode; newnode- > next = next; newnode- > prev = phead; phead- > next = newnode Void DListNodePopBack (DListNode* phead) {if (phead- > next = = phead) {return;} DListNode* tail = phead- > prev; DListNode* prev = tail- > prev; prev- > next = phead; phead- > prev = prev; free (tail); tail = NULL } 3.8 head deletion void DListNodePopFront (DListNode* phead) {if (phead- > next = = phead) {return;} DListNode* firstnode = phead- > next; DListNode* secondnode = firstnode- > next; secondnode- > prev = phead; phead- > next = secondnode; free (firstnode); firstnode = NULL } 3.9 find data (return node address of data) DListNode* DListNodeFind (DListNode* phead, DataType x) {DListNode* firstnode = phead- > next; while (firstnode! = phead) {if (firstnode- > data = = x) {return firstnode;} firstnode = firstnode- > next;} return NULL Insert node void DListNodeInsert (DListNode* pos, DataType x) {DListNode* prev = pos- > prev; DListNode* newnode = BuyDListNode (x) before pos position; newnode- > next = pos; newnode- > prev = prev; prev- > next = newnode; pos- > prev = newnode;} 3.11Delete node void DListNodeErase (DListNode* pos) at pos location {DListNode* prev = pos- > prev DListNode* next = pos- > next; prev- > next = next; next- > prev = prev; free (pos); pos = NULL;} IV. Summary of implementation interfaces

Multi-drawing: can clearly show the process of change, conducive to the realization of programming.

Little knowledge: head- > next can represent both the member variables of the previous structure and the address of the latter structure. When head- > next is the left value, it represents the member variable, and when the right value is, it represents the address of the latter structure. It is important for linked lists to understand this.

Practice: true knowledge comes from practice

Lead a two-way circular linked list: it is easier to implement than a single linked list and does not have to discuss the length of the linked list in the same way as a single linked list. Although the structure is more complex, it is simpler and more convenient to use.

Online oj training and detailed explanation

The middle node of the linked list (force buckle)

Given a non-empty single linked list whose header node is head, return the middle node of the linked list.

If there are two intermediate nodes, the second intermediate node is returned.

Input: [1, 2, 3, 4, 5]

Output: node 3 in this list (serialized form: [3mem4pence5])

The node value returned is 3. (the serialization of the node is described by the evaluation system as [3pr 4je 5].

Notice that we returned an object of type ListNode ans

Like this:

Ans.val = 3, ans.next.val = 4, ans.next.next.val = 5 and ans.next.next.next = NULL.

Source: power buckle (LeetCode)

Train of thought: speed pointer

Take two pointers, both pointing to head initially. One is fast pointer (fast) taking two steps at a time, and the other is slow pointer (slow). When the fast pointer meets fast==NULL (even number of nodes) or fast- > next==NULL (odd number of nodes), slow points to the intermediate node and returns slow.

Struct ListNode* middleNode (struct ListNode* head) {struct ListNode* fast=head; struct ListNode* slow=head; while (fast&&fast- > next) {fast=fast- > next- > next; slow=slow- > next;} return slow;} about "how C language implements the leading two-way cyclic linked list in linear tables". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to realize the leading two-way circular linked list in the linear table in C language". If you want to learn more, you are welcome to follow the industry information channel.

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.