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

This article will explain in detail how to use the single linked list in C language. 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. Single 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 achieved through the pointer link order in the linked list.

The closest thing between a linked list and our lives is the train. )

2. The realization of single linked list

Next, let's realize the addition, deletion and modification of the single linked list.

Creation of header file # pragma once # include # include # include typedef int SLDataType; / / creation of linked list typedef struct SListNode {SLDataType data;//val struct SListNode* next;// stores the address of the next node} SListNode,SLN; / / print linked list void SListPrint (SListNode* phead); / / insert void SListPushBack (SListNode** pphead, SLDataType x); / / insert void SListPushFront (SListNode** pphead, SLDataType x); / / delete void SListPopBack (SListNode** pphead) / / delete void SListPopFront (SListNode** pphead); / / find SListNode* SListFind (SListNode* phead, SLDataType x); / / insert void SListInsert (SListNode** pphead, SListNode* pos, SLDataType x) before pos location; / / delete pos location void SListErase (SListNode** pphead, SListNode* pos); / / insert void SlistInserAfter (SListNode* pos, SLDataType x) after pos location; / / delete the value void SlistEraseAfter (SListNode* pos) after pos / / destroy void SListDestroy (SListNode** pphead); implementation of the function (1) print linked list void SListPrint (SListNode* phead) {assert (phead); SListNode* cur = phead; if (cur = = NULL) {printf ("SList is NULL\ n");} while (cur! = NULL) {printf ("% d->", cur- > data) Cur = cur- > next;} printf ("NULL\ n");} (2) dynamically apply for nodes

Apply for a data x node dynamically.

SListNode* BuySList (SLDataType 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) tail insertion

Void SListPushBack (SListNode** pphead, SLDataType x) {assert (pphead); SListNode* newnode = BuySList (x); if (* pphead = = NULL) {* pphead = newnode;} else {/ / tail finding SListNode* tail = * pphead While (tail- > next! = NULL) {tail = tail- > next;} / / find the tail tail- > next = newnode;}} (4)

Void SListPushFront (SListNode** pphead, SLDataType x) {assert (pphead); SListNode* newnode = BuySList (x); newnode- > next = * pphead; * pphead = newnode;} (5) tail deletion

Void SListPopBack (SListNode** pphead) {assert (pphead); / / when the linked list has only one node, if (* pphead = = NULL) {printf ("SListNode is NULL\ n"); return } / / when the linked list has only one node, else if ((* pphead)-> next = = NULL) {free (* pphead); * pphead = NULL;} / / when the linked list has multiple nodes, else {SListNode* tail = * pphead While (tail- > next- > next! = NULL) {tail = tail- > next;} free (tail- > next); tail- > next = NULL;}} (6) header deletion

Void SListPopFront (SListNode** pphead) {assert (pphead); if (* pphead = = NULL) {printf ("SList is NULL\ n"); return;} else {SListNode* next = (* pphead)-> next; free (* pphead); * pphead = next }} (7) find SListNode* SListFind (SListNode* phead, SLDataType x) {assert (phead); SListNode* cur = phead; while (cur! = NULL) {if (cur- > data = = x) {return cur } / / if it is not found, go down cur = cur- > next;} / / after the loop is completed and not found, it means there is no such value in the linked list return NULL;} (8) insert before pos

Void SListInsert (SListNode** pphead, SListNode* pos, SLDataType x) {assert (pphead); assert (pos); / / pos is the first location if (pos = = * pphead) {SListPushFront (pphead, x);} / / pos is not the first location else {SListNode* prev = * pphead While (prev- > next! = pos) {prev = prev- > next;} SListNode* newnode = BuySList (x); prev- > next = newnode; newnode- > next = pos;}} (9) Delete pos

Void SListErase (SListNode** pphead, SListNode* pos) {assert (pphead); assert (pos); / / 1. Empty header node if (* pphead = = NULL) {printf ("SList is NULL\ n"); return } / / 2. Delete the first node else if (pos = = * pphead) {SListPopFront (pphead);} / / 3, other nodes else {SListNode* prev = * pphead While (prev- > next! = pos) {prev = prev- > next;} prev- > next = pos- > next; free (pos); pos = NULL;}} (10) insert after pos

Instead of inserting before pos, inserting after pos does not need a header node, no matter where the pos is located.

Void SListInsertAfter (SListNode* pos, SLDataType x) {assert (pos); SListNode* newnode = BuySList (x); SListNode* next = pos- > next; pos- > next = newnode; newnode- > next = next; / / the following way can also be / * SListNode* newnode = BuySList (x); newnode- > next = pos- > next; pos- > next = newnode;*/} (11) delete after pos

Void SListEraseAfter (SListNode* pos) {assert (pos); SListNode* next = pos- > next; if (next) {pos- > next = next- > next; free (next); next = NULL;} (12) remember to destroy void SListDestroy (SListNode** pphead) {assert (pphead) SListNode* cur = * pphead; while (cur) {SListNode* next = cur- > next; free (cur); cur = next;} * pphead = NULL;} 3, functional testing # include "SList.h" void test1 () {SListNode* slist = NULL / / Test tail insert SListPushBack (& slist, 1); SListPushBack (& slist, 2); SListPushBack (& slist, 3); SListPushFront (& slist, 5); SListPushFront (& slist, 4); SListPrint (slist); / / Test head insert SListPushFront (& slist, 5); SListPushFront (& slist, 4); SListPrint (slist) / / delete SListPopBack (& slist); SListPopBack (& slist); SListPrint (slist); / / delete SListPopFront (& slist); SListPrint (slist); / / Test find SListNode* ret1 = SListFind (slist, 5) Printf ("% d\ n", ret1- > data); / * SListNode* ret2 = SListFind (slist, 2); printf ("% d\ n", ret2- > data); * / / pos forward test SListNode* pos = SListFind (slist, 1); if (pos) {SListInsert (& slist,pos,3);} SListPrint (slist) Pos = SListFind (slist, 1); if (pos) {SListInsert (& slist, pos, 10);} SListPrint (slist); / / Delete pos test pos = SListFind (slist, 10); if (pos) {SListErase (& slist, pos);} SListPrint (slist) / Test insert pos = SListFind (slist, 3) after pos; if (pos) {SListInsertAfter (pos, 6);} SListPrint (slist); pos = SListFind (slist, 1); if (pos) {SListInsertAfter (pos, 8);} SListPrint (slist) / / Test the value pos = SListFind (slist, 1) after pos is deleted; if (pos) {SListEraseAfter (pos);} SListPrint (slist);} int main () {test1 (); return 0;}

Running result:

This is the end of the implementation of the single linked list, if you want to go further, please follow the follow-up-single linked list OJ, so that you are no longer confused!

This is the end of the article on "how to use a single linked list in C language". I hope the above content can be helpful 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.