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

This article will explain in detail the use of the C language linked list. 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.

The concept and structure concept of linked list

The linked list is a kind of discontinuous and non-sequential storage structure in the physical storage structure, and the logical order of data elements is realized by the pointer link order in the linked list.

structure

Code

Struct Slist {int* a; struct Slist* next;}

Logical structure:

Physical structure:

Note:

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

These nodes are usually applied from the heap.

The space applied for from the heap is allocated according to a certain planning. The space of the two applications may be continuous, but the probability is discontinuous.

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. Unidirectional or bidirectional

① unidirectional

② bidirectional

two。 Take the lead or not

① takes the lead.

② doesn't take the lead.

3. Cyclic or non-cyclic

① cycle

② acyclic

Although there are so many linked lists, there are only two structures that are most commonly used in practice:

1. Headless unidirectional acyclic linked list

two。 Lead two-way circular linked list

1. 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.

two。 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.

Implementation of single linked list (headless)

Single linked list structure

Typedef int SLTDateType;typedef struct SListNode {SLTDateType data; struct SListNode* next;} SListNode

Functions required by a single linked list

/ / dynamically apply for a node SListNode* BuySListNode (SLTDateType x); / / single linked list print void SListPrint (SListNode* plist); / / single linked list footer insert void SListPushBack (SListNode** pplist, SLTDateType x); / / single linked list header insert void SListPushFront (SListNode** pplist, SLTDateType x); / / single linked list tail delete void SListPopBack (SListNode** pplist); / single linked list header delete void SListPopFront (SListNode** pplist); / / single linked list search SListNode* SListFind (SListNode* plist, SLTDateType x) / / the single linked list inserts x _ pos after the pos position / analyze why not insert it before the XML position? Void SListInsertAfter (SListNode* pos, SLTDateType x); / / the value of a single linked list after deleting the pos location / / analyze why not delete the pos location? Void SListEraseAfter (SListNode* pos); / / destruction of single linked list void SListDestory (SListNode** pplist)

Function realization

SListNode* BuySListNode (SLTDateType x) {SListNode* newnode = (SListNode*) malloc (sizeof (SListNode)); if (newnode = = NULL) {exit (- 1);} newnode- > data = x; return newnode;} void SListPrint (SListNode* plist) {if (plist = = NULL) {printf ("NULL\ n"); return } else {while (plist) {printf ("% d->", plist- > data); plist = plist- > next;} printf ("NULL\ n") }} void SListPushBack (SListNode** pplist, SLTDateType x) {SListNode* tail = * pplist; SListNode* newnode = BuySListNode (x); newnode- > next = NULL; if (tail = = NULL) {* pplist = newnode } else {while (tail- > next) {tail = tail- > next;} tail- > next = newnode;}} void SListPushFront (SListNode** pplist, SLTDateType x) {SListNode* newnode = BuySListNode (x); newnode- > next = * pplist; * pplist = newnode } void SListPopBack (SListNode** pplist) {assert (* pplist); SListNode* tail = * pplist; SListNode* Pretail = NULL; if (tail- > next = = NULL) {* pplist = NULL; return } else {while (tail- > next) {Pretail = tail; tail = tail- > next;} free (tail); tail = NULL; Pretail- > next = NULL } void SListPopFront (SListNode** pplist) {assert (* pplist); SListNode* front = * pplist; * pplist = front- > next; free (front); front = NULL;} SListNode* SListFind (SListNode* plist, SLTDateType x) {assert (plist); SListNode* pos = plist; while (pos & & pos- > data! = x) {pos = pos- > next } return pos;} void SListInsertAfter (SListNode* pos, SLTDateType x) {assert (pos); SListNode* newnode = BuySListNode (x); newnode- > next = pos- > next; pos- > next = newnode;} void SListEraseAfter (SListNode* pos) {assert (pos); assert (pos- > next); SListNode* node = pos- > next; pos- > next = node- > next; free (node) } void SListDestory (SListNode** pplist) {SListNode* node = * pplist; SListNode* PreNode = NULL; while (node) {PreNode = node- > next; free (node); node = PreNode;}} implementation of bidirectional linked lists

The structure of two-way linked list

SListNode* BuySListNode (SLTDateType x) {SListNode* newnode = (SListNode*) malloc (sizeof (SListNode)); if (newnode = = NULL) {exit (- 1);} newnode- > data = x; return newnode;} void SListPrint (SListNode* plist) {if (plist = = NULL) {printf ("NULL\ n"); return } else {while (plist) {printf ("% d->", plist- > data); plist = plist- > next;} printf ("NULL\ n") }} void SListPushBack (SListNode** pplist, SLTDateType x) {SListNode* tail = * pplist; SListNode* newnode = BuySListNode (x); newnode- > next = NULL; if (tail = = NULL) {* pplist = newnode } else {while (tail- > next) {tail = tail- > next;} tail- > next = newnode;}} void SListPushFront (SListNode** pplist, SLTDateType x) {SListNode* newnode = BuySListNode (x); newnode- > next = * pplist; * pplist = newnode } void SListPopBack (SListNode** pplist) {assert (* pplist); SListNode* tail = * pplist; SListNode* Pretail = NULL; if (tail- > next = = NULL) {* pplist = NULL; return } else {while (tail- > next) {Pretail = tail; tail = tail- > next;} free (tail); tail = NULL; Pretail- > next = NULL } void SListPopFront (SListNode** pplist) {assert (* pplist); SListNode* front = * pplist; * pplist = front- > next; free (front); front = NULL;} SListNode* SListFind (SListNode* plist, SLTDateType x) {assert (plist); SListNode* pos = plist; while (pos & & pos- > data! = x) {pos = pos- > next } return pos;} void SListInsertAfter (SListNode* pos, SLTDateType x) {assert (pos); SListNode* newnode = BuySListNode (x); newnode- > next = pos- > next; pos- > next = newnode;} void SListEraseAfter (SListNode* pos) {assert (pos); assert (pos- > next); SListNode* node = pos- > next; pos- > next = node- > next; free (node) } void SListDestory (SListNode** pplist) {SListNode* node = * pplist; SListNode* PreNode = NULL; while (node) {PreNode = node- > next; free (node); node = PreNode;}}

The function of two-way linked list

/ create linked list return header node LTNode* ListInit (); / Bidirectional linked list destroy void ListDestory (LTNode* phead); / Bidirectional linked list print void ListPrint (LTNode* phead); / Bidirectional linked list footer insert void ListPushBack (LTNode* phead, LTDateType x); / / Bidirectional linked list footer deletion void ListPopBack (LTNode* phead); / / Bidirectional linked list header insert void ListPushFront (LTNode* phead, LTDateType x); / / Bidirectional linked list header deletion void ListPopFront (LTNode* phead) / / two-way linked list looks up LTNode* ListFind (LTNode* phead, LTDateType x); / / two-way linked list inserts void ListInsert (LTNode* pos, LTDateType x) in front of pos; / / two-way linked list deletes node void ListErase (LTNode* pos) at pos location

Function realization

LTNode* ListInit () {/ / Sentinel head node LTNode* phead = (LTNode*) malloc (sizeof (LTNode)); if (phead = = NULL) {printf ("failed to open up space!!\ n"); exit (- 1);} phead- > next = phead; phead- > prev = phead; return phead } void ListDestory (LTNode* phead) {assert (phead); LTNode* cur = phead; LTNode* p = NULL; LTNode* tail = phead- > prev; while (cur! = tail) {p = cur; cur = cur- > next; free (p);} free (tail) } void ListPrint (LTNode* phead) {assert (phead); LTNode* front = phead- > next; while (front! = phead) {printf ("% d", front- > data); front = front- > next;} printf ("\ n");} void ListPushBack (LTNode* phead, LTDateType x) {assert (phead); LTNode* tail = phead- > prev LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)); if (newnode = = NULL) {printf ("failed to open up space!\ n"); exit (- 1);} newnode- > data = x; tail- > next = newnode; newnode- > prev = tail; newnode- > next = phead; phead- > prev = newnode } void ListPopBack (LTNode* phead) {assert (phead); assert (phead! = phead- > next); LTNode* tail = phead- > prev; LTNode* TailFront = tail- > prev; TailFront- > next = phead; phead- > prev = TailFront; free (tail);} void ListPushFront (LTNode* phead, LTDateType x) {assert (phead); LTNode* next = phead- > next LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)); if (newnode = = NULL) {printf ("failed to open up space!\ n"); exit (- 1);} newnode- > data = x; phead- > next = newnode; newnode- > prev = phead; newnode- > next = next; next- > prev = newnode } void ListPopFront (LTNode* phead) {assert (phead); assert (phead! = phead- > next); LTNode* head = phead- > next;// header node phead- > next = head- > next; head- > next- > prev = phead; free (head);} LTNode* ListFind (LTNode* phead, LTDateType x) {assert (phead); LTNode* cur = phead- > next While (cur! = phead) {if (cur- > data = = x) {return cur;} cur = cur- > next;} return NULL;} void ListInsert (LTNode* pos, LTDateType x) {assert (pos); LTNode* posPrev = pos- > prev LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)); if (newnode = = NULL) {printf ("failed to open up space!\ n"); exit (- 1);} newnode- > data = x; posPrev- > next = newnode; newnode- > prev = posPrev; newnode- > next = pos; pos- > prev = newnode } void ListErase (LTNode* pos) {assert (pos); LTNode* posPrev = pos- > prev; LTNode* posNext = pos- > next; posPrev- > next = posNext; posNext- > prev = posPrev; free (pos) } this is the end of the article on "what is the use of C language linked list". 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.