Headless one-way acyclic linked list (implemented in C language)

Single list

Design ideas

The linked list is a non-sequential and non-sequential storage structure in the physical storage structure. The logical order of the data elements is through the linked list The pointers in link order are implemented in .

Preparatory work for adding, deleting, checking and modifying

There are two source files and one header file:

linked.h linked.c test.c

Node Type Definition

//linked.h
typedef int type;//Redefine the name of the data type, so that it is convenient to replace the data type in the linked list
typedef struct Chain_table//linked list type
{
	type data;//data field
	struct Chain_table* next;//pointer field
}ct;
copy

define a head node

//test.c
	ct* head = NULL;//head node pointer
copy

The default point is empty, if there is no data, it will be empty Open up node space

//linked.c
ct* crunode(type x)//Create a node dynamically
{
	ct* cur = (ct*)malloc(sizeof(ct));
	if (cur == NULL)
	{
		perror("malloc fail");
		exit(-1);//end of program
	}
	cur->data = x;
	cur->next = NULL;
	return cur;//Returns the address of the opened node
}
copy

print linked list function It cannot be asserted here whether it is a null pointer, because when there is no data, the point pointed to by the head node is a null pointer, so we also need to print the null pointer (because it is more vivid, and actually does not need to print NULL)

//linked.c
void SListPrint(ct* phead)//print linked list
{
	ct* cur = phead;//Let cur also point to the location of the head pointer
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");//print the NULL at the end
}
copy

Head plug and tail plug

The following functions are all in the linked.c file tail plug

void SListPushBack(ct** phead, type x)//tail plug
{
	assert(phead);//The assertion here is because phead points to the head node, so it cannot be empty
	ct* newnode = crunode(x);
	if (*phead == NULL)//head node pointer is null
	{
		*phead = newnode;//Let the head node point to the newly created node
	}
	else//Head node pointer is not null
	{
		ct* cur = *phead;
		while (cur->next)//find the last node
		{
			cur = cur->next;
		}
		cur->next = newnode;//Let the next area of ​​the last node store the address of the newly created node
	}
}
copy

It should be noted here that the address of the head node is passed by the second-level pointer, otherwise it will cause the formal participation and actual parameters to open up two independent spaces, so that the head node will not move due to the transfer function.

In this way, the head can be controlled by phead. plug

void SListPushFront(ct** phead, type x)//plug
{
	assert(phead);
	ct* newnode = crunode(x);
	newnode->next = *phead;
	*phead = newnode;
}
copy

The head insertion does not need to be divided into situations, because even if the linked list is empty, the head insertion is to store the position pointed to by the head node in the next of the newly created node.

Delete the head and delete the tail

tail delete

void SListPopBack(ct** phead)//tail delete
{
	assert(phead);
	assert(*phead);//Check if it is an empty list
	ct* cur = *phead;
	if (cur->next == NULL)//Determine whether there is only one node left in the linked list
	{
		free(cur);
		cur = NULL;
		*phead = NULL;
	}
	else
	{
		while (cur->next->next)//Determine whether to come to the end
		{
			cur = cur->next;
		}
		free(cur->next);//cur->next->next is empty, it means that cur->next points to the last node, release it
		cur->next = NULL;//Set the next of the end node to a null pointer
	}
}
copy

head delete

void SListPopFront(ct** phead)//head delete
{
	assert(phead);
	assert(*phead);//Check if the linked list is empty
	ct* cur = *phead;
	*phead = cur->next;
	free(cur);//Free up head node space
	cur = NULL;
}
copy

find and destroy

destroy

void SListDestory(ct** phead)//Destroy linked list
{
	assert(phead);
	ct* cur = *phead;
	while (cur)
	{
		ct* tai = cur->next;//Keep the next node of cur
		free(cur);
		cur = tai;
	}
	*phead = NULL;//Finally, let the head node pointer become a null pointer
}
copy

look up When designing a search, if the return value is not equal to a null pointer, it exists

ct* SListFind(ct* phead, type x)//search
{
	ct* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;//Find the corresponding address
		}
		cur = cur->next;
	}
	return NULL;//Returns a null pointer if not found
}
copy

Insert the node with data x after pos and delete the node after pos

This works with our lookup The address after the returned pos is where we want to insert and delete insert

void SListInsertAfter(ct* pos, type x)//Insert a node with data x after pos
{
	assert(pos);
	ct* newnode = crunode(x);
	newnode->next= pos->next;
	pos->next = newnode;
}
copy

delete

void SListEraseAfter(ct* pos)//Delete the node after pos
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;//If the node behind pos is empty, just return it directly
	}
	else 
	{
		ct* cur = pos->next;
		pos->next = cur->next;
		free(cur);
		cur = NULL;
	}
}
copy

As for inserting and deleting in front of pos, I don’t need to write it, just add a pointer to find the node in front of pos.

full code

linked.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int type;//Redefine the name of the data type, so that it is convenient to replace the data type in the linked list
typedef struct Chain_table//linked list type
{
	type data;//data field
	struct Chain_table* next;//pointer field
}ct;

//function declaration
ct* crunode(type x);//The development of the head node
void SListPrint(ct* phead);//print linked list

void SListPushBack(ct** phead, type x);//tail plug
void SListPushFront(ct** phead, type x);//plug
void SListPopBack(ct** phead);//tail delete
void SListPopFront(ct** phead);//head delete

void SListDestory(ct** phead);//Destroy linked list
ct* SListFind(ct* phead, type x);//look up

void SListInsertAfter(ct* pos, type x);//Insert a node with data x after pos
void SListEraseAfter(ct* pos);//Delete the node after pos
copy

linked.c

#include "linked.h"
ct* crunode(type x)//Create a node dynamically
{
	ct* cur = (ct*)malloc(sizeof(ct));
	if (cur == NULL)
	{
		perror("malloc fail");
		exit(-1);//end of program
	}
	cur->data = x;
	cur->next = NULL;
	return cur;//Returns the address of the opened node
}
void SListPrint(ct* phead)//print linked list
{
	ct* cur = phead;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");//print the NULL at the end
}
void SListPushBack(ct** phead, type x)//tail plug
{
	assert(phead);
	ct* newnode = crunode(x);
	if (*phead == NULL)//head node pointer is null
	{
		*phead = newnode;
	}
	else//Head node pointer is not null
	{
		ct* cur = *phead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
void SListPushFront(ct** phead, type x)//plug
{
	assert(phead);
	ct* newnode = crunode(x);
	newnode->next = *phead;
	*phead = newnode;
}
void SListPopBack(ct** phead)//tail delete
{
	assert(phead);
	assert(*phead);
	ct* cur = *phead;
	if (cur->next == NULL)
	{
		free(cur);
		cur = NULL;
		*phead = NULL;
	}
	else
	{
		while (cur->next->next)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}
void SListPopFront(ct** phead)//head delete
{
	assert(phead);
	assert(*phead);//Check if the linked list is empty
	ct* cur = *phead;
	*phead = cur->next;
	free(cur);//Free up head node space
	cur = NULL;
}
void SListDestory(ct** phead)//Destroy linked list
{
	assert(phead);
	ct* cur = *phead;
	while (cur)
	{
		ct* tai = cur->next;
		free(cur);
		cur = tai;
	}
	*phead = NULL;
}
ct* SListFind(ct* phead, type x)//search
{
	ct* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsertAfter(ct* pos, type x)//Insert a node with data x after pos
{
	assert(pos);
	ct* newnode = crunode(x);
	newnode->next= pos->next;
	pos->next = newnode;
}
void SListEraseAfter(ct* pos)//Delete the node after pos
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else 
	{
		ct* cur = pos->next;
		pos->next = cur->next;
		free(cur);
		cur = NULL;
	}
}
copy

test.c

#include "linked.h"
void test()
{
	ct* head = NULL;//head node pointer
	SListPushBack(&head, 1);//tail plug
	SListPushBack(&head, 2);
	SListPushFront(&head, 3);//plug
	SListPushFront(&head, 4);
	SListPopFront(&head);//head delete
	SListPopBack(&head);//tail delete
	ct* pos = SListFind(head, 1);//look up
	if (pos)
	{
		printf("YES\n"); 
		SListInsertAfter(pos, 9);
		SListPrint(head);//print linked list
		SListEraseAfter(pos);
	}
	else
	{
		printf("NO\n");
	}
	SListPrint(head);
	SListDestory(&head);//Destroy linked list
	SListPrint(head);

}
int main()
{
	test();
	return 0;
}
copy

Code running results

Tags: linked list function pointer

Posted by shatztal on Tue, 28 Mar 2023 13:28:17 +0530