# In depth analysis of headless single linked list -- dynamic diagram demonstration of C language

2022-04-29 15:11:01_ Qiqi

Personal introduction
Data structure series Click to jump
Hello everyone , I am a _ Strange , a C/C++ Blogger . He Mu yuan is a freshman studying .
Welcome to exchange and study
️ The future of programming is bright , The road is winding .
Smile till the end is the winner

The realization of single linked list , To learn a single linked list, you need to be right C The language pointer is familiar with . Because the linked list , As the name suggests, it is a watch connected by a chain . And this chain is the pointer . It's actually the address . A table connected by address .
drawing ` Draw... Draw `, Let's see what a single linked list looks like .
The single linked list I implemented has no head . No initial node . There is only one head pointer . Point to first element . Each element of the single linked list ( It is generally called node ） Is a structure type . Each such node contains a pointer to the next node and a data .
As shown in the figure below .
Suppose that the address of each node is known . I wrote down the address of each structure

• The difference from teacher Yan's book is , Our single linked list has no initial node , The reason is that at the beginning of school, the single chain list starts with simplicity , Otherwise, it's easy to get confused .
• The essence of the linked list is the following picture .` As long as you understand this picture . Single linked list, you will .`
• The essence of the linked list is through `16 Address in hexadecimal ` Connected , You can say that ` The address is the pointer ` As shown in the figure .
• ` The pointer is equivalent to a green arrow `. The head pointer plist Inside is the address of the first node `0x00000030`, In the first node next The pointer stores the address of the second node `0x00000050`, In the first node next The pointer stores the address of the second node `0x00000010`… And so on until the last node next Pointer to `NULL`;

# Structure declaration ( node )

• Declare and create the structure in the header file , Why is it called `SListNode`, the reason being that `Signle List Node （ Single chain list ）` Abbreviation ;
• take int type typedef by `SLNDataType` The reason is that it is easy to replace the data of each node later .
• Every SListNode The node contains a `int Type data ` and A point to this node ` The pointer next`.

# Dynamic application for new nodes

• You need to apply for a node before tailoring , We call it `newnode`. On demand . Don't waste space .
• While applying again, we need to initialize this new node .
• hold next The pointer is assigned a null pointer . Data transmission the data we want to transmit .
• If the initiative fails , End the program .
• else Initialize the node .

Function definition in source file

# Tail insertion

• There is something to note here . That's the secondary pointer . Because of the need ` Modify the address in the header pointer ` So we need to send the address of the header pointer . The value inside can only be modified by sending the address .

• ` The reason is that the formal parameter is only a temporary copy of the argument . Only the address can change the value inside .`

• In teacher Yan Weimin's data structure book, we use `C++ References in grammar , yes & Symbol `, It's the same effect as sending addresses .

• Call the function of applying for space before tailoring .

• There are two cases of inserting data in the tail

## 1. When the list is empty .

When it is empty, it will directly newnode This address is assigned to *pphead Just ok 了 .

## 2. When the linked list is not empty .

You need to find the tail node first . At this point, we define a pointer to the head node `tail`
1.

`tail->next` Not empty , Is executed `tail = tail->next`.` It means to let tail The pointer moves forward one node `.
3. Not empty , Move a node forward
4.newnode->next It's empty . Jump out of while loop 5. Add a new node

6. take newnode The value is assigned to tail->next. This completes the tail deletion .

# Print

• Print and traverse the linked list in turn ok 了 .
Source file
test Source file

## 1. When the table is empty

The two situations can be combined into one .

## 2. When the table is not empty

1. Insert... At the first node
2. Create a new node

3. The first step will be newnode->next The pointer stores the address of the first node `0x0000 0030`.
The second step is to newnode Value `0x00000020` Pointer assigned to header .
` The order cannot be wrong , Otherwise, the logic is wrong .`
This completes the explanation of head insertion .

# Deletion at the end

`````` Without saying , Draw a picture first .
``````

## 1. When the table is not empty

Define a `prev` Pointer to the variable . Used to find ` The penultimate node ` And put his next The pointer is assigned to NULL.
When tail->next Not empty ,prev Point to tail Point to .tail Move forward .

The two pointers continue to move until tail->next by NULL. When tail->next Jump out of loop when null

Jump out of the loop and `prev->next Set to empty .free fall tail Space .tail Set to empty `

## 2. When the table is empty

When the table is empty, you can directly return.

## 3. When the table has only one node

` Remember to assign null to the header pointer . Otherwise, the head pointer is a wild pointer `.
This is the end of the explanation of the tail deletion

## 2. When the table is a node

Having only one node is the same as having multiple node codes . It can be combined into one .

## 3. When the table is not empty

Order one first current Variable is used to remember the address of the second node .（` because free After dropping the first node . The address of the second node cannot be accessed `.） And then again free U-turn pointer . And then current Put the value stored in the header pointer .

# lookup

Find an element , If you find his address . Otherwise return null pointer .

# Insert a node before the specified element

Call the lookup function first . Find the address of this element . Then return .

## 1. When the header pointer is equal to the address of the specified element

This situation is the same as the head plug . Look at the head in front

## 2. General situation

Just like the tail insertion . For details, see the end insert .

# The destruction

Why destroy ？
When our linked list has nodes perhaps You can destroy it when you don't want to use it anymore .

## 1. When the table is empty

Do not enter at this time while loop , Directly null the header pointer .

## 2. When the table is not empty

Set a temporary variable tmp. Used to save header pointer cur Of next Inside address .
then free The space pointed by the U-turn pointer .
At this point, the whole linked list is over .

Dear viewers , It's not easy to create , If you like, let's have a three company 、

# test.c

``````#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

int main()
{

SListNode* plist = NULL;
SListNodePushBack(&plist, 1);
SListNodePushBack(&plist, 2);
SListNodePushBack(&plist, 3);
SListNodePushBack(&plist, 4);
SListNodePushBack(&plist, 1);
SListNodePushFront(&plist, 0);
SListNodePushFront(&plist, -1);

SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePopBack(&plist);
SListNodePushFront(&plist, 0);
SListNodePushFront(&plist, -1);

SListNode* pos = SListNodeFind(&plist, 0);
SListInsert(&plist, pos, 6);

SListNodePrint(&plist);
SListNodeDestory(&plist);
SListNodePrint(&plist);
return 0;
}

``````

# SList.h

``````#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLNDataType;

typedef struct SListNode
{

SLNDataType data;
struct SListNode* next;
}SListNode;
// Dynamically apply for a node
// Tail insertion
// Print
// Deletion at the end
// lookup
// Insert a node before an address
void SListInsert(SListNode** pphead, SListNode* pos, SLNDataType x);
// The destruction

``````

# SList.c

``````#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
// Dynamically apply for a node
{

SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (NULL == newnode)
{

printf("malloc fail");
exit(-1);
}
else
{

newnode->data = x;
newnode->next = NULL;
}
return newnode;
}
// Tail insertion
{

// When the list is empty
{

}
// When it's not empty
else
{

while (tail->next != NULL)
{

tail = tail->next;
}
tail->next = newnode;
}
}
// Print
{

{

}
printf("NULL\n");
}
{

}
// Deletion at the end
{

// When the table is empty
{

return;
}
// When a table has only one node
{

return;
}
// When the table is not empty
else
{

SListNode* prev = NULL;
while (tail->next != NULL)
{

prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}
{

{

return;
}
}
// lookup
{

while (cur)
{

if (cur->data == x)
{

return cur;
}
else
{

cur = cur->next;
}
}
return NULL;

}
// Insert a node before an address
void SListInsert(SListNode** pphead, SListNode* pos, SLNDataType x)
{

{

}
else
{

while (prev->next != pos)
{

prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
// The destruction
{

while (cur)
{

SListNode* tmp = cur->next;
free(cur);
cur = tmp;
}