Shulou(Shulou.com)05/31 Report--

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

Create a linked list storage structure

We need to create a structure to store information about a linked list node.

Typedef int ListDataType;// first defines ListDataType as an int type, and can change it to a different type as needed / / create a linked list structure typedef struct ListNode {ListDataType data;// store data struct ListNode* next;// store the address pointer of the next node struct ListNode* prev;// store the address pointer of the previous node} ListNode; create the node

Every time we add data, we have to create a new node, but it is very troublesome to create it each time. So we consider encapsulating the function of creating a node into a function that can be called each time we want to use it.

ListNode* BuyListNode (ListDataType x) {ListNode* newnode = (ListNode*) malloc (sizeof (ListNode)); / / apply to memory for a new node if (newnode = = NULL) {printf ("BuyListNode::%s\ n", strerror (errno)); / / print the reason why the node space application failed exit (- 1); / / terminate the program} newnode- > data = x / / put x into the node data area of the application newnode- > next = NULL;// so that the next of the new node points to empty newnode- > prev = NULL;// let the prev of the new node point to empty return newnode;// return the address of the new node} initialization of the linked list

To take the lead in a two-way circular linked list we initialize it by applying for a sentinel head node. Next, let's look at two methods of initialization.

Void ListInit (ListNode** pphead) / / here we need to change the header node, so pass the secondary pointer {assert (pphead); / / check whether the address of the passed pphead is empty * pphead = BuyListNode (0); / / create a new Sentinel header node (* pphead)-> next = * pphead;// to point the node to itself (* pphead)-> prev = * pphead } ListNode* ListInit () {ListNode* phead = BuyListNode (0); / / create a new Sentinel header node phead- > next = phead;// so that the next of this node points to its own phead- > prev = phead;// let prev point to its return phead;// return Sentinel header node address} print of the bi-directional linked list

We print the data in the linked list by traversing the linked list.

Void ListPrint (ListNode* phead) {assert (phead); ListNode* cur = phead- > next;// lets cur point to the next node of the sentinel while (cur! = phead) / / conditional judgment of whether the linked list printing ends {printf ("% d", cur- > data); cur = cur- > next;} printf ("\ n") } two-way linked list tail insertion

The structure of the two-way cyclic linked list is better, so it is easy to find the tail node. The tail node is the node pointed to by the sentry node prev.

Void ListPushBack (ListNode* phead, ListDataType x) {assert (phead); / / check whether the passed header node is empty ListNode* tail = phead- > prev;// find the tail node of the linked list ListNode* newnode = BuyListNode (x); / / create a new node tail- > next = newnode;// so that the next of the tail node points to the new node newnode- > prev = tail / / Let the prev of the new node point to the previous tail node newnode- > next = phead;// let the next of the new node point to the header node phead- > prev = newnode;// let the header node point to the new tail node} two-way linked list deletion void ListPopBack (ListNode* phead) {assert (phead) If (phead- > next = = phead) / / if there are only sentinel nodes in the linked list, you cannot continue to delete return; ListNode* tail = phead- > prev;// find the tail node ListNode* tailPrev = tail- > prev;// define the previous node free (tail) of the tail node; / / release the node to be deleted tailPrev- > next = phead / / Let the former node point to the sentinel node phead- > prev = tailPrev;// let the sentry node point to the new tail node} two-way chain header insertion

The header insertion of a two-way linked list inserts a new data at the next location of the Sentinel node.

Note: the pointing relationship of this method can not be reversed at will, otherwise it will go wrong.

Void ListPushFront (ListNode* phead, ListDataType x) {assert (phead); ListNode* newnode = BuyListNode (x); / / create a new node newnode- > next = phead- > next;// the next of the new node points to the next node of the head node phead- > next- > prev = newnode;// head node points to the new node phead- > next = newnode;// head node points to the new node newnode- > prev = phead / / New node prev points to header node}

We can optimize the previous case to define the address of the next node of a next record header node. In this way, we can ignore the problem of pointing order and reduce the probability of error.

Void ListPushFront (ListNode* phead, ListDataType x) {assert (phead); ListNode* newnode = BuyListNode (x); / / create a new node ListNode* next = phead- > next;// defines the location of the next node of the next record header node phead- > next = newnode;// header node next points to the new node newnode- > prev = phead;// the prev of the new node points to next- > prev = newnode / / the prev of the next node of the header node points to the new stage newnode- > next = next;// the next of the new node points to the next node of the original header node} two-way chain header deletion

We first find the next node of the head node, and then release it. It is important to note that if the linked list is empty and there is only the Sentinel head node, we need to deal with it specially.

Void ListPopFront (ListNode* phead) {assert (phead); if (phead- > next = = NULL) / / return; ListNode* next = phead- > next- > next;// defines next to point to the next node free (phead- > next) of the node to be deleted; / / release the node phead- > next = next to be deleted / / Let the sentry header node point to the next node to be deleted next- > prev = phead;//. Let the prev of the next node to be deleted point to toujied} two-way linked list lookup.

If we want to make corresponding changes to the node of the specified location, we have to find the corresponding node, so we encapsulate the search data into a function. It is convenient for subsequent calls.

ListNode* ListFind (ListNode* phead, ListDataType x) {assert (phead); ListNode* cur = phead- > next;// lets cur point to the next node of the sentry head node while (cur! = phead) / / the condition for judging whether the linked list loop ends {if (cur- > data = = x) return cur; cur = cur- > next } return NULL;// cannot find the node for the node} insert the node before the bidirectional linked list pos

The second method is recommended, which is not error-prone.

Void ListInsert (ListNode* pos, ListDataType x) {assert (pos); ListNode* newnode = BuyListNode (x); / / create a new node pos- > prev- > next = newnode;//pos the next of the previous node points to the new node newnode- > prev = pos- > prev;// the prev of the new node points to the previous node of pos newnode- > next = pos;// the next of the new node points to the pos node pos- > prev = newnode / / prev of pos points to new node} void ListInsert (ListNode* pos, ListDataType x) {assert (pos); ListNode* newnode = BuyListNode (x); / / create a new node ListNode* posPrev = pos- > prev;// define the previous node of pos posPrev- > next = newnode;// make next of pos of pos point to new node newnode- > prev = posPrev / / the prev of the new node points to the previous node of the pos newnode- > next = pos;// the next of the new node points to the prev of the new node pos pos- > prev = newnode;//pos points to the new node} the node void ListErase (ListNode* pos) {assert (pos) of the pos location deleted by the two-way linked list; ListNode* prev = pos- > prev;//prev is the previous node ListNode* next = pos- > next of pos / / next is the last node of pos free (pos); / / release posjied prev- > next = next; next- > prev = prev;} destroy void ListDestroy (ListNode* phead) {assert (phead) of two-way linked list; ListNode* cur = phead- > next / / point to the next node of the sentinel node while (cur! = phead) / / cycle through each node of the linked list {ListNode* next = cur- > next;// record the next node location of cur free (cur); / / release the node cur = next of the cur location / / point to the next node} free (phead); / / release the sentinel header node}

Note: in writing the two-way linked list head insert, head delete, tail insert, tail delete, we can reuse the two functions at any position of the two-way linked list and delete those two functions. Those two functions can complete the functions of head insertion, head deletion, tail insertion and tail deletion.

The difference between sequential lists and linked lists

Advantages of sequential tables:

1. The physical space is continuous and easy to access randomly with subscript.

The 2.CPU cache hit rate will be higher.

Disadvantages of the sequence table:

1. Due to the need for physical space continuity, insufficient space needs to be expanded. The expansion itself has a certain consumption. Secondly, there is still a certain waste of space in the expansion mechanism.

two。 Insert and delete the head or middle part, move the data, and it is inefficient. O (N)

Advantages of linked list:

1. It is efficient to insert and delete data at any location. O (1)

two。 Request and release space on demand

List disadvantages:

Random access to the subscript is not supported. Some algorithms are not suitable to run on it. Such as: binary search, sorting and so on.

At this point, I believe you have a deeper understanding of "C language how 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.