Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

What are the types of linked lists of data structures

2025-01-18 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >

Share

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

This article mainly introduces "what are the types of linked lists of data structures". In daily operation, I believe that many people have doubts about the types of linked lists of data structures. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "which types of linked lists of data structures"! Next, please follow the editor to study!

1. One-way cyclic linked list 1.1. structure

The pointer domain of the trailing node of a single linked list is NULL, so the single linked list terminates here. If we use the pointer domain of the trailing node of a single linked list to store the address of the header node, that is, the direct successor node of the tail node is the header node, then the single linked list forms a ring (loop), which is called a single cyclic linked list.

1.2. Realization idea

The unidirectional cyclic linked list evolved from the single linked list, which is the "son" of the single linked list, so the structure of the single linked list is completely applicable to the unidirectional cyclic linked list. As you can see from the above figure, the structure has not changed much. The difference between the two is only in the tail node, so we just need to work on the tail node and the operations related to the tail node.

Therefore, the structure of a unidirectional circular linked list is the same as that of a single linked list.

/ * Node structure of unidirectional circular linked list * / typedef struct _ Node {int data; / / data field: store data struct _ Node * next; / / pointer domain: store the address of the direct successor node} Node

In order to unify the operation of empty linked list and non-empty linked list, we use the linked list of leading nodes to implement it.

1.3. Empty linked list and initialization

An empty linked list is shown in the figure, with only one header pointer and header node:

Empty linked list

The pointer field of the header node points to itself to form a loop, by which we can determine whether the linked list is empty.

If (head- > next = = head) {printf ("empty linked list.\ n");}

It's easy to initialize an empty linked list by creating a header node so that the next pointer of the header node points to itself:

Node * create_node (int elem) {Node * new = (Node *) malloc (sizeof (Node)); new- > data = elem; new- > next = NULL; return new;} / * initialize the linked list * p_head: pointer to the header pointer * / void init (Node * * p_head) {/ / create header node Node * head_node = create_node (0) / / the header pointer points to the header node * p_head = head_node; / / the next pointer of the header node points to itself, forming a ring head_node- > next = head_node;} 1.4. Insert operation

Only display head insertion and tail insertion are shown here.

[head insertion]

Because of the lead node, there is no need to consider whether it is an empty linked list. The following figure shows the process of inserting two elements into an empty linked table:

One-way cyclic chain meter insertion process

/ * head insertion, the new node is the direct successor of the head node * p_head: pointer to the head pointer * elem: data of the new node * / void insert_at_head (Node * * p_head, int elem) {Node * new = create_node (elem); Node * head_node = * padded head; / / head node / / new- > next = head_node- > next after the new node is inserted into the header node Head_node- > next = new;} [tail interpolation]

Because we do not set a tail pointer to the tail node in order to keep it as simple as possible, we need to traverse to the tail node with the help of a pointer before inserting it.

/ * tail insertion: the newly inserted node is always at the end of the chain list * p_head: pointer to the head pointer * elem: data of the new node * / void insert_at_tail (Node * * p_head, int elem) {Node * new = create_node (elem); Node * head_node = * padded head; / / head node Node * tail = head_node / / the tail pointer points to the header node while (tail- > next! = head_node) {/ / tail traverses to the end of the chain tail = tail- > next;} / / insert new- > next = tail- > next; tail- > next = new;} 1.5. Delete operation

The essence of deletion is to "skip" the node to be deleted, so we need to find the direct precursor node of the node to be deleted, and then let the next pointer of the direct precursor node point to its direct successor node, so as to "skip" the node to be deleted, and finally save its data field and release the node to complete the deletion.

Only the head deletion method is shown here.

Because the direct successor node of the header node is deleted, we no longer have to bother to find the direct precursor node of the node to be deleted.

One-way cyclic chain header deletion process

/ * * header deletion method: delete the node after the header node * p_head: pointer to the header pointer * elem: pointer to the saved data variable * / void delete_from_head (Node * * p_head, int * elem) {Node * head_node = * padded headers; / / header node if (head_node- > next = = head_node) {printf ("empty linked list, no elements can be deleted. \ n "); return;} Node * first_node = head_node- > next; / / head node: the next node of the header node * elem = first_node- > data; / / saves the data of the deleted node head_node- > next = first_node- > next; / / delete node free (first_node); / / release} 1.6. Ergodic operation

We can loop through the linked list one after another, and here is the code that prints the node 20 times:

/ * print nodes * / void output_20 (Node * head) {if (head- > next = = head) {printf ("empty linked list.\ n"); return;} Node * p = head- > next; for (int I = 0; I data);} p = p-> next;} printf ("\ n");} 2. Two-way linked list 2.1. structure

As the name implies, a two-way linked list has two directions, one pointing forward and the other pointing back. In this way, we make up for the defect that a node in a single linked list can only find its direct successor. As shown in the figure:

Bidirectional linked list

2.2. Realization idea

In order to achieve the effect of pointing before and after pointing, it is certainly not enough to rely on the next pointer, so we need to add another pointer-prev, which points to the direct precursor node of a node.

/ * Node structure of bidirectional linked list * / typedef struct _ Node {int data; / / data field struct _ Node * prev; / / pointer to the direct precursor node struct _ Node * next; / / pointer to the direct successor node} Node;2.3. Empty linked list and initialization

The empty list of the two-way linked list is shown in the figure:

Two-way empty linked list

To initialize such an empty linked list, you need to create a header node, and then leave the two pointer fields empty:

Node * create_node (int elem) {Node * new = (Node *) malloc (sizeof (Node)); new- > data = elem; new- > prev = NULL; new- > next = NULL; return new;} void init (Node * * p_head) {/ / create the header node Node * head_node = create_node (0); / / the header pointer points to the header node * p_head = head_node;} 2.4. Insert operation

Only the plug insertion method is shown here, and the process is as follows:

Two-way chain meter insertion process

The code is as follows:

/ * head insertion. The new node is the direct successor of the header node * p_head: pointer to the header pointer * elem: data of the new node * / void insert_at_head (Node * * p_head, int elem) {Node * new = create_node (elem); Node * head_node = * p_head / / header node if (head_node- > next! = NULL) {/ / is not empty linked list Node * first_node = head_node- > next; / / header node: the prev pointer of the next node / / header node points to the new node first_node- > prev = new; / / new node next pointer to the first node new- > next = first_node The prev pointer of the} / / new node points to the header node new- > prev = head_node; / / the next pointer of the header node points to the new node head_node- > next = new;} 2.5. Delete operation

Only the head deletion method is shown here. The following figure shows the process of deleting a two-way link header with two element nodes to an empty linked list:

Two-way chain header deletion process

The code is as follows:

/ * * header deletion * p_head: pointer to the header pointer * elem: pointer to the saved variable * / void delete_from_head (Node * * p_head, int * elem) {Node * head_node = * paired head; / / header node Node * first_node = head_node- > next / / the first node to be deleted: the next node of the header node if (head_node- > next = = NULL) {/ / empty printf ("empty linked list, no elements can be deleted. Return;} * elem = first_node- > data; / / Save data if (first_node- > next! = NULL) {first_node- > next- > prev = first_node- > prev;} first_node- > prev- > next = first_node- > next; free (first_node) Ergodic operation

With the next pointer domain, we can traverse all the way back; with the prev pointer domain, we can traverse all the way forward.

The code is no longer shown here.

At this point, the study of "what are the types of linked lists of data structures" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.

Views: 274

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report