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

This article introduces the knowledge of "how to implement single linked list operation in C language". 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!

1 the concept and structure of linked list

Concept: a linked list is a non-continuous, non-sequential storage structure on the physical storage structure, and the logical order of data elements is realized through the pointer link order in the linked list.

Note:

1. As can be seen from the above figure, the chain structure is logically continuous, but not necessarily physically continuous.

two。 In reality, nodes are usually applied from the heap.

3. The space for the application from above is allocated according to a certain strategy, and the space for the two applications may or may not be continuous.

2 classification of linked lists

In practice, the structure of linked lists is very diverse, and there are 8 kinds of linked list structures in the following situations:

1. one-way or two-way linked list

2. Take the lead or not lead the linked list

3. Cyclic or acyclic linked list

There are two most commonly used: headless unidirectional acyclic linked list and leading two-way cyclic linked list

Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more used as a sub-structure of other data structures, such as hash bucket, adjacency table of graph, and so on. In addition, this structure appears a lot in written interviews.

Lead two-way circular linked list: the structure is the most complex and is generally used to store data separately. The linked list data structure used in practice is to take the lead in two-way circular linked list. In addition, although the structure of this structure is complex, but the use of code implementation will find that the structure will bring a lot of advantages, but the implementation is simple, we will know after the code implementation.

3 implementation of the linked list headless + one-way + non-cyclic linked list addition and deletion modification to achieve the definition of the linked list typedef int SLTDataType;//typedef struct SListNode {int data;//val, the stored data, here it is assumed that the stored data is the int struct SListNode* next;// storage location of the next node} SListNode,SLN;3.2 linked list data print void SListPrint (SListNode* phead) {SListNode* cur = phead While (cur! = NULL) {printf ("% d->", cur- > data); cur = cur- > next;} printf ("NULL\ n");} 3.3 insert void SListPushBack (SListNode** pphead, SLTDataType x) {SListNode* newnode = BuySListNode (x) of linked list If (* pphead = = NULL) {* pphead = newnode;} else {/ / tail finding SListNode* tail = * pphead; while (tail- > next! = NULL) {tail = tail- > next } tail- > next = newnode;}}

In the process of finding the tail, you must not write the following code:

While (tailored null) {tail = tail- > next;} tail- > next = newnode

Of course, the above introduction is the situation of tail deletion.

Tail insertion is also similar. In the above code, when tailored null is not established, tail equals null, and then the assignment operation is performed. The line of code tail- > next = newnode is equivalent to the following code:

(* tail). Next, which is equivalent to dereferencing a null pointer, is actually an illegal access, and attempts to illegally modify data in unauthorized memory, which will inevitably lead to a program crash. And the address of the new node is not stored in the next that used to be the node.

This place needs to understand the fundamentals of traversing linked lists:

A linked list is a relatively static data space stored in the heap area. We traverse it by changing the data in the local variable tail in the stack area (that is, the address of each linked list node). The reason why we can access and modify node data through the tail variable is because the data type of tail is SListNode*, that is, a pointer to the node. The type of pointer determines the type of data that can be accessed by dereferencing the pointer, so * tail can access the data of nodes in the heap area and can modify it.

3.4 dynamic application for linked table spaces SListNode* BuySListNode (SLTDataType x) {SListNode* newnode = (SListNode*) malloc (sizeof (SListNode)); if (newnode = = NULL) {printf ("malloc fail\ n"); exit (- 1);} else {newnode- > data = x; newnode- > next = NULL } return newnode;} 3.5 head insert void SListPushFront (SListNode** pphead, SLTDataType x) {SListNode* newnode = BuySListNode (x); newnode- > next = * pphead; * pphead = newnode;} 3.6 tail deletion of linked list

There are three situations to consider:

Vbl.

One node

Multiple nodes

There are two ways to write:

The first kind:

Void SListPopBack (SListNode** pphead) {assert (pphead); if (* pphead = = NULL) / / empty linked list {return;} else if ((* pphead)-> next = = NULL) / / a node {free (* pphead); / / pphead is the value of plist * pphead = NULL } else// multiple nodes {SListNode* tail = * pphead; SListNode* prev = NULL;// Why should it be left empty? Because this place is equivalent to pointing to the node before the first node, this node does not exist and is set to empty while (tail- > next! = NULL) {prev = tail; tail = tail- > next;} free (tail); tail = NULL Prev- > next = NULL;}}

In this way, there is no problem when there is only one node.

The second kind:

Void SListPopBack (SListNode** pphead) {assert (pphead); if (* pphead = = NULL) / / empty linked list {return;} else if ((* pphead)-> next = = NULL) / / a node {free (* pphead); / / pphead is the value of plist * pphead = NULL } else// multiple nodes {SListNode* tail = * pphead; while (tail- > next- > next! = NULL) {tail = tail- > next;} free (tail- > next); / / release tail node tail- > next = NULL / / set the next of the new tail node to NULL}}

Void SListPopFront (SListNode** pphead) {assert (pphead); if (* pphead = = NULL) / / empty list {return;} else// non-empty list {SListNode* next = (* pphead)-> next / / next as a temporary variable stores the address free (* pphead) of the second node stored by next in the deleted node; * pphead = next;}}

3.8 pre-insert void SListInsertBefore (SListNode** pphead, SListNode* pos,SLTDataType x) {assert (pphead) anywhere in the linked list; if (* pphead = = pos) / / pos is the first node, equivalent to headinserting {SListPushFront (pphead, x);} else {SListNode* prev = * pphead While (prev- > next! = pos) {prev = prev- > next;} SListNode* newnode = BuySListNode (x); prev- > next = newnode; newnode- > next = pos;}}

3.9 Post-insertion at any location of the linked list

There are two ways to implement:

Method 1:

Void SListInsertAfter (SListNode* pos, SLTDataType x) {assert (pos); SListNode* newnode = BuySListNode (x); newnode- > next = pos- > next; pos- > next = newnode; / / the order of these two lines of code is fixed and can only be changed.

The figure shows:

Method 2:

Void SListInsertAfter (SListNode* pos, SLTDataType x) {assert (pos); SListNode* next = pos- > next; SListNode* newnode = BuySListNode (x); newnode- > next = next; pos- > next = newnode; / / these two lines of code can be changed at will, and who comes first and then does not affect the final result}

The figure shows:

3.10 delete void SListErase (SListNode** pphead, SListNode* pos) {assert (pphead); assert (pos); if (pos = * pphead) / / when pos is a header node {SListPopFront (pphead);} else// {SListNode* prev = * pphead when pos is a non-header node While (prev- > next! = pos) {prev = prev- > next;} prev- > next = pos- > next; free (pos); pos = NULL;}}

The figure shows:

3.11 pre-delete void SListEraseBefore (SListNode** pphead, SListNode* pos) / / pos at any location of the linked list is any location {assert (pphead); assert (pos); if (pos== * pphead) {return;} else if (pos== (* pphead)-> next) {SListPopFront (pphead) } else {SListNode* prev = * the previous location while (prev- > next- > next! = pos) used by pphead;//prev to store the previous location of the pos {prev = prev- > next;} SListNode* next = prev- > next / / Save the address of the previous node of pos prev- > next = prev- > next- > next;// connect the two nodes of prev and pos to free (next); / / delete the previous node of pos}}

3.12 delete void SListEraseAfter (SListNode* pos) {assert (pos) anywhere in the linked list; SListNode* next = pos- > next; if (next = = NULL) / / when pos is the last node {return;} else {pos- > next = next- > next; free (next) Next = NULL;}}

The figure shows:

3.13 destruction of the linked list void SListDestory (SListNode** pphead) {assert (pphead); SListNode* cur = * pphead; SListNode* next = * pphead;// is used to store the address of the next node in cur, because after free (cur), the data in memory pointed to by the cur pointer may already be called garbled, that is, while (cur) {next = cur- > next can no longer be used normally. Free (cur); cur = next;} * pphead = NULL;} "how to operate a single linked list in C language" ends 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.