[Data structure] Addition, deletion, checking and modification of one-way linked list and insertion and deletion of specified pos position

Table of Contents

The concept and structure of one-way linked list

tail plug

Head plug

tail delete

?edit

Header deletion

Find

Insert forward at pos position

Insert after pos position

delete pos position

Delete the last position of pos

Summarize

code

The concept and structure of one-way linked list

Concept: A linked list is a
Physical storage structure is non-contiguous
, non-sequential storage structure, data elements
Logical order
It is linked through pointer in the linked list
implemented sequentially.

The structure of a one-way linked list:

Note:

As can be seen from the above figure, the chain structure is logically continuous, but not necessarily physically continuous.
In reality, nodes are generally applied from the heap.
The space requested from the heap is allocated according to a certain strategy. The space applied for twice may be continuous or discontinuous.

Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more often used as a substructure of other data structures, such as hash buckets, adjacency lists of graphs, etc. In addition, this structure appears a lot in written interviews.

Tail insert

There are two situations for tail insertion:

There is no linked list at the beginning: When there is no linked list at the beginning, newnode is directly assigned to *pphead, and the plist is changed through the secondary pointer.
There is a linked list at the beginning: When there is a linked list at the beginning, create a structure pointer tail to find the last node, and then assign newnode to the next of the last node.

Head plug

Header insertion is divided into two situations, there is a linked list at the beginning and there is no linked list at the beginning, but the two situations do not need to be classified. First assign *pphead or plist to newnode->next, and then connect newnode to *pphead.

Tail Delete

Tail deletion is considered in two situations:

There is only one node: assign null value to *pphead
More than one node: After determining the tail node tail, pass the previous node tailprev of tail, perform tailprev->next=NULL and assign a null valueor directly find the penultimate one through tail->next->next node, and then assign a null value to tail->next.

Head deletion does not need to be specific. The next of the first node, that is, the address of the second node, is directly assigned to *pphead through the transfer of newnode.

Search

Create a structure pointer cur, traverse the linked list to find the node of cur->data==x, and return cur after finding it to facilitate subsequent modification functions.

(No modification is required, so what is passed into the function is a first-level pointer)

Insert before pos

Consider two situations:

When pos is the first node, it is equivalent to head insertion, just call the head insertion function.
When pos is not the first node, insert newnode in front of pos through prev, the previous node of pos.

Insert after pos position

Insert after pos, first assign pos->next to newnode->next, connect newnode to d3, then assign newnode to pos->next, and connect to d2.

Note: You cannot change the positions of the two statements, otherwise they will form a loop and print in a loop.

Delete pos location

There are two situations:

pos is at the first node position, just call the header deletion function directly.
pos is not at the first node position. Through prev, the previous node of pos, assign pos->next to prev->next to achieve the effect of deleting the pos node.

Delete the last position of pos

To delete the last position of pos, you need to first check whether pos->next is a null value. If it is a null value, it will be returned directly. If pos->next is not null, assign it to posNext, and then assign posNext->next to pos->next. To delete the posNext node, you can later release the posNext node with free(posNext), and then assign a null value to it with posNext=NULL.

Headless deletion of pos location

If the head node is not given, you can first exchange the content through pos->data=posNext->data, then delete the next node posNext of pos, and replace pos with posNext to achieve the same effect as deleting pos.

However, the disadvantage of this method is that when pos itself is the tail node, the replacement method cannot be used through the next node posNext.

code

Summary

Among the many implementations of one-way linked lists above, many are not practical. When a large number of header plugs are required to be deleted, it will be more efficient to use one-way linked lists.

code

SList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>




typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;

//typedef struct SListNode SLTNode;

//Print
void SLTPrint(SLTNode*phead);


SLTNode* BuySListNode(SLTDataType x);


//Tail insertion
void SLTPushBack(SLTNode** pphead, SLTDataType x);


//Delete tail
void SLTPopBack(SLTNode** pphead);


//Head plug
void SLTPushBack(SLTNode** pphead, SLTDataType);


//Delete header
void SLTPopFront(SLTNode** pphead);


//Find
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);


//Insert before pos position
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);


//Insert after pos position
void SLTInsertAfter(SLTNode* pos, SLTDataType x);


//Delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos);


//Delete the last position of pos
void SLTEraseAfter(SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"


//Print
void SLTPrint(SLTNode*phead)
{
SLTNode* cur = phead;
//while (cur != NULL)
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\\
");
}



SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}

newnode->data = x;
newnode->next = NULL;

return newnode;

}

End insertion phead is the formal parameter of plist //There is a linked list at the beginning
//void SLTPushBack(SLTNode* phead, SLTDataType x)
//{
// SLTNode* newnode = BuySListNode(x);
// SLTNode* tail = phead;
// while (tail->next != NULL)
// {
// tail = tail->next;
// }
// tail->next = newnode;
//}

//Tail insert //Including no linked list at the beginning
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
//Change the pointer of the structure, so use a secondary pointer
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
//To change the structure, use the pointer of the structure.
tail->next = newnode;
}
}



//Head plug
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);

newnode->next = *pphead;
*pphead = newnode;
}



//Delete tail
void SLTPopBack(SLTNode** pphead)
{
//1.Empty
assert(*pphead);
//2. A node
//3. More than one node
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
\t\t//method 1.
SLTNode* tailPrev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
\t\t
Method 2.
//SLTNode* tail = *pphead;
//while (tail->next->next)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
}

}



//Delete header
void SLTPopFront(SLTNode** pphead)
{
\t//null
assert(*pphead);

\t//non empty
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}


//Find if there is a number x, find it and return a pointer to the number
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}


//Insert before pos position
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);

if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}


//Insert after pos position
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);

SLTNode* newnode = BuySListNode(x);
\t
//The following two sentences cannot exchange positions, otherwise they will form a loop.
newnode->next = pos->next;
pos->next = newnode;
}


//Delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pos);

if (*pphead == pos)
{
SLTPopFront(pphead);
}
//else if (pos->next == NULL)
//{
//SLTPopBack(pphead);
//}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//free(prev->next);//Don’t free, otherwise this node will be gone
prev->next = pos->next;
}
}



//Delete the position after pos
void SLTEraseAfter(SLTNode* pos)
{
//
assert(pos);

//Check whether pos is the tail node
//assert(pos->next);//Violent detection
if (pos->next == NULL)//Gentle detection
{
return NULL;
}

SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;

}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"


void TestSList1()
{
int n;
printf("Please enter the length of the linked list:");
scanf("%d", & amp;n);
printf("\\
Please enter the value of each node in turn:");
SLTNode* plist = NULL;

for (size_t i = 0; i < n; i + + )
{
int val;
scanf("%d", & amp;val);
SLTNode* newnode = BuySListNode(val);


//Head plug
newnode->next = plist;
plist = newnode;

}

SLTPrint(plist);
SLTPushBack( & amp;plist, 1000);
SLTPrint(plist);

}

void TestSList2()
{
SLTNode* plist = NULL;
\t
//Tail insertion
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

//Head plug
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);
}


void TestSList3()
{
SLTNode* plist = NULL;

//Tail insertion
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

Head plug
//SLTPushFront( & amp;plist, 10);
//SLTPushFront( & amp;plist, 20);
//SLTPushFront( & amp;plist, 30);
//SLTPushFront( & amp;plist, 40);
//SLTPrint(plist);

//Delete tail
SLTPopBack( & amp;plist);
//SLTPopBack( & amp;plist);
//SLTPopBack( & amp;plist);
//SLTPopBack( & amp;plist);
//SLTPopBack( & amp;plist);
SLTPrint(plist);


}



void TestSList4()
{
SLTNode* plist = NULL;

//Tail insertion
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

//Head plug
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);




//Delete header
SLTPopFront( & amp;plist);
SLTPrint(plist);
}


void TestSList5()
{
SLTNode* plist = NULL;

//Tail insertion
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

//Head plug
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);


//Find
SLTNode* pos = SLTFind(plist, 40);
if(pos)
{
pos->data *= 10;
}
SLTPrint(plist);
}

void TestSList6()
{
SLTNode* plist = NULL;

//Tail insertion
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

//Head plug
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);

//Insert before pos position
int x;
scanf("%d", & amp;x);
SLTNode* pos = SLTFind(plist, x);
if(pos)
{
SLTInsert( & amp;plist, pos, x * 10);
}
SLTPrint(plist);
}


void TestSList7()
{
SLTNode* plist = NULL;

//Tail insertion
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

//Head plug
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);

//Insert after pos position
int x;
scanf("%d", & amp;x);
SLTNode* pos = SLTFind(plist, x);
if(pos)
{
SLTInsertAfter(pos, x * 10);
}
SLTPrint(plist);
}


void TestSList8()
{
SLTNode* plist = NULL;

//Tail insertion
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

//Head plug
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);

//Delete pos position
int x;
scanf("%d", & amp;x);
SLTNode* pos = SLTFind(plist, x);
if(pos)
{
SLTErase( & amp;plist, pos);
pos = NULL;
}
SLTPrint(plist);
}



void TestSList9()
{
SLTNode* plist = NULL;

//Tail insert
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPushBack( & amp;plist, 5);
SLTPrint(plist);

//Head plug
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);

//Delete the position after pos
int x;
scanf("%d", & amp;x);
SLTNode* pos = SLTFind(plist, x);
if(pos)
{
SLTEraseAfter(pos);
pos = NULL;
}
SLTPrint(plist);
}








void PrintSList(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\\
");
}




int main()
{
\t
//TestSList1();
// Head plug Tail plug
//TestSList2();
// tail delete
//TestSList3();
//Delete header
//TestSList4();
// Find
//TestSList5();
// Insert pos position forward
//TestSList7();
// Insert after pos position
//TestSList8();
// Delete pos position
TestSList9();
//Delete the last position of pos
//TestSList10();

return 0;
}

The concept and structure of one-way linked list

Tail insert

Head plug

Tail Delete

Header Delete

Search

Insert before pos

Insert after pos position

Delete pos location

Delete the last position of pos

Headless deletion of pos location

Summary

code