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

Editor to share with you how to achieve C++ single linked list, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's go to understand it!

The concept and structure of the implementation of single linked list (from entry to proficiency)

Concept: a linked list is a physical storage structure that is discontinuous and non-sequential.

The logical order of data elements is realized by the pointer linking order in the linked list.

The figure shows:

Note:

The linked list structure is logically continuous, but physically (memory) is not necessarily continuous

Linked list nodes are all applied on the heap, and the application space is allocated according to a certain policy.

Type of structure

Linked lists have a variety of structures: one-way / two-way, lead\ no lead, circular\ non-circular

In fact, the most commonly used are: headless unidirectional non-cyclic linked list, leading two-way cyclic linked list

Realization of linked list

Note: what is implemented here is a headless unidirectional acyclic linked list

Add, delete, query and modify API / dynamically apply for a node SListNode* BuySListNode (SLTDateType x); / single linked list print void SListPrint (SListNode* plist); / / single linked list tail 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 link header delete void SListPopFront (SListNode** pplist) / / single linked list looks up SListNode* SListFind (SListNode* plist, SLTDateType x); / / single linked list inserts xvoid SListInsertAfter (SListNode* pos, SLTDateType x) after pos position; / / single linked list deletes the value void SListEraseAfter (SListNode* pos) after pos position; node structure creates typedef int SLTDateType;typedef struct SListNode {SLTDateType data; struct SListNode* next;} SListNode; node opening

For linked lists, we need to open up every space needed. Here, we encapsulate it into a function, which is convenient for subsequent calls to use directly (opening up and assigning values at the same time).

Reference Code:

/ / the linked list node opens SLTNode* BuySListNode (SLTDateType x) {/ / dynamically allocates a node SLTNode* newnode = (SLTNode*) malloc (sizeof (SLTNode)); if (newnode = = NULL) {/ / if the assignment fails, it prints an error message and ends the process perror ("newnode fail:"); exit (- 1) } / / if successful, assign newnode- > data = x; newnode- > next = NULL; / / return the node address for subsequent operations return newnode;} data printing

Note:

1. For unheaded linked lists, printing data does not need to change the address of the first node of the linked list (so just pass the linked list pointer)

two。 Loop through the linked list and point to the next node every time you print the data

3. End the loop by relying on the address domain of the tail node to be NULL

Code:

/ / linked list data printing void SListPrint (SLTNode* phead) / / first-level pointer receiving first-level pointer (printing does not need to change the contents of the pointer itself) {/ / create an addressing pointer SLTNode* cur = phead While (curving null) / / there are nodes {/ / print data and point to the next node printf ("% d->", cur- > data); cur = cur- > next;} / / finally print null pointer printf ("NULL\ n"); return;} linked list tail insert data

To insert data at the end, you need to traverse to find the tail node of the linked list

For an unheaded linked list, the trailing insert data may also be the address of the element at the beginning of the linked list (when the linked list is empty), and the content of the linked list pointer needs to be modified (therefore, the address of the linked list pointer needs to be passed in).

Insert data to open up nodes

Code:

/ / linked list tail insert data void SListPushBack (SLTNode** pphead, SLTDateType x) / / second-level pointer receives first-level pointer (tail insertion exists and needs to change the contents of the linked list pointer itself) {/ / avoid incoming errors (direct error report is easy to find the wrong location) assert (pphead); / / receive the address of the new node SLTNode* newnode=BuySListNode (x) / / header node is empty if (* pphead = = NULL) {* pphead = newnode;} else {/ / find tail node SLTNode* tail = * pphead / / create an addressing node / / in the case of two or more nodes while (tail- > next! = NULL) {/ / points to the next node tail = tail- > next;} / / found tail- > next = newnode } return;}

Note the role of assert in the code:

The address that is correctly passed into the linked list pointer will not be empty

However, if the linked list pointer is passed abnormally (not the address of the linked list pointer) and the linked list pointer is empty, an error will occur (the assert error will tell the error location), telling the programmer that the address of the linked list pointer should be passed.

Head deletion

Note:

The address domain of the current node needs to be saved before deletion (that is, the space address of the next node is saved in case of loss)

Delete the data before deleting the current linked list header node, that is, you need to modify the contents of the linked list pointer (so you need to pass in the address of the linked list pointer)

Modify the contents of the linked list pointer after deletion to point to the new header node

Cannot be deleted if the linked list is empty (saving the next node address will cause illegal access)

Code:

/ / data deleted before the linked list void SListPopFront (SLTNode** pphead) {/ / avoid incoming errors (directly report the error to facilitate finding the wrong location) assert (pphead); / / if the linked list is empty, if (* pphead = = NULL) {return;} / / the creation pointer saves the second node address SLTNode* next = (* pphead)-> next / / release the current header node space free (* pphead); / / update header node data * pphead = next; return;} linked list data lookup

Note:

Loop through the linked list when looking up

There is no need to modify the contents of the linked list pointer for finding data, so you only need to pass in the linked list pointer

Return the node address when it is found, otherwise return NULL

Code:

/ / linked list data lookup SLTNode* SListFind (SLTNode* phead, SLTDateType x) {/ / create addressing pointer SLTNode* cur = phead; while (curvilinear null) {if (cur- > data = = x) / / find data matching node {return cur / / return the node address (benefit: for later search or modification)} else {/ / find the next node cur = cur- > next;}} / / No data matching node return NULL was found } linked list pos position pre-insertion data

Note:

If you want to insert data in the pos position, you not only need to find the pos location, but also need to record the previous node location of the pos.

If the incoming pos is NULL, an error is reported.

Before modification, the address domain of the node is changed into a new node, and the address domain of the new node is changed to pos, which is a successful pos location forward data.

Loop through the linked list to find the pos location. If you don't find the pos location, do nothing.

Code:

/ / it is difficult to insert the pos position forward (and after the pos position, simple point) void SListInsert (SLTNode** pphead, SLTNode* pos, SLTDateType x) {/ / avoid incoming errors (direct error reporting is easy to find the wrong location) assert (pphead); assert (pos); SLTNode* newnode = BuySListNode (x) / / if (* pphead = = pos) {newnode- > next = * pphead; * pphead = newnode;} else {/ / create addressing pointer SLTNode* cur = * pphead While (cur! = NULL) {if (cur- > next extents = pos) {cur = cur- > next / / find the next node} else / / find the corresponding space {cur- > next = newnode; newnode- > next = pos; return / / end the search (otherwise it will be inserted all the time, resulting in an endless loop) / / if nothing is found, nothing will be done. Return;} the linked list pos position inserts the data.

Note:

If you insert the back, you don't have to pay attention to whether it is the first node.

And you don't have to find the location of the front node through traversal.

After interpolation, first change the new node address domain to pos and then change the pos address domain to the new node address.

Ps: be sure to modify the address domain of the linked node in order to avoid address loss

Code:

/ the linked list pos position is inserted back into void SListInsert (SLTNode** pphead, SLTNode* pos, SLTDateType x) {SLTNode* newnode = BuySListNode (x); newnode- > next = pos- > next; pos- > next = newnode; return;} linked list pos location data deletion

Note:

Considering the deletion of the first node, the content of the linked list pointer may be modified, so the address of the linked list pointer needs to be passed in.

For deleting a node, you need to save the address of the next node in the pos location, release the pos location, and then change the address domain of the node in front of the pos location to the address of the node behind the pos location. This is the successful deletion of the pos location node.

Loop to find the pos location, and do nothing if you don't find it.

Reference Code:

/ / linked list pos location deletion void SListErase (SLTNode** pphead, SLTNode* pos) {/ / avoid incoming errors (direct error reporting is easy to find the wrong location) assert (pphead); assert (pos); / / the header node matches if (* pphead = = pos) {* pphead = (* pphead)-> next; free (pos) } else {/ / create the addressing pointer SLTNode* cur = * pphead; while (cur! = NULL) {if (cur- > next! = pos) {cur = cur- > next / / find the next node} else / / find the corresponding space {SLTNode* next = cur- > next- > next; free (cur- > next); cur- > next = next Return;// ends searching} / / if nothing is found, do nothing return;} linked list node release

Note:

For dynamically opened memory space, be sure to release it after use (to avoid memory leaks).

Because the linked list nodes are opened one by one, the same release needs to be released one by one.

Loop traversal needs to save the address of the next node before releasing the current node to avoid address loss and unable to release.

After the release, you also need to set the linked list pointer to null (avoid using wild pointers)

Reference Code:

/ / the linked list node releases void SListDestory (SLTNode** pphead) {/ / avoid incoming errors (direct error reporting is easy to find the wrong location) assert (pphead); / / ergodic release SLTNode* cur = * pphead; while (cur) {/ / Save the next address SLTNode* next = cur- > next; free (cur) Cur = next;} / / empty * pphead = NULL; return;} the advantages and disadvantages of distinguishing linked lists from sequential lists

Advantages

Apply for space on demand (reasonable use of space)

High insertion efficiency (no need to move data like a sequential table)

Shortcoming

Random access is not supported (cannot be accessed directly by subscript)

Advantages and disadvantages of sequential tables

Advantages

Support random access (some algorithms require structures to support random access: binary search, fast scheduling, etc.)

Shortcoming

Space for expansion is consumed (space fragmentation and space waste)

Inserting data requires moving data and consuming data.

The above is all the contents of the article "how to achieve a single linked list in C++". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to 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.