Headless singly linked list with complete test program

Headless singly linked list

All nodes of the headless singly linked list store valid information
Headless single-linked list is relative to the headed single-linked list. In some functions involving changing the head node, a secondary pointer needs to be passed

Header file list.h

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SLTNode {<!-- -->
SLTDataType data;
struct SLTNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType x);
void Destroy_Method1(SLTNode** pphead);
void Destroy_Method2(SLTNode** pphead);

//check
SLTNode* FindBySerialNumber(SLTNode* phead, int n);
SLTNode* FindByContent(SLTNode* phead, SLTDataType x);
//change
void ModefyNodeBySerialNumber(SLTNode* phead, int n, SLTDataType x);
void ModifyNodeByContent(SLTNode* phead, SLTDataType x1, SLTDataType x2);
//increase
void PushFront(SLTNode** pphead, SLTDataType x);
void PushBack(SLTNode** pphead, SLTDataType x);

void InsertFrontBySerialNumber(SLTNode** pphead, int n, SLTDataType x);
void InsertFrontByAddress(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void InsertFrontByContent(SLTNode** pphead, SLTDataType x1, SLTDataType x2);

void InsertBackBySerialNumber(SLTNode** pphead, int n, SLTDataType x);
void InsertBackByAddress(SLTNode* pos, SLTDataType x);
void InsertBackByContent(SLTNode* pphead, SLTDataType x1, SLTDataType x2);
//delete
void PopFront(SLTNode** pphead);
void PopBack(SLTNode** pphead);

void DeleteFrontNode(SLTNode** pphead, SLTNode* pos);
void DeleteNode(SLTNode** pphead, SLTNode* pos);
void DeleteAfterNode(SLTNode* pos);

//test
SLTNode* testPush_Front_Back();
void testInsertFront();
void testInsertBack();
void testPop();

function implements list.c

Auxiliary operation function

Print linked list function

//Auxiliary operation (print linked list, dynamically apply for nodes)
// print linked list
void SLTPrint(SLTNode* phead) {<!-- -->
SLTNode* cur = phead;
while (cur) {<!-- -->//Enter the loop when the pointer is not empty
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\\
");
}

create node, destroy linked list function

Create node function

//2. Dynamically apply for a node
SLTNode* BuySLTNode(SLTDataType x) {<!-- -->
//1. Use malloc to dynamically apply for a node space
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//2. Determine whether the application is successful, and exit the program directly if the application fails
if (newnode == NULL) {<!-- -->
perror("mallocfail");
exit(-1);
}
//3. Assign x to the data field of the node, and NULL to the pointer field
newnode->data = x;
newnode->next = NULL;
//4. Return the address of the node
return newnode;
}

Destroy linked list function

Method 1: Keep the head node first, delete the latter, and finally delete the head node

//Destroy the linked list
//Method 1: Keep the head node first, delete the latter, and finally delete the head node
void Destroy_Method1(SLTNode** pphead) {<!-- -->
// linked list is empty, no need to delete
assert(pphead);
//First delete the back, and finally delete the head
while ((*pphead)->next) {<!-- -->
SLTNode* next = (*pphead)->next;
(*pphead)->next = next->next;
free(next);
}
free(*pphead);
}

Method 2: Delete from the beginning to the end, the value of the head node is always updated

//Method 2: Delete from the beginning to the end, the value of the head node is always updated
void Destroy_Method2(SLTNode** pphead) {<!-- -->
assert(pphead);
SLTNode* cur = *pphead;
while (cur) {<!-- -->
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}

Add, delete, check and modify-check

1. Find nodes according to serial number

serial number: serial number

// 3.1 Find the node according to the serial number
SLTNode* FindBySerialNumber(SLTNode* phead, int n) {<!-- -->
SLTNode* cur = phead;
for (int i = 1;i < n;i ++ ) {<!-- -->
cur = cur->next;
//If the searched node does not exist (beyond the range of the linked list), return a null pointer
if (cur == NULL) {<!-- -->
return NULL;
}
}
return cur;
}

2. Find nodes based on content

//3.2 Find nodes based on content
SLTNode* FindByContent(SLTNode* phead, SLTDataType x) {<!-- -->
SLTNode* cur = phead;
while (cur) {<!-- -->
if (cur->data == x) {<!-- -->
return cur;
}
cur = cur->next;
}
//cannot find return null pointer
return NULL;
}

Add, delete, check and modify–Change

1. Change the data in the node (find the changed node by serial number)

//4.1 Change the data in the node (find the changed node through the serial number)
void ModefyNodeBySerialNumber(SLTNode* phead, int n, SLTDataType x) {<!-- -->
SLTNode* cur = FindBySerialNumber(phead, n);
cur->data = x;
}

2. Change the data in the node (find the changed node through the content)

//4.2 Change the data in the node (find the changed node through the content)
void ModifyNodeByContent(SLTNode* phead, SLTDataType x1, SLTDataType x2) {<!-- -->
SLTNode* cur = FindByContent(phead, x1);
cur->data = x2;
}

Add, delete, check and modify-add

(head insertion, tail insertion, insertion before the specified node, insertion after the specified node)

1. Plug

//5.1 plug
void PushFront(SLTNode** pphead, SLTDataType x) {<!-- -->
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}

Question: Why does the data x not pass the pointer when passing the parameter, but the head node needs to pass the secondary pointer?
Because the data x is passed in, it will be immediately placed in the space applied for on the heap through the BuySLTNode function. The point becomes a new node newnode, which is equivalent to a change in the value of the head node pphead. The head node is a first-level pointer, and the modification of the first-level pointer requires a second-level pointer

2. Tail plug

//5.2 tail plug
void PushBack(SLTNode** pphead, SLTDataType x) {<!-- -->
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL) {<!-- -->
*pphead = newnode;
//To change the structure pointer, use a second-level pointer. The first-level pointer can only modify the formal parameter, and the formal parameter is destroyed after going out of scope
}
else {<!-- -->
SLTNode* tail = *pphead;
while (tail->next != NULL) {<!-- -->
tail = tail->next;
}
tail->next = newnode;
}
}

3. Insert before the specified node

Insert before the specified node, you need to get the previous node at the specified position. There are control loop method and pre-pointer method to let the pointer stay at the previous node, but the control loop method can only be used when the number of nodes to be inserted is known, while the pre-pointer method can be used in any case

3.1 Specify nodes by serial number

The control for loop method is used

//5.3 Insert before the specified node (specify the node by serial number)
void InsertFrontBySerialNumber(SLTNode** pphead, int n, SLTDataType x) {<!-- -->
//Create a new node and assign a value
SLTNode* newnode = BuySLTNode(x);
SLTNode* ptmp = *pphead;
//If you want to insert a node before the first node, it becomes a head insertion
if (n == 1) {<!-- -->
PushFront(pphead, x);
return;
}
//Put the node into the previous node at the specified position, the specified position does not include the first node
for (int i = 2;i < n;i ++ ) {<!-- -->
ptmp = ptmp->next;
if (ptmp == NULL)
printf("The location is invalid");
}
newnode->next = ptmp->next;
ptmp->next = newnode;

}

The reason why this function needs to pass the second-level pointer is because there is a plug-in situation, and the SLTPushFront function needs to be called, but it is actually a first-level pointer, and the address of the first-level pointer can be obtained when calling the PushFront function.

3.2 content->address->find node

The while loop and the forward pointer method are used

//5.4 Insert before the specified node (content->address->find node)
//Parameter two pos is the node position returned by the Find function called by test.c
void InsertFrontByAddress(SLTNode** pphead, SLTNode* pos, SLTDataType x) {<!-- -->
assert(pphead);
assert(pos);
//head plugging situation
if (*pphead == pos) {<!-- -->
PushFront(pphead, x);
}
//non plug
else {<!-- -->
SLTNode* prev = *pphead;
while (prev->next != pos) {<!-- -->
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos;
prev->next = newnode;
//Because there are two pointers to control the inserted node and the previous node respectively, the order of these two sentences is random
}
}

3.3 Specify nodes by content

The while loop and the forward pointer method are used

//5.5 Insert before the specified node (specify node by content)

void InsertFrontByContent(SLTNode** pphead, SLTDataType x1, SLTDataType x2) {<!-- -->
SLTNode* cur = *pphead;
//head plugging situation
if (cur->data == x1) {<!-- -->
PushFront(pphead, x2);
}
//Non-head inserted case
else {<!-- -->
cur = FindByContent(*pphead, x1);
SLTNode* prev = *pphead;
while (prev->next != cur) {<!-- -->
prev = prev->next;
}//The second pointer prev is required at this time
SLTNode* newnode = BuySLTNode(x2);
newnode->next = cur;
prev->next = newnode;
}
}

When you only know the content of the specified node without using the FindByContent function, you need to enter each node to compare whether the data is consistent. At this time, you can only use the while instruction and the pre-pointer method, because you do not know the specified position in advance, and you cannot use it to control the for loop. Find the predecessor node at the specified position

4. Insert after the specified node

4.1 Specify nodes by serial number

//5.6 Insert after the specified node (specify the node by serial number)
void InsertBackBySerialNumber(SLTNode** pphead, int n, SLTDataType x) {<!-- -->
//The original linked list is empty
if (*pphead == NULL) {<!-- -->
SLTNode* newnode = BuySLTNode(x);
*pphead = newnode;
}
//The original linked list is not empty
SLTNode* newnode = BuySLTNode(x);
SLTNode* ptmp = *pphead;
// Put the node into the next node at the specified position
for (int i = 1;i < n;i ++ ) {<!-- -->
ptmp = ptmp->next;
//The specified node exceeds the maximum length, and an error is reported
if (ptmp == NULL);
assert(ptmp);
}
newnode->next = ptmp->next;
ptmp->next = newnode;
}

4.2 content->address->find node

//5.7 Insert after the specified node (content->address->find node)
//The parameter one pos is the node position returned by the SLTFind function called by test.c
void InsertBackByAddress(SLTNode* pos, SLTDataType x) {<!-- -->
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

4.3 Specifying nodes by content

Without the FindByContent function

//5.8 Insert after the specified node (specify the node through the content) without using the FindByContent function
void InsertBackByContent(SLTNode** pphead, SLTDataType x1, SLTDataType x2) {<!-- -->
SLTNode* newnode = BuySLTNode(x2);
SLTNode* cur = *pphead;
//The original linked list is empty, newnode is the head node
if (cur == NULL) {<!-- -->
*pphead = newnode;
}
while (cur) {<!-- -->
if (cur->data == x1) {<!-- -->
//The specified node is the end node
if (cur->next == NULL) {<!-- -->
cur->next = newnode;
}
//The specified node is not the end node
else {<!-- -->
newnode->next = cur->next;
cur->next = newnode;
}
}
cur = cur->next;
}
\t//did not find
return;
}

Add, delete, check and modify–delete

(head delete, tail delete, delete the specified position, delete the previous node at the specified position, delete the next node at the specified position)

1. Header deletion

//6.1 header deletion
void PopFront(SLTNode** pphead) {<!-- -->
//The head node is empty, and an error is reported
assert(*pphead);
\t//not null
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}

2. Tail deletion

//6.2 Tail deletion
void PopBack(SLTNode** pphead) {<!-- -->
//The head node is empty, and an error is reported
assert(*pphead);
//only one node
if ((*pphead)->next == NULL) {<!-- -->
free(*pphead);
*pphead = NULL;
}
//There are two or more nodes
else {<!-- -->
SLTNode* tail = *pphead;
while (tail->next->next)
{<!-- -->
tail = tail->next;//Point to the front node of the tail node
}
free(tail->next);
tail->next = NULL;
}
}

3. Delete the previous node of the specified node

(Because the pre-pointer method is more general than the control for loop method, only the pre-pointer method is shown here)

//Delete the previous node of the specified node
void DeleteFrontNode(SLTNode** pphead, SLTNode* pos) {<!-- -->
//The specified location cannot be the head node
if (pos == *pphead) {<!-- -->
return;
}
//The specified position is the second node, the head node is deleted, and the head node is updated
if ((*pphead)->next == pos) {<!-- -->
PopFront(pphead);
}
//Define the front pointer prev of pos
else {<!-- -->
SLTNode* prevprev = *pphead;
while (prevprev->next->next != pos) {<!-- -->
prevprev = prevprev->next;
}
free(prevprev->next);
prevprev->next = pos;
}
}

4. Delete the specified location node

//Delete the specified location node
void DeleteNode(SLTNode** pphead, SLTNode* pos) {<!-- -->
//If the head node is deleted, the head delete function
if (pos == *pphead) {<!-- -->
PopFront(pphead);
}
else {<!-- -->
SLTNode* prev = *pphead;
while (prev->next != pos) {<!-- -->
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

5. Delete the node after the specified node

//Delete the node after the specified node
void DeleteAfterNode(SLTNode* pos) {<!-- -->
// check if pos is empty
assert(pos);
//Check if pos is the tail node
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}

Test function test.c

Test head plug and tail plug

SLTNode* testPush_Front_Back() {<!-- -->
//Test head plugged into PushFront
printf("Please enter the length of the header:");
int n = 0;
scanf("%d", &n);
printf("Please enter the value of the nodes in turn:\\
");
SLTNode* plist = NULL;
for (int i = 0;i < n;i ++ ) {<!-- -->
int val = 0;
scanf("%d", &val);
PushFront( &plist, val);
}
SLTPrint(plist);
//Test tail plug
printf("Please enter the tail length:");
int m = 0;
scanf("%d", &m);
printf("Please enter the value of the nodes in turn:\\
");
for (int i = 0;i < m;i ++ ) {<!-- -->
int val = 0;
scanf("%d", &val);
PushBack( &plist, val);
}
SLTPrint(plist);
return plist;
//destroy linked list
Destroy_Method1( &plist);
//Destroy_Method2( & amp;plist);
}

test is inserted before the specified node

void testInsertFront() {<!-- -->
SLTNode* plist = testPush_Front_Back();
//Insert before the specified node (specify the node by serial number)
printf("Insert before the specified node (specify node by serial number)\\
");
printf("Please enter the node number:");
int input1 = 0;
scanf("%d", &input1);
printf("Please enter the inserted data");
SLTDataType data1 = 0;
scanf("%d", &data1);
InsertFrontBySerialNumber( & plist, input1, data1);
SLTPrint(plist);

//Insert before the specified node (content->address->find node)
printf("Insert before the specified node (content->address->find node)\\
");
printf("Please enter the data to be inserted:");
SLTDataType data2 = 0;
scanf("%d", &data2);
SLTNode* pos = FindByContent(plist, data2);
printf("Please enter the inserted data:");
SLTDataType data3 = 0;
scanf("%d", &data3);
InsertFrontByAddress( &plist, pos, data3);
SLTPrint(plist);

//Insert before the specified node (specify node by content)
printf("Insert before the specified node (specify node by content)\\
");
printf("Please enter the data to be inserted:");
SLTDataType data4 = 0;
scanf("%d", &data4);
printf("Please enter the inserted data:");
SLTDataType data5 = 0;
scanf("%d", &data5);
InsertFrontByContent( &plist, data4, data5);
SLTPrint(plist);
//destroy linked list
Destroy_Method1( &plist);
//Destroy_Method2( & amp;plist);
}

test is inserted after the specified node

void testInsertBack() {<!-- -->
SLTNode* plist = testPush_Front_Back();
// Insert after the specified node (specify the node by serial number)
printf("Insert after the specified node (specify node by serial number)\\
");
printf("Please enter the node number:");
int input2 = 0;
scanf("%d", &input2);
printf("Please enter the inserted data:");
SLTDataType data6 = 0;
scanf("%d", &data6);
InsertBackBySerialNumber( &plist, input2, data6);
SLTPrint(plist);

//Insert after the specified node (content->address->find node)
printf("insert after the specified node (content->address->find node)\\
");
printf("Please enter the data to be inserted:");
SLTDataType data7 = 0;
scanf("%d", &data7);
SLTNode* pos = FindByContent(plist, data7);
printf("Please enter the inserted data:");
SLTDataType data8 = 0;
scanf("%d", &data8);
InsertBackByAddress(pos, data8);
SLTPrint(plist);

//Insert after the specified node (specify node by content)
printf("Insert after the specified node (specify node by content)\\
");
printf("Please enter the data to be inserted:");
SLTDataType data9 = 0;
scanf("%d", &data9);
printf("Please enter the inserted data:");
SLTDataType data10 = 0;
scanf("%d", &data10);
InsertBackByContent( & amp;plist, data9, data10);
SLTPrint(plist);
//destroy linked list
Destroy_Method1( &plist);
//Destroy_Method2( & amp;plist);
}

Test various deletions

void testPop() {<!-- -->
SLTNode* plist = testPush_Front_Back();
//Test header delete
printf("Delete test header\\
");
PopFront( &plist);
SLTPrint(plist);

//Test tail deletion
printf("Test tail deletion\\
");
PopBack( &plist);
SLTPrint(plist);

//Delete the previous node of the specified node
printf("Delete the node before the specified node\\
");
printf("Please enter the specified node content:\\
");
SLTDataType data11 = 0;
scanf("%d", &data11);
SLTNode* pos1 = FindByContent(plist, data11);
DeleteFrontNode( &plist, pos1);
SLTPrint(plist);

//Delete the node at the specified location
printf("Delete the specified location node\\
");
printf("Please enter the specified node content:\\
");
SLTDataType data12 = 0;
scanf("%d", &data12);
SLTNode* pos2 = FindByContent(plist, data12);
DeleteNode( &plist, pos2);
SLTPrint(plist);

//Delete the node after the specified node
printf("Delete the node after the specified node\\
");
printf("Please enter the specified node content:\\
");
SLTDataType data13 = 0;
scanf("%d", &data13);
SLTNode* pos3 = FindByContent(plist, data13);
DeleteAfterNode(pos3);
SLTPrint(plist);

//destroy linked list
Destroy_Method1( &plist);
//Destroy_Method2( & amp;plist);

}

Main function

Comment out the other three when testing one, or you will be exhausted O(∩_∩)O haha~

int main() {<!-- -->
testPush_Front_Back();
testInsertFront();
testInsertBack();
testPop();
}

Test results

Test 1: Head Plug and Tail Plug

Test 2: Insert a node before the specified node

Test 3: Insert a node after the specified node

Test 4: Various deletions

Currently, there is a small defect. When finding a node through the specified content, if there are multiple identical data, it will stop at the first position where the data appears and perform operations such as insertion. This is because the current node The data in is just a simple number. When there are more data in the node or each node has its own unique identifier in the future, this defect will not exist.

Connect all the above code blocks together to form a complete program. The first is the header file list.h, the next is the function implementation list.c, and the last is the test file test.c, which is divided into 4 functions.

There are a lot of functions in the insert and delete functions. I wrote everything I thought of, which is a bit cumbersome. Everyone mainly uses ideas for reference. Please correct me in time if there are any mistakes, thank you