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

This article will explain in detail what the C language linked list is like. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

1. Overview of linked lists 1.1 concept and structure of linked lists

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 achieved through the pointer link order in the linked list.

1.2 Classification of linked lists

In practice, the structure of linked list is very diverse, and there are 8 kinds of linked list structure in the following cases.

Unidirectional or bidirectional

Take the lead or not

Cyclic or non-cyclic

Although there are so many linked list structures, two structures are the most commonly used in practice.

Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more as a substructure of other data structures, such as hash buckets, adjacency tables of graphs, 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, we will find that the structure will bring a lot of advantages after using the code to implement it, and the implementation is simple. Later, we will know when the code implements it.

two。 Realization of one-way linked list

Unidirectional linked list structure

2.1 SList.h (summary of header files, declaration of functions) # pragma once#include#include#include#includetypedef int SLTDataType;typedef struct SListNode {address of the next node} SListNode;void SListPrint (SListNode* phead) of int data;// data struct SListNode* next;//; / / print SListNode* BuySListNode (SLTDataType x); / / create a new node void SListPushBack (SListNode** pphead, SLTDataType x); / / insert void SListPushFront (SListNode** pphead, SLTDataType x) / / insert void SListPopBack (SListNode** pphead); / / delete void SListPopFront (SListNode** pphead); / / delete SListNode* SListFind (SListNode* phead, SLTDataType x); / / find void SListInsert (SListNode** pphead, SListNode* pos, SLTDataType x); / / insert void SListInsertAfter (SListNode* pos, SLTDataType x) before pos location; / / insert void SListErase (SListNode** pphead, SListNode* pos) after pos location; / / delete pos location void SListEraseAfter (SListNode* pos) / / delete void SListDestroy (SListNode** pphead) after pos; / / destroy 2.2 SList.c (specific implementation logic of the function) 2.2.1 print linked list / / print void SListPrint (SListNode* phead) {/ / assert (phead); / / No need to assert, empty linked list can also print SListNode* cur = phead While (cur! = NULL) {printf ("% d->", cur- > data); cur = cur- > next;} printf ("NULL\ n");} / / test.cvoid TestSList1 () {SListNode* slist;// structure pointer, address for storage node SListNode* N1 = (SListNode*) malloc (sizeof (SListNode)) SListNode* N2 = (SListNode*) malloc (sizeof (SListNode)); SListNode* n3 = (SListNode*) malloc (sizeof (SListNode)); N1-> data = 1; N2-> data = 2; N2-> data = 3; N1-> next = N2; N2-> next = N2; N2-> next = NULL; slist = N1; SListPrint (slist);}

2.2.2 create a new node (serving other functions) / / create a new node 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;} 2.2.3 insertion of linked list

/ / insert void SListPushBack (SListNode** pphead,SLTDataType x) / / will change the argument slist by passing the secondary pointer {assert (pphead); / / even if the linked list is empty, its secondary pointer is not null SListNode* newnode = BuySListNode (x); if (* pphead = = NULL) {* pphead = newnode } else {/ / traversal tail finding SListNode* tail = * pphead; while (tail- > next! = NULL) {tail = tail- > next;} tail- > next = newnode;}} void TestSList2 () {SListNode* slist = NULL For (int I = 0; I

< 6; i++) { SListPushBack(&slist,i); } SListPrint(slist);} 2.2.4 链表头插 //头插void SListPushFront(SListNode** pphead, SLTDataType x){ assert(pphead);//就算链表是空，它的二级指针也不为空 SListNode* newnode = BuySListNode(x); newnode->

Next = * pphead; * pphead = newnode;} void TestSList2 () {SListNode* slist = NULL; for (int I = 0; I

< 6; i++) { SListPushFront(&slist,i); } SListPrint(slist);} 2.2.5 链表尾删 方法1（用两个指针，分别找最后一个和倒数第二个）： 方法2（直接找倒数第二个）： //尾删void SListPopBack(SListNode** pphead)//如果只有一个节点但还要尾删，就会改变实参slist，建议传二级指针{ assert(pphead);//就算链表是空，它的二级指针也不为空 //三种情况： //1.空 //2.一个节点 //3.多个节点 if (*pphead == NULL) { return; } else if ((*pphead)->

Next = = NULL) / / priority, remember to put parentheses {free (* pphead); * pphead = NULL;} / / the first way to write (find the last one and the penultimate second with two pointers) else {SListNode* prev = NULL / / find the penultimate element to point it to NULL SListNode* tail = * pphead;// tail-finding while (tail- > next! = NULL) {prev = tail; tail = tail- > next;} free (tail); tail = NULL / / if you drop the habitual free, leave it empty prev- > next = NULL;} / / method 2 (find the penultimate one directly) / / else / / {/ / SListNode* tail = * pphead / / find the tail / / while (tail- > next- > next! = NULL) / / {/ / tail = tail- > next; / /} / / free (tail- > next); / / tail- > next = NULL; / /}} 2.2.6 chain header deletion

/ / head deletion void SListPopFront (SListNode** pphead) {assert (pphead); / / 1. Empty / / 2. Non-empty if (* pphead = = NULL) {return;} else {SListNode* next = (* pphead)-> next; free (* pphead); * pphead = next;} 2.2.7 find node / / find SListNode* SListFind (SListNode* phead, SLTDataType x) {SListNode* cur = phead While (phead! = NULL) {if (cur- > data = = x) {return cur;} cur = cur- > next;} return NULL;} 2.2.8 insert before pos position

/ / insert (usually used with find) void SListInsert (SListNode** pphead, SListNode* pos, SLTDataType x) {assert (pphead); assert (pos) before the pos position / / indirectly detect whether the linked list is empty, because the empty linked list cannot find pos / / 1.pos is the first node (header) / / 2.pos is not the first node if (pos = * pphead) {SListPushFront (pphead, x);} else {SListNode* prev = * pphead While (prev- > next! = pos) {prev = prev- > next;} SListNode* newnode = BuySListNode (x); prev- > next = newnode; newnode- > next = pos;} 2.2.9 insert after pos position

Method 1: two pointers: connect pos and newnode first or newnode and next first

Method 2: there is only one pointer, be sure to connect newnode and the next through pos, and then connect pos and newnode, otherwise the address of the next will not be found.

/ insert void SListInsertAfter (SListNode* pos, SLTDataType x) {assert (pos); SListNode* newnode = BuySListNode (x) after the pos position; SListNode* next = pos- > next; newnode- > next = next;// order does not matter pos- > next = newnode; / / or do not define next / / newnode- > next = pos- > next;// pos- > next = newnode / / order must be set, otherwise} 2.2.10 delete pos location will not be found

/ delete pos location void SListErase (SListNode** pphead, SListNode* pos) {assert (pphead); assert (pos); if (pos = = * pphead) {SListPopFront (pphead);} else {SListNode* prev = * pphead While (prev- > next! = pos) {prev = prev- > next;} prev- > next = pos- > next; free (pos); pos = NULL;// good habits} 2.2.11 position after pos deletion

/ / position void SListEraseAfter (SListNode* pos) {assert (pos) after pos deletion; SListNode* next = pos- > next; if (next) / / prevent pos from being the last element {pos- > next = next- > next; free (next); next = NULL;} 2.2.12 linked list destruction

Find it one by one, destroy it one by one, and finally empty the slist.

/ / destroy void SListDestroy (SListNode** pphead) {assert (pphead); SListNode* cur = * pphead; while (cur) {SListNode* next = cur- > next; free (cur); cur = next;} * pphead = NULL;}

This is the end of the article on "what the C language linked list is like". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

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.