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

This article mainly explains "how to use C language to take the lead in two-way circular linked list". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "C language how to take the lead in two-way circular linked list" bar!

Two-way cyclic linked list

Last time we talked about the implementation of an one-way headless non-cyclic linked list. The characteristic of an one-way headless non-cyclic linked list is that it has a simple structure and is generally not used to store data alone. In practice, it is more as a substructure of other data structures. On the other hand, the leading two-way circular linked list is just the opposite of the headless unidirectional non-cyclic linked list, which has the most complex structure and is generally used to store data separately. Although this structure is complex, you will find that this structure is very simple to use after using monotonous implementation.

Structural diagram

The lead two-way circular linked list is logically like this, with the last node of the linked list pointing to the header node. The precursor of the header node points to the last node of the linked list. Therefore, the logical structure of an empty leading two-way circular linked list should look like this:

Its forerunner and successor both point to the head node.

Realize the leading two-way circular linked list

# pragma once#include#include#includetypedef int LTDataType;// defines the node of the linked list typedef struct ListNode {LTDataType data; struct ListNode* prev; struct ListNode* next;} LTNode;// creates the header node of the returned linked list .LTNode * ListCreate (); / / destroys the void ListDestory (LTNode* pHead) of the bidirectional linked list; / / prints the void ListPrint (LTNode* pHead) of the bidirectional linked list; / / inserts the void ListPushBack (LTNode* pHead, LTDataType x) at the end of the bidirectional linked list / / Bidirectional linked list footwall deletion void ListPopBack (LTNode* pHead); / Bidirectional linked list header insert void ListPushFront (LTNode* pHead, LTDataType x); / Bidirectional linked list header deletion void ListPopFront (LTNode* pHead); / Bidirectional linked list lookup LTNode* ListFind (LTNode* pHead, LTDataType x); / / Bidirectional linked list inserts void ListInsert (LTNode* pos, LTDataType x) in front of pos; / / Bidirectional linked list deletes node void ListErase (LTNode* pos) at pos location

First of all, we have to define the structure of a node, which consists of three parts: the leading pointer, the successor pointer and the data.

/ / define the node typedef struct ListNode {LTDataType data; struct ListNode* prev; struct ListNode* next;} LTNode of the linked list

Once defined, we will create a header node. We also encapsulate the process of creating the header node into a function, and the return value of this function is the pointer to the header node. When we use it, we create a variable to receive the pointer.

* * Note: * * when a header node is created, its data part does not store data, and its predecessor and successor point to itself.

LTNode* ListCreate () {LTNode* head = (LTNode*) malloc (sizeof (LTNode)); head- > next = head; head- > prev = head; return head;} / / int main () {LTNode* head = ListCreate (); return 0;} as used in the main function

After you have created the header node, you can insert data into the linked list. The tail insertion is implemented first, that is, a node is inserted after the last node of the linked list. Then there is head insertion, which is to insert a new node behind the head node.

/ insert void ListPushBack (LTNode* pHead, LTDataType x) {assert (pHead); LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)); / / New node created newnode- > data = x; / / insert new node into linked list LTNode* prev = pHead- > prev; prev- > next = newnode; newnode- > prev = prev; newnode- > next > pHead; pHead- > prev = newnode;} / / insert void ListPushFront (LTNode* pHead, LTDataType x) {assert (pHead) / / create a new node LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)); newnode- > data = x; / / insert the new node into the linked list LTNode* next = pHead- > next; pHead- > next = newnode; newnode- > prev = pHead; newnode- > next = next; next- > prev = newnode;}

There are insert data, there are delete data, there are also two kinds of delete data, one is the head deletion and the other is the tail deletion. Header deletion is to delete the node that the next of the header node points to. Tail deletion is to delete the last node. Take the lead in two-way circular linked list, which is very convenient when we delete it at the end. Because the leading node of the header node points to the last node of the linked list, we do not need to traverse the list to find the address of the last node.

/ / two-way chain header delete void ListPopFront (LTNode* pHead) {assert (pHead); assert (pHead- > next! = pHead); / / define a temporary variable to save the location of the node we want to delete LTNode* popnode = pHead- > next; / / the chain of the node to be deleted is broken LTNode* next = popnode- > next; pHead- > next = popnode- > next; next- > prev = pHead; / / free drop that node free (popnode); popnode = NULL } / / delete void ListPopBack (LTNode* pHead) {assert (pHead); assert (pHead- > prev! = pHead); LTNode* popnode = pHead- > prev; LTNode* prev = popnode- > prev; prev- > next = pHead; pHead- > prev = prev; free (popnode); popnode = NULL;}

After adding and deleting nodes, we implement the lookup node. The method also traverses the entire linked list and returns the address of a node if the value of the data of that node is the same as x. If you can't find it, return empty.

/ find LTNode* ListFind (LTNode* pHead, LTDataType x) {if (pHead- > next = = pHead) {return NULL;} LTNode* find = pHead- > next; while (find! = pHead) {if (find- > data = = x) {return find;} find = find- > next;} return NULL;}

To implement random insertion of data, random insertion here means that we insert a new node into the back or front of the node we specify. This node can be anywhere in the linked list. Our function passes in the address of a node, through which you can find the node to enter and leave, and connect the new node to the back of that node.

/ / two-way linked list deletes node void ListErase (LTNode* pos) {assert (pos) at pos location; LTNode* prev = pos- > prev; LTNode* next = pos- > next; prev- > next = next; next- > prev = prev; free (pos); pos = NULL;}

Print a two-way circular linked list, also by traversing the linked list

/ print void ListPrint (LTNode* pHead) {assert (pHead); LTNode* tail = pHead- > next; while (tail! = pHead) {printf ("% d->", tail- > data); tail = tail- > next;}}

After we finish using the linked list, we should remember to destroy the linked list to prevent memory leaks

/ / destroy void ListDestory (LTNode* pHead) {assert (pHead); LTNode* tail = pHead- > next; while (tail! = pHead) {LTNode* tmp = tail- > next; free (tail); tail = tmp;} free (pHead); pHead = NULL;} so far, I believe you have a deeper understanding of "C language to take the lead in two-way circular linked list". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue 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.