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

This article introduces the relevant knowledge of "how to realize the C language double-linked list". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Define

The linked list stores the data elements in the linear table through a set of arbitrary storage units, each node contains two fields: the domain in which the information of the data elements is stored is called the data field, and the domain in which the addresses of its subsequent elements are stored is called the pointer domain. Therefore, the linear list of n elements is connected into a "chain" by the pointer field of each node, which is called the linked list. If each node of this linked list contains two pointer fields, it is called a double linked list.

The node structure of a double-linked list is defined as follows:

Typedef struct node {DataType data; struct node * llink; struct node * rlink;} DLinkList

Like a single linked list, you need a node similar to the "header node" (marked as rear), whose data field is empty, the llink pointer in the pointer domain points to the header node, and the rlink pointer points to the footer node. The llink pointer of the header node points to NULL, and the rlink pointer of the table footer node points to NULL.

1. Delete

Assuming that node p is a node to be deleted, we only need to make the rlink pointer of the previous node of p (p-> llink- > rlink) point to the next node of p (p-> rlink), and let the llink pointer of the latter node of p point to the previous pointer of p (p-> llink), and then release the memory space occupied by p to complete the deletion operation. Because this is a double-linked list deletion algorithm, there will be a slight difference in the header or footer of the node to be deleted, but as long as you grasp the core algorithm:

P-> llink- > rlink = p-> rlink; p-> rlink- > llink = p-> llink; free (p)

Then carry out special treatment on the header and footer node (change the pointer domain of the rear pointer).

Examples of double-linked list deletion algorithms are as follows:

Int DeleteDLinkList (DLinkList * rear, DLinkList * p) / * deletes node p in the double linked list and returns 1 successfully, otherwise it returns zero / {DLinkList * Q = p-> rlink, * s = p-> llink;/*q points to p's successor, s points to p's predecessor * / if (slots null & q==NULL) / * deletes the last node * / {rear- > rlink = p-> llink; p-> llink- > rlink = p-> rlink Free (p); return 1;} if (s==NULL & & qflux null) / * the first node is deleted * / {rear- > llink = p-> rlink; p-> rlink- > llink = p-> llink; free (p); return 1;} if (s==NULL & q==NULL) / * double linked list has only one node * / {rear- > rlink = rear- > llink = NULL Free (p); return 1;} if (slots null & & qnotify null) {p-> llink- > rlink = p-> rlink; p-> rlink- > llink = p-> llink; free (p); return 1;} return 0;} 2. insert

Suppose that to insert node Q between node p and the next node of p, the llink pointer (Q-> llink) and rlink pointer (Q-> rlink) of ① shilling Q are required to point to the latter node of p and p (p-> rlink), respectively. ② then makes the llink pointer (p-> rlink- > llink) of the latter node of p point to Q, and the rlink pointer of ③ p (p-> rlink) to Q. A little analysis shows that if the three steps of ①②③ are in the wrong order, the insertion cannot be completed. Expressed in code is:

Q-> llink = p; Q-> rlink = p-> rlink; p-> rlink- > llink = Q; p-> rlink = Q

Similarly, to insert an element in the header or footer, hold on to the core algorithm and change the pointer field of the rear.

Examples of double-linked list insertion algorithms are as follows:

Int Insert (DLinkList * rear, DLinkList * p, DataType x) {DLinkList * Q = (DLinkList *) malloc (sizeof (DLinkList)); if (Q = = NULL) return 0; Q-> data = x DLinkList * data field assignment * / if (p-> rlink = = NULL) / * insert elements * / {rear- > rlink = Q; Q-> llink = p; Q-> rlink = p-> rlink; p-> rlink = Q at the end of the table Return 1;} if (p = = rear) / * if p is rear, insert the element * / {Q-> llink = rear- > llink- > llink; Q-> rlink = rear- > llink; rear- > llink- > llink = Q; rear- > llink = Q; return 1;} Q-> llink = p; Q-> rlink = p-> rlink; p-> rlink- > llink = Q P-> rlink = Q; return 1;} 3. Establish

Using the method of inserting elements at the end of the table mentioned earlier, we can insert it at the end of the table every time a new node is created. When you start to build a double-linked list, let the llink pointer (rear- > llink) of rear point to the header node, and let the header node point to NULL;. When the establishment is finished, let the rlink pointer (rear- > rlink) of rear point to the last node to complete the establishment of the double-linked list.

DLinkList * CreateDLinkList () {DLinkList * rear, * p, * Q; rear= (DLinkList *) malloc (sizeof (DLinkList)); p = (DLinkList *) malloc (sizeof (DLinkList)); if (rear==NULL | | p==NULL) {free (rear); free (p); return NULL;} DataType x; scanf (& x); p-> data = x; rear- > llink = p; p-> llink = NULL P-> rlink = NULL; scanf (& x); while (x! = flag) / * flag is the flag * / {Q = (DLinkList *) malloc (sizeof (DLinkList)); if (Q = = NULL) {DLinkList * pr; p = rear- > llink; while (p! = NULL) {pr = p-> rlink Free (p); p = pr;} free (rear); return NULL;} Q-> data = x; Q-> llink = p; Q-> rlink = NULL; p-> rlink = Q; scanf (& x);} rear- > rlink = q; return rear } DLinkList * CreateDLinkList () {DLinkList * rear, * p, * Q; rear= (DLinkList *) malloc (sizeof (DLinkList)); p = (DLinkList *) malloc (sizeof (DLinkList)); if (rear==NULL | | p==NULL) {free (rear); free (p); return NULL;} DataType x; scanf (& x); p-> data = x; rear- > llink = p; p-> llink = NULL P-> rlink = NULL; scanf (& x); while (x! = flag) / * flag is the flag * / {Q = (DLinkList *) malloc (sizeof (DLinkList)); if (Q = = NULL) {DLinkList * pr; p = rear- > llink; while (p! = NULL) {pr = p-> rlink Free (p); p = pr;} free (rear); return NULL;} Q-> data = x; Q-> llink = p; Q-> rlink = NULL; p-> rlink = Q; scanf (& x);} rear- > rlink = q; return rear;} 4. Find

Compared with single linked list, the advantage of double linked list is that it can realize two-way search. Suppose the pointer p and Q traverse each node of the double-linked list from the header and the footer to the middle, respectively, and the traversal is considered to have ended when pause _ traq or p-> llink==q.

DLinkList * SearchDLinkList (DLinkList * rear, DataType x) {DLinkList * p = rear- > llink, * Q = rear- > rlink; while (p-> rlink; Q = Q-> llink; if (p-> llink==q) break;} if (p-> data = = x) return p; else if (Q-> data = = x) return Q Else return NULL;} "C language double linked list how to achieve" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.