current position:Home>In depth analysis of headless single linked list -- dynamic diagram demonstration of C language

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

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

 Insert picture description here

Personal introduction
Data structure series Click to jump
Poke me and jump to my personal home page
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
 Insert picture description here

Headless one-way linked list

  • 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.
     Insert picture description here

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 .
     Insert picture description here
  • If the initiative fails , End the program .
  • else Initialize the node .
  • Finally, return to the node .

Function declaration in header file
 Insert picture description here

Function definition in source file
 Insert picture description here


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 .

 Insert picture description here

  • 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 了 .
 Insert picture description here

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.
 Insert picture description here

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

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


Print

  • Print and traverse the linked list in turn ok 了 .
    Source file
     Insert picture description here test Source file

 Insert picture description here

Head insertion

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  Insert picture description here
2. Create a new node
 Insert picture description here
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 . Insert picture description here


Deletion at the end

 Without saying , Draw a picture first .

 Insert picture description here

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.
 Insert picture description here When tail->next Not empty ,prev Point to tail Point to .tail Move forward .
 Insert picture description here
The two pointers continue to move until tail->next by NULL. Insert picture description here When tail->next Jump out of loop when null

 Insert picture description here Jump out of the loop and prev->next Set to empty .free fall tail Space .tail Set to empty

 Insert picture description here

2. When the table is empty

When the table is empty, you can directly return.

3. When the table has only one node

direct free fall The head pointer (*pphead) Point to space .
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

Head deletion

1. When the table is empty

 Insert picture description here

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 .
 Insert picture description here


lookup

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

 Insert picture description here

 Insert picture description here


Insert a node before the specified element

Call the lookup function first . Find the address of this element . Then return .
 Insert picture description here

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
 Insert picture description here

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 .

 Insert picture description here

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 .
Let the head pointer advance one node , Until the entire linked list is traversed .
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 
SListNode* SListNodeBuyNewnode(SLNDataType x);
// Tail insertion 
void SListNodePushBack(SListNode** pphead, SLNDataType x);
// Print 
void SListNodePrint(SListNode** pphead);
// Head insertion 
void SListNodePushFront(SListNode** pphead, SLNDataType x);
// Deletion at the end 
void SListNodePopBack(SListNode** pphead);
// Head deletion 
void SListNodePopFront(SListNode** pphead);
// lookup 
SListNode* SListNodeFind(SListNode** pphead, SLNDataType x);
// Insert a node before an address 
void SListInsert(SListNode** pphead, SListNode* pos, SLNDataType x);
// The destruction 
void SListNodeDestory(SListNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
// Dynamically apply for a node 
SListNode* SListNodeBuyNewnode(SLNDataType x)
{
    
	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 
void SListNodePushBack(SListNode** pphead, SLNDataType x)
{
    
	SListNode* newnode = SListNodeBuyNewnode(x);
	// When the list is empty 
	if (*pphead == NULL)
	{
    
		*pphead = newnode;
	}
	// When it's not empty 
	else
	{
    
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
    
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
// Print 
void SListNodePrint(SListNode** pphead)
{
    
	while (*pphead != NULL)
	{
    
		printf("%d->", (*pphead)->data);
		(*pphead) = (*pphead)->next;
	}
	printf("NULL\n");
}
// Head insertion 
void SListNodePushFront(SListNode** pphead, SLNDataType x)
{
    
	SListNode* newnode = SListNodeBuyNewnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
// Deletion at the end 
void SListNodePopBack(SListNode** pphead)
{
    
	assert(pphead);
	// When the table is empty 
	if (*pphead == NULL)
	{
    
		return;
	}
	// When a table has only one node 
	else if ((*pphead)->next == NULL)
	{
    
		free(*pphead);
		*pphead = NULL;
		return;
	}
	// When the table is not empty 
	else 
	{
    
		SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
    
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}
// Head deletion 
void SListNodePopFront(SListNode** pphead)
{
    
	assert(pphead);
	if (*pphead == NULL)
	{
    
		return;
	}
	SListNode* current = (*pphead)->next;
	free(*pphead);
	*pphead = current;
}
// lookup 
SListNode* SListNodeFind(SListNode** pphead, SLNDataType x)
{
    
	SListNode* cur = *pphead;
	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)
{
    
	SListNode* newnode = SListNodeBuyNewnode(x);
	if (*pphead == pos)
	{
    
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
    
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
    
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}
// The destruction 
void SListNodeDestory(SListNode** pphead)
{
    
	assert(pphead);

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

	*pphead = NULL;
}

copyright notice
author[_ Qiqi],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/119/202204291332456057.html

Random recommended