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

The editor will share with you the example analysis of a single linked list in C++ 's data structure. I hope you will get something after reading this article. Let's discuss it together.

What is a linked list

Linked list is a kind of non-continuous and non-sequential storage structure in physical storage structure, and the logical order of data elements is realized through pointer links in the linked list.

From the graph, the chain structure is logically continuous, but not necessarily physically continuous.

The node in the display is usually applied from the heap.

The space applied for from the heap is divided according to a certain strategy. The space for two applications may be continuous or discontinuous, as shown in the sequence table.

Classification of linked lists

Linked lists can also be divided into many types.

1. Unidirectional or bidirectional

two。 Take the lead or not

3. Cyclic or acyclic

Our most commonly used list is headless unidirectional acyclic linked list and leading two-way cyclic linked list. In this article, we realize the addition, deletion, deletion and modification of headless unidirectional acyclic linked list.

Second, the realization of linked list

Basic node structure

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

Header file

/ / llist.h#pragma once#include # include typedef int SLTDateType;typedef struct SListNode {SLTDateType data; struct SListNode* next;} SListNode;// 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 deletion void SListPopBack (SListNode** pplist); / single-linked header deletion void SListPopFront (SListNode** pplist); / / single-linked list lookup SListNode* SListFind (SListNode* plist, SLTDateType x); / / single-linked list inserting XUnip after pos position / Analysis Why not insert before pos 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* plist)

Apply for a node dynamically

/ / dynamically apply for a node SListNode* BuySListNode (SLTDateType x) {SListNode* newnode = (SListNode*) malloc (sizeof (SListNode)); if (newnode = = NULL) / / Application failed {printf ("malloc fail\ n"); exit (- 1);} else {newnode- > data = x Newnode- > next = NULL;} return newnode;}

Single linked list printing

In a single node in the linked list, data stores data, next stores the address of the next node, and the next node can be accessed through next.

/ single linked list print void SListPrint (SListNode* plist) {SListNode* cur = plist; while (cur! = NULL) {printf ("% d->", cur- > data); cur = cur- > next;// visit the next node} printf ("NULL\ n");}

Single chain footer insert

The pointer to the address of the header node is passed here because it is possible to change the situation of the header node. If only * plist is passed in, it is equivalent to changing only the parameter, and the argument will not actually change. This problem can be solved through pplist.

/ / insert void SListPushBack (SListNode** pplist, SLTDateType x) {SListNode* newnode = BuySListNode (x); if (* pplist = = NULL) / / empty linked list {* pplist = newnode;} else {SListNode* tail = * pplist / / insert while (tail- > next! = NULL) {tail = tail- > next;} tail- > next = newnode;}} at the end of traversal

Tail deletion of single linked list

Traverse before and after, find empty and directly free (tail), and leave prev- > next empty.

/ / delete void SListPopBack (SListNode** pplist) {assert (pplist) of single linked list; if (* pplist = = NULL) / / empty linked list. There is no need to delete {return;} else {SListNode* prev = NULL; SListNode* tail = * pplist {while (tail- > next! = NULL) {prev = tail; tail = tail- > next;} free (tail); tail = NULL Prev- > next = NULL;}

Head insertion of single linked list

It's a little roundabout. Think about it.

/ void SListPushFront (SListNode** pplist, SLTDateType x) {assert (pplist) of single linked list; SListNode* newnode = BuySListNode (x); newnode- > next = * pplist; * pplist = newnode;}

Single chain header deletion

It's relatively simple

/ / single link header delete void SListPopFront (SListNode** pplist) {assert (pplist); if (* pplist = = NULL) / / the linked list is empty {return;} else {SListNode* next = (* pplist)-> next; free (* pplist); * pplist = next SListNode* SListFind (SListNode* plist, SLTDateType x) {SListNode* cur = plist; while (cur! = NULL) {if (cur- > data = x) {return cur;} cur = cur- > next;} retuen NULL;}

* single linked list inserts x after pos position

Why not insert before pos? because we are an one-way linked list, we need to search for pos from the beginning. If we insert before pos, we still need to find the address before pos to find pos. It is not friendly to the passed parameters, so we usually insert after.

/ the single linked list inserts xvoid SListInsertAfter (SListNode* pos, SLTDateType x) {assert (pos) after the pos position; SListNode* newnode = BuySListNode (x); newnode- > next = pos- > next; pos- > next = newnode;}

Why the value after deleting the pos position in a single linked list does not delete the pos position? as above, it is logically and unfriendly to pass parameters.

/ / single linked list value void SListEraseAfter (SListNode* pos) {assert (pos) after deleting pos position; SListNode* next = pos- > next; if (next) {pos- > next = next- > next; free (next); next = NULL;}}

The destruction of a single linked list is not like continuous deletion of the head of a sequential list, because the linked list is a scattered node and needs to be deleted one by one.

/ / destruction of single linked list void SListDestory (SListNode** pplist) {assert (* pplist); SListNode* cur = * pplist; while (cur) {SListNode* next = cur- > next; free (cur); cur = next;} * pplist = NULL } after reading this article, I believe you have some understanding of "example Analysis of single linked list in C++ data structure". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for reading!

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.