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

Most people do not understand the knowledge points of this article "what are the operations of the C language linked list", so the editor summarizes the following contents, detailed contents, clear steps, and has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "C language linked list operation" article.

Preface

Compilation tool: vs2019

Before we start: it is necessary to remind everyone to pay attention to the use of secondary pointers and why secondary pointers are used. My blog also has some related introductions. To put it simply, passing value parameters does not change the actual parameters, and address parameters change the formal parameters.

First, the introduction of linked list 1. What is a linked list

To put it simply, it is a table connected by a chain, and the links above also have a more formal introduction to the rules.

Compared with the sequential list, the most important feature of the linked list is that it does not require physical space continuity and insertion does not need to move a large amount of data.

How to contact each node?

In fact, it is not difficult to see from the above picture, just connect it with a pointer. Note that both the data field and the pointer field are needed: the pointer domain of the last element is NULL. The arrow above doesn't actually exist, just to look direct and visualized. So how do you show it? You can use the self-reference of the structure.

two。 Classification of linked lists

We did not talk about the types of linked lists before, but we can actually classify them according to different types. Because they are all based on single linked lists, we need to learn single linked lists well and deepen their learning.

2.1. According to the direction

Unidirectional / bidirectional linked list

2.2. Head node

Lead node / no lead node

2.3. Cyclic / acyclic

Second, the realization of linked list

Of course, the implementation of the linked list is inseparable from us to knock the code, which first needs to prepare our compilation environment, vs2019, at the same time, each time we finish writing a template, we have to test whether there is bug, so that we can find errors and debug, which will greatly reduce our workload.

1. Structural body

How should we express the linked list? In fact, from the above example, we already know that we need one place to store the data and another place to store the address of the next node. We can define it by structure. The specific code is as follows:

# include typedef int SLTDataType;typedef struct SListNode {SLTDataType data; struct SListNode* next;} SLTNode;2. Open up a node

Subsequent operations will frequently dynamically open up a header node, so we might as well encapsulate it into a function to facilitate later use. Of course, you don't have to write a function if you think you can write it yourself every time.

/ / create a new node SLTNode* BuySListNode (SLTDataType x) {SLTNode* newnode = (SLTNode*) malloc (sizeof (SLTNode)); newnode- > data = x; newnode- > next = NULL; return newnode;}

Note: the pointer field of the new node is set to empty!

3. Printing

Don't worry, let's try the water first and try to write the printed function ourselves.

In order to make it more vivid, I use-> to connect it every time I print, and at the same time, it ends with NULL.

Void SListPrint (SLTNode* phead) {SLTNode*cur = phead; while (cur! = NULL) {printf ("% d->", cur- > data); cur = cur- > next;} printf ("NULL\ n");} 4. Tail insertion

What is tail insertion? Literally, the new node is inserted at the end of the linked list.

In order to make it easier for everyone to understand, I found a picture on the Internet. Let's take a look.

Each insert a number is placed in the last position, at the same time, the pointer field of the last node is set to empty, the key is, how do we find the end node of the current linked list? As mentioned earlier, the pointer field of the last node is empty, which we can use as a breakthrough. Note: what do you do when the linked list is empty? Think about it. Let's not talk about it here, just look at our code.

/ / insert void SListPushBack (SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySListNode (x); if (* pphead = = NULL) {* pphead = newnode;} else {SLTNode* tail = * pphead; while (tail- > next! = NULL) {tail = tail- > next } tail- > next = newnode;}}

If you are careful, you should have noticed that we are all using secondary pointer pphead here.

Because if we use a first-level pointer and pass in the header pointer phead directly, the header pointer itself is a first-level pointer, and when we need to change the address that the pointer points to, the change will only take effect inside the function, and the phead pointer in the main function has not been changed. If you want to change it, you need a secondary pointer to operate it.

5. Head insertion

If there is a tail insertion, there will naturally be a head insertion. Compared with the tail insertion, the head insertion appears to be more simple. Why not put the new node in front of the head node directly ok?

/ / insert void SListPushFront (SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySListNode (x); newnode- > next = * pphead; * pphead = newnode;} 6. test

All right, at this point, we already have some functions. There's no hurry. Let's test the test results first.

Void TestSList1 () {SLTNode* plist = NULL; SListPushBack (& plist, 1); SListPushBack (& plist, 2); SListPushBack (& plist, 3); SListPushBack (& plist, 4); SListPushFront (& plist, 0); SListPrint (plist);} int main () {TestSList1 ();}

The running results are as follows:

We have to get into the habit of testing while writing code, which helps us to find our mistakes in time, and it is not easy to cause a lot of bug and we don't know what's wrong. Of course, in addition, we can also quickly and accurately find our own bug through debugging, which is what we need to develop. These are all points that we need to pay attention to.

All right, I won't explain it in so much detail as above. Let's just delete the head and tail.

7. Head deletion / tail deletion

If you have the head to insert the tail, you will naturally have the head to delete the tail. In fact, I don't know if you find that whether it is inserting or deleting, the operation on the head is relatively simple. Let's start with an appetizer, head delete: we can't delete it directly, oh, we have to record the next position of the head node, how to delete the head node directly, then it will be troublesome, it will cause wild pointer, and we can sort it out ourselves.

/ / head deletion void SListpopFront (SLTNode**pphead) {SLTNode* next = (* pphead)-> next; free (* pphead); * pphead = next;}

Tail deletion: speaking of tail deletion, we should pay more attention to it. It depends on the specific situation. Let's take a look at the code directly.

/ / delete void SListPopBack (SLTNode** pphead) {/ / the linked list is empty if (* pphead = = NULL) {return;} / / there is only one node else if ((* pphead)-> next = = NULL) {free (* pphead); * pphead = NULL } / / there is more than one node else {SLTNode* prev = NULL; SLTNode* tail = * pphead; while (tail- > next! = NULL) {prev = tail; tail = tail- > next } free (tail); prev- > next = NULL;}}

The key point of tail deletion is to find the last node, and the pointer field of the last node is empty.

1. When the linked list is empty, there is no need to delete

two。 The linked list has only one node, so it itself is the last node.

3. Multiple nodes will be treated as ok as usual, and what should be made clear should be made clear.

8. Find

Find this operation is actually relatively simple, it is said here for the later use, want to find a touch element, you can directly call the function, do not have to traverse again and again.

SLTNode* SListFind (SLTNode* phead, SLTDataType x) {SLTNode* cur = phead; while (cur) {if (cur- > data = = x) {return cur;} cur = cur- > next;} return NULL;} 9. Insert x in front of pos

In addition to the basic head-to-tail addition, we may also need to insert before and after a particular node, which requires us to play around and become more flexible.

Two core points:

Location of 1.pos

two。 Insert operation (some students here may have some doubts, in fact, as long as you know one thing, the location of the insertion is already known)

/ / insert xvoid SListInsert (SLTNode** pphead, SLTNode* pos, SLTDataType x) {if (pos = = * pphead) {SListPushFront (pphead,x);} else {SLTNode* newnode = BuySListNode (x); SLTNode* prev = * pphead before the pos While (prev- > next! = pos) {prev = prev- > next;} prev- > next = newnode; newnode- > next = pos;}} 10. Delete the value of the pos location

The key point is how to find the pos, skip it from the linked list, and then delete it.

/ / Delete the value of pos location void SListErase (SLTNode** pphead, SLTNode* pos) {if (pos = = * pphead) {SListpopFront (pphead);} else {SLTNode* prev = * pphead; while (prev- > next! = pos) {prev = prev- > next } prev- > next = pos- > next; free (pos);} third, main function Test

There's nothing to say about this. You can try it yourself.

The above is the content of this article on "what are the operations of the C language linked list?" I believe we all have a certain understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about the relevant knowledge, please follow 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.