Although the order has convenient subscript random access ( Because it's a continuous physical space ) Advantages of , But it also has some defects ,

as :

1. insert data , Capacity expansion when space is insufficient , However, capacity expansion has performance consumption

2. Insert or delete data in the head or middle position , Need to move data , Low efficiency

3. Space expansion is too large , There may be some space occupation , Waste space , Unable to apply for and release space on demand

Because of these defects , The linked list was born

So what is a linked list ?

concept : Linked list is a kind of discontinuous physical storage structure , Non sequential storage structure , The logical order of data elements is through the pointer chain in the linked list Sequential implementation .

As can be seen from the above figure :

1. The chain structure is logically continuous , But not necessarily continuous physically

2. In reality, nodes are generally applied from the heap

3. Space requested from heap , It is allocated according to a certain strategy , Space for two applications may be continuous , It may also be discontinuous

Linked list classification :

One way or two-way

  Take the lead or not

Cyclic or acyclic

  Common structures :

Headless one-way acyclic linked list

Simple structure , Generally, it is not used to store data alone . In practice, it is more as a substructure of other data structures , Such as hash bucket , Adjacency table of graph, etc . In addition, this structure appears a lot in the written interview .

Lead two-way circular linked list

The most complex structure
, Generally used for separate data , Linked list data structure used in practice , Are two-way circular linked lists . In addition, although the whole structure is complex , However, after using code implementation, you will find that it will bring many advantages , The implementation is simpler

  Here is a headless one-way acyclic linked list

Interfaces to be completed :
// Create node SListNode* BuySListNode(SListDateType x); // Print linked list void
PrintSList(SListNode* phead); // Tail insertion void SListPushBack(SListNode** pphead,
SListDateType x); // Head insert void SListPushFornt(SListNode** pphead, SListDateType
x); // Tail deletion void SListPopBack(SListNode** pphead); // Header deletion void
SListPopFront(SListNode** pphead); // Find the specified value SListNode* SListFind(SListNode*
phead, SListDateType x); // Insert before the specified position void SListInsertBefore(SListNode** pphead,
SListNode* pos, SListDateType x); // Insert after specified position void SListInsertAfter(SListNode*
pos, SListDateType x); // Delete specified location void SListErase(SListNode** pphead, SListNode*
pos); // Node after deleting the specified location void SListEraseAfter(SListNode* pos); // Destroy linked list void
SListDestroy(SListNode** pphead);
notes : Headless one-way acyclic linked list needs to understand the parameters passed by the secondary pointer , And the empty and nonexistent linked list and the empty and nonexistent sequential list

Defined structure node :
typedef int SListDateType;// Flexible and convenient type transformation typedef struct SListNode { int date;// data
struct SListNode* next;// Address of the next node }SListNode;
Create a new node :

You need to pay attention here , Due to the characteristics of linked list , We manipulate structure pointers , Not the operation structure , This is different from the sequence table , So what we need to do is not initialization , Instead, write an interface function to create a new node , When the node is created, put the data into
// Create a new node SListNode* BuySListNode(SListDateType x) { // Open up a dynamic memory SListNode*
newnode = (SListNode*)malloc(sizeof(SListNode)); // Development failure termination procedure if (newnode ==
NULL) { printf("Fail\n"); exit(-1); } else { newnode->date = x;// take x Add new development date
newnode->next = NULL;// I don't know where to point after opening up space , Empty first } // Will open up space to return return newnode; }
Tail insertion node :

You need to pay attention here

Due to tail interpolation, the first node may be changed ( The linked list is empty ), Since the first node will be changed , You should send the address , The pointer passed from the first node of the list should be a pointer , So we should use the secondary pointer to receive

Although the linked list pointed to by the passed first level pointer may be empty ( That is, the first level pointer is null ), This just means that the linked list is empty , But there is this linked list , however pphead As the secondary pointer should point to the primary pointer passed , therefore pphead The address of this first level pointer is stored in , Since there is this first level pointer , Then the first level pointer has an address to store the first level pointer , therefore pphead Cannot be empty , Otherwise, the linked list is not empty , That's because the linked list doesn't exist , This is an illegal situation

When the linked list is empty, it needs to be discussed separately , Directly assign a value to the newly created node

Other information is as follows :

void SListPushBack(SListNode** pphead, SListDateType x) {
assert(pphead);//pphead Cannot be empty // pass x And receive the created node SListNode* newnode = BuySListNode(x);
// If the message is NULL, Description is an empty linked list , The open space is directly assigned to the empty linked list if (*pphead == NULL) {
// When the end of the linked list is empty , Assign a value to the newly opened node for the first time , be *pphead The first node is always stored *pphead = newnode; }
// If it's not NULL, Description is not an empty linked list , The original linked list has nodes else { // Find the tail , Find the head node to the tail node SListNode* tail = *pphead;
// When tail Medium next be equal to NULL, It indicates that it is the node at the end while (tail->next != NULL) {
// Tail finding node , Constantly give the address of the next node to tail, Until the address of the next node is NULL tail = tail->next; }
// When tail->next==NULL, Assign a value to the newly opened node , replace NULL tail->next = newnode; } }
Print linked list :

Because it is printing , The first node will not be changed , Therefore, value transmission is adopted , That is, pass the value of the first level pointer , Just use the first level pointer to receive
void PrintSList(SListNode* phead) { SListNode* cur = phead;// Assign the head node to the current node
// Use existing node traversal ,cur->next==NULL Is the sign of the end of the linked list while (cur != NULL) { printf("%d->",
cur->date); cur = cur->next; } printf("NULL\n"); }
Header insertion node :

Here, the head insertion is the same as the tail insertion ,

The insertion is as follows :

void SListPushFornt(SListNode** pphead, SListDateType x) {
assert(pphead);//pphead Cannot be empty // Receive new nodes created SListNode* newnode = BuySListNode(x);
// Assign the address of the first node to the address of the new node next newnode->next = *pphead; // Put the address of the new node on the first node *pphead = newnode; }
Tail delete node :

Tail deletion is the same as the previous tail insertion , Also note that the linked list is empty and there is only one node in the linked list , We have to discuss the situation separately , because prev Cannot be empty , So discuss it according to the situation

No node can be deleted

Only one node is deleted directly

  Other information is as follows :

void SListPopBack(SListNode** pphead) { assert(pphead);// Linked list must exist // Empty linked list returns directly if
(*pphead == NULL) { return; } // The linked list has only one node , Direct release else if ((*pphead)->next == NULL)
{ free(*pphead); *pphead = NULL; } // The linked list is larger than one node else { // Double pointer method is adopted SListNode* tail
= *pphead; SListNode* prev = NULL; // Tail finding while (tail->next != NULL) {
// Keep the address of the previous node prev = tail; tail = tail->next; } // Release tail node and empty free(tail); tail =
NULL; // Of the previous node next Empty prev->next = NULL; /* Double dereference while (tail->next->next !=
NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; */ } }
Header delete node :

Same as tail insertion , Also, the linked list cannot be empty , It is empty and cannot be deleted

void SListPopFront(SListNode** pphead) { assert(pphead);// Linked list must exist // The linked list is empty if
(*pphead == NULL) { return; } // Linked list is not empty else { // Address of the second node SListNode* next =
(*pphead)->next; // Release the first node free(*pphead); // Point to the second node *pphead = next; } }
Find the specified value :

Because it's a search , Do not change the first node , So pass value , Receive with primary pointer
SListNode* SListFind(SListNode* phead, SListDateType x) { // Traversing the current pointer of the linked list
SListNode* cur = phead; // lookup x while (cur) { if (cur->date == x) { return cur; }
cur = cur->next; } // can't find return NULL; }
Insert before the specified position :

  Same as tail insertion , The first node may change , And the position to be inserted cannot be empty , It needs to be discussed according to the situation ,

When the inserted node is the first node , It's just a head plug , because prev Cannot be empty , So discuss it separately

When the inserted node is not the first one :

void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x) {
assert(pphead);// Linked list must exist assert(pos);// The inserted position cannot be empty // When the inserted node is the first if (pos ==
*pphead) { SListPushFornt(pphead, x); } // When the inserted node is not the first one else { // Traverse from the first node
SListNode* prev = *pphead; // lookup pos position while (prev->next != pos) { prev =
prev->next; } // Create a new node SListNode* newnode = BuySListNode(x); // insert prev->next =
newnode; newnode->next = pos; } }
Insert after specified position :

This situation cannot be changed in the first place , So just transfer the value , Receive with primary pointer , And the position to be inserted cannot be empty

void SListInsertAfter(SListNode* pos, SListDateType x) {
assert(pos);// The inserted position cannot be empty // Create node SListNode* newnode = BuySListNode(x); // insert
newnode->next = pos->next; pos->next = newnode; }
Delete the node at the specified location :

It is possible to delete the first node , Secondary pointer receiving , Location cannot be empty

It needs to be discussed on a case by case basis :

When the deleted node is the first node , That is, header deletion , Need to be discussed separately , because prev Cannot be empty

Other information is as follows :

void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead);// Linked list must exist
assert(pos);// The search location cannot be empty // When the deleted location is the first node if (*pphead == pos) {
SListPopFront(pphead); } // When the deleted location is not the first node else { // Traverse from the first node SListNode* prev
= *pphead; // lookup pos while (prev->next != pos) { prev = prev->next; } // Delete Vertex
prev->next = pos->next; free(pos); pos = NULL; } }
Delete the node after the specified location :

It is impossible to delete the first node , So pass value , Primary pointer reception , Location cannot be empty

void SListEraseAfter(SListNode* pos) { assert(pos);//pos Cannot be empty // Store nodes to be deleted
SListNode* next = pos->next; //pos Not the last node , that is next Cannot be empty if (next) { // Delete Vertex
pos->next = next->next; free(next); next = NULL; } }
Destroy linked list :

The first node will be changed , Transmission address , Secondary pointer receiving
void SListDestroy(SListNode** pphead) { assert(pphead);// Existence of linked list SListNode* cur
= *pphead; while (cur) { // Point to the next node to be deleted SListNode* next = cur->next; // delete
free(cur); // Point to the next node , Just to the last node cur Empty cur = next; } }
thus it can be seen , singly linked list :

Suitable for head plug deletion

Not suitable for insertion and deletion at the tail or somewhere in the middle

Technology
©2019-2020 Toolsou All rights reserved,
【C++ Must see for entry 】C++ from 0 reach 1 Introductory programming axios Interceptor packaging and use Spring Boot Interview must ask : Automatic configuration principle VMware 16 install centos 7 Detailed tutorial C Language data structure - Sequence table delete duplicates V2.0.0 The 12th Blue Bridge Cup c++b Group personal problem solving On sending data from serial port single chip microcomputer to upper computer centos7 install RabbitMqjava Polymorphic array of opencv-python Fourier transform and inverse transform