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

Today, the editor will share with you the relevant knowledge points about how to achieve dynamic linked lists in C language. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

The linked list is a non-continuous and non-sequential storage structure on the physical storage unit, and the logical order of data elements is realized by the pointer link order in the linked list. The linked list consists of a series of nodes (each element in the linked list is called a node), and the node can be generated dynamically at run time. Each node consists of two parts: one is the data field in which the data elements are stored, and the other is the pointer domain in which the address of the next node is stored.

The structure definition has been declared by the function

Node structure definition

Typedef struct SNode {void * pdata; / / stores data, which can be the next node address of any type of struct SNode* next; / / node} SNode;typedef struct SNode* SLink; / / defines a linked list

Function declaration

/ / create a linked list SLink create_slink (); / / initialize a linked list void init_slink (SLink * link); / / determine whether the linked list is empty bool is_empty (SLink link); / / get the number of linked list stored size_t size (SLink link); / / insert element elements stored in pdata, a total of size bytes int insert (SLink link,size_t index,void * pdata,size_t size) / / get the node element of the specified subscript and return its address void * get (SLink link,size_t index); / delete a node int remove_data (SLink link,size_t index); / / reverse linked list SLink reverse (SLink link); / / clear linked list void clear (SLink link); / / destroy linked list void destroy (SLink link) / / traversing the linked list (completing the requirements required by the user through the function pointer) void foreach (SLink link,void (* func) (const void*)); / / finding a node void* find by value (SLink link,void * pdata,int (* compare) (const void*, const void*)); / / deleting all nodes that need to be deleted by value (SLink link,void * pdata,int (* compare) (const void*, const void*)) / / sort the linked list by bubbling sort void sort (SLink link,int (* compare) (const void *, const void *)); function to create a linked list

First of all, dynamic linked lists generally have a header node (it is not necessary, but the header node can make the following algorithm easier). This header node does not store data, but only stores the address of the first node (the node where the data is stored, also known as the first node), so we can make the node's pdata null.

The specific implementation is as follows:

First of all, we write a function implementation to generate a node, so that as long as we insert the node in the future, we can use this static method; this function we need to pass the address of the data, the size of the data (so that we can copy the data into the node), and the address of the next node

Static SNode * create_node (void * pdata,size_t size,SNode * next) {SNode * node = malloc (sizeof (SNode)); / / first use malloc to apply for a dynamic memory if (pdata = = NULL) {/ / if the incoming data address is null node- > pdata = NULL;} else {node- > pdata = malloc (size) / / otherwise, apply for a piece of dynamic memory with the size of size, memcpy (node- > pdata,pdata,size); / / copy the data pointed to by pdata to node- > pdata via memcpy, and copy size bytes} node- > next = next; / / Let the node point to the next node return node; / / return this node}

So with the static method above, it's easy to create a linked list or insert a node.

Because we started out with an empty linked list, that is, there is only one header node, we do not pass data.

SLink create_slink () {/ / return create_node (NULL,0,NULL); SNode * head = create_node (NULL,0,NULL); return head;}

In addition to creating a linked list, we can initialize a linked list (that is, define a node in other functions) and then initialize it.

Here we pass the address of a linked list. The linked list type is SNode *, and its address is SNode * *, because only by passing the address of an element can we change the value of the element in a function (the parameter passed between functions is a value assignment).

Void init_slink (SLink * link) {* link = create_node (NULL,0,NULL); / / also call the static method of the generating node} to determine whether the linked list is empty.

The so-called empty linked list means that there is only one header node, which does not store data, but only records the address of the first node. If the address of the first node is empty, then this is an empty linked list.

Bool is_empty (SLink link) {return link- > next = = NULL;} gets the number of nodes in the linked list

The node in the linked list refers to the node that stores the element, so it cannot contain the header node. We just need to traverse this node. If the next address (next) of a node is empty, then this node is the tail node.

} size_t size (SLink link) {size_t cnt = 0; / / used to record the number of nodes SNode * node = link- > next; / / while (node! = NULL) {/ / traverse the linked list + + cnt; node = node- > next;} return cnt;} insert an element at a specific location

Insert an element in the location of index, that is, we need to change the location of index to our newly inserted node.

Inserting a node in a linked list is not as complicated as in a linear table (array). To insert an element in a linear table, we need to move all the elements behind the inserted node back, which adds a lot of burden, but inserting a node (or deleting a node) in the linked list only needs to change the pointer of the nearby node to OK, so the operation becomes much easier. Let's explain in detail how to insert a node.

First of all, it must be to find the location where we are inserted.

As shown in the figure above, we need to insert a node where the subscript is 3, so what should we do?

Yes, we can find a way to get the node with subscript 2, then disconnect the connection between 2 and 3, and insert the new node into it.

As shown in the figure, we point the next of the 2 nodes to the newly inserted new node and the next of the new to the nodes of 3, so the connection between 2 and 3 is broken smoothly, and our insertion is complete.

So let's take a look at the code.

The first thing, of course, is to get the previous node where we need to insert, that is, the 2 nodes in the figure above.

Static SNode * get_prev_node (SLink link,size_t index) {/ / get the previous node SNode * node = link;//. For example, if we insert a node at the beginning of a linked list, we insert a node behind the header node / / We insert a node at the end of the chain list when size_t I is inserted when node- > next is null. } return node; / / the return value here may be null. For example, when node is the trailing node, its node- > next is null}.

Insert operation

Int insert (SLink link,size_t index,void * pdata,size_t size) {if (pdata = = NULL) {/ / if no data is passed in, insert failed return-1;} SNode * prev = get_prev_node (link,index) If (prev = = NULL) {/ / gets the previous node of the insertion location, and cannot insert data when it is Null, return-1;} SNode * node = create_node (pdata,size,prev- > next) / / call the static method of generating node to generate a node, / / and pass in pdata,size. As shown in the figure above, the next of the newly inserted node points to the next prev- > next = node of the previous node prev. / / redirect prev- > next to the newly inserted node, so the insertion is complete / / the link between the two lines next to the new node / / prev- > next = create_node (pdata,size,prev- > next); return 0;}

About inserting data at the beginning or end of a linked list

It is actually very simple here, that is, the problem that the first node of the newly inserted node is the head node or the tail node. You can write about it yourself.

Gets the element of the node of the specified subscript

This operation is relatively simple, you only need to traverse the subscript when the conditions are met, and there is no difficulty.

Void * get (SLink link,size_t index) {SNode * node = link- > next; / / here we cannot start traversing from the header node, because the header node does not store data, so we can only traverse size_t I from the first node; for } return node- > pdata; / / you can delete a node by traversing and returning the address of this data.

Delete can be said to be the reverse of insertion.

For example, in the image above, we need to delete the node 3, so what should we do? In fact, it is easier than inserting. We just need to point the next of 2 to the next of the node to be deleted (that is, the next of 3), and release the 3 nodes, releasing the data inside and OK.

First, we can also write a static method to delete a node.

Static void remove_node (SNode * prev) {/ / the prev here is the previous node of the node to be deleted SNode * node = prev- > next; / / record the deleted node SNode * next = node- > next; / / record the next node free (node- > pdata) of the deleted node; free (node); prev- > next = next;}

Then delete the operation of the node

Int remove_data (SLink link,size_t index) {SNode * prev = get_prev_node (link,index); / / get the previous node if of the deleted node (link = = NULL | | prev = = NULL | | prev- > next = = NULL) {/ / if the linked list does not exist or the previous node of the deleted node does not exist or the deleted node does not exist, then delete failed return-1 } remove_node (prev); return 0;}

You can also write to delete the first node or the end node.

List reverse order

The so-called reverse order of linked lists is to reverse the storage order of linked lists.

For example, in the picture above, what is the reverse result?

Let's take a look, that is, let the next of 5 nodes point to 4 nodes, 4 point to 3, point to 2, point to 2, point to 1, point to NULL, and then point the header node to 5, and then complete the reverse order, as shown in the following figure.

So how do we implement it in code?

SLink reverse (SLink link) {if (link==NULL | | link- > next = = NULL | | link- > next- > next = = NULL) {/ / if the linked list does not exist or only has a header node or only one node, then we do not need to reverse the operation return link;} SNode * prev = link- > next / / record the first node SNode * curr = link- > next- > next;// record the second node SNode * next; while (curr! = NULL) {/ / continue to execute next = curr- > next;// record the next node of curr curr- > next = prev as long as the current node is not empty / / Let the pointer point backwards, that is, the pointer of the current node points to the previous node prev = curr; / / and then move back to curr = next } / / finally, there are two lines that are not connected / / that is, the next of the previous first node (that is, node 1 in the figure above) should point to null, and the first node should be changed to prev, that is, the node 5 link- > next- > next = NULL; / / link- > next = prev; return link;} list in the above figure.

It only takes one traversal to clear the linked list, release the data in the node, and then release the node.

Void clear (SLink link) {SNode * node = link- > next; / / traversing while (node! = NULL) {SNode * next = node- > next; / / record the next node free (node- > pdata) of the node that needs to be released; free (node); node = next } link- > next = NULL;} destruction of linked list

This is more simple, just clear the node inside and release the header node.

Traversal of void destroy (SLink link) {clear (link); free (link);} linked lists

The traversal of the linked list is needless to say, we just need to traverse from the first node and pass the node's data to the function pointer, which is more flexible and traverses all the way to null.

Void foreach (SLink link,void (* func) (const void *)) {SNode * node = link- > next; / / traverse for (; node! = NULL; node = node- > next) {func (node- > pdata) from the first node / / pass the data of the node to the func function, / / then it is up to the user to decide what to do with the data, not just to print out the data / / the advantage is that the processing of the data is more flexible}} to find nodes by specific elements

We also start traversing from the first node and compare the data in the first node. If we find the same data, we return the address of the data.

Void* find (SLink link,void * pdata,int (* compare) (const void*, const void*)) {SNode * node = link- > next; / / find for (; node! = NULL; node = node- > next) {if (node- > pdata,pdata) = 0) {/ / if the data of this node and the data with search are equal return node- > pdata / / then return the address of this data}} return NULL; / / if not found, return null}

The compare here is also a function pointer, and by the same token, it is up to the user to decide what to find, not just to find a particular element.

For example, in the structure of a student information, we can look it up by student number, name, age, class, and so on, to make it more flexible to use.

For example, if I write a search function for you, I will search according to the student's student number.

Int compare (const void* v1 Const void* v2) {Stu * stu1 = (Stu *) v1; Stu * stu2 = (Stu *) v2; return v1-> no-v2- > no;} delete all eligible nodes according to certain conditions

In fact, this deletion operation is more or less the same as the above operation of deleting a specific subscript node, which is to find the previous node of the node to be deleted, and then carry out the operation. After finding it here, there is no rush to exit, but to continue to look down until the entire linked list is found and all eligible nodes are deleted.

Int remove_all (SLink link,void * pdata,int (* compare) (const void *, const void *)) {SNode * prev = link; int cnt = 0; while (prev- > next! = NULL) {if (compare (prev- > next- > pdata,pdata) = = 0) {/ / find the previous node remove_node (prev) of the node to be deleted / / delete the number of cnt++; / / deleted on this node + +} else {prev = prev- > next; / / otherwise, if you don't find it, you will continue to look for}} return cnt > 0permal1;} the sort of linked list.

I choose bubble sorting here. If you want to see more sorting methods, you can also take a look at my previous blog. I have written a total of 12 sorting methods.

The order here is almost exactly the same as what I wrote before, so I won't say any more. The only thing I need to explain is the application of function pointers. For example, we can choose to sort students' student numbers. Students' names, grades, height, age and so on can be sorted in ascending or descending order.

Void sort (SLink link,int (* compare) (const void *, const void *) {if (link- > next = = NULL | | link- > next- > next = = NULL) {return;} size_t I; SNode * tail = NULL; SNode * n = link- > next; for (; n! = NULL;n = n-> next) {SNode * node Bool swap = false; for (node = link- > next;node- > next! = tail;node = node- > next) {SNode * prev = node; SNode * next = prev- > next If (compare (prev- > pdata,next- > pdata) > 0) {/ / the sorting method selected here or the element swap (prev- > pdata,next- > pdata); swap = true }} tail = node; if (! swap) {break;}

Let me write another way to sort the names of students in ascending order.

Int cmopare (const void* v1 Const void* v2) {Stu * S1 = (Stu *) v1; Stu * S2 = (Stu *) v2; return strcmp (S1-> name,s2- > name);} that's all about the article "how C language implements dynamic linked lists". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to 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.