无头单向链表_无头链表

目录

一、无头单向链表概念和结构

二、无头单向链表的接口实现

• 声明和定义
• 创建新结点
• 头插
• 尾插
• 头删
• 尾删
• 在任意位置之前插入
• 删除任意位置的数据
• 查找
• 打印
• 销毁顺序表

三、无头单向链表的优缺点

---

一、无头单向链表概念和结构

链表的概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

 结构示意图：由前一个链表中的指针指向下一个链表的地址，在逻辑上是连续的。

二、无头单向链表的接口实现

• 声明和定义

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

• 创建新结点

顺序表是按需创造和销毁结点，每当想存储一个数据的时候，就malloc一个新结点

//创建新节点
SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

• 头插

创造新节点，直接将新节点包含的指针指向原来的头结点，将新节点的地址作为之前的头结点。

//头插
void SListPushFrond(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
 
	*pphead = newnode;
}

• 尾插

创造一个新的结点，判断原来的头是否为空，为空，将新创造的结点作为新的头。不为空就找到尾结点将尾结点包含的指针指向新创建的结点地址。

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
 
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾节点
		SLTNode* tail = *pphead;//tail结尾
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

• 头删

判断链表是否为空，不为空，将头节点的地址修改成头节点指向的下一个结点的地址，释放之前的头结点。

//头删
void SListPopFrond(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	*pphead = next;
}

• 尾删

判断链表是否为空，不为空，找到尾结点，将尾结点之前的结点指向下一个结点的指针置为空，释放掉尾结点。

//尾删
void SListPopBack(SLTNode** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tailPrev = NULL;//tailPrev 结尾之前
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		tailPrev->next = NULL;
		free(tail);
		tail = NULL;
	}
}

• 在任意位置之前插入

找到pos位置，保存pos之前的结点的地址，创建新结点，pos之前的结点中指向下一个结点指针指向新节点，新节点中指向下一个结点指针指向pos

//pos位置之前插入
void SListInsrt(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos && pphead);
	SLTNode* newnode = BuySListNode(x);
	if (pos == *pphead)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		SLTNode* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve ->next = newnode;
		newnode->next = pos;
	}
}

• 删除任意位置的数据

找到pos之前的结点的地址，pos之前的结点中指向下一个结点的指针指向pos结点中指向下一个结点的地址，释放pos。

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos && pphead);
	
	if (pos == *pphead)
	{
		*pphead = pos->next;
	}
	else
	{
		SLTNode* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve->next = pos->next;
	}
	free(pos);
	pos = NULL;
}

• 查找

//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cru = phead;
	while (cru)
	{
		if (cru->data == x)
		{
			return cru;
		}
		else
		{
			cru = cru->next;
		}
	}
	return NULL;
}

• 打印

//打印链表
void SListPrint(SLTNode* phead)
{
	SLTNode* cru = phead;
 
	while (cru != NULL)
	{
		printf("%d->", cru->data);
		cru = cru->next;
	}
	printf("NULL\n");
}

• 销毁顺序表

void SListDestory(SLTNode** pphead)
{
    
    //使用尾删
    SListPopBack（pphead)；
 
}

三、无头单向链表的优缺点

优点：
1. 无头单向链表可以轻松地插入或删除链表的头部和尾部，因为它不需要像有头链表一样先找到头部节点。
2. 在某些情况下，无头单向链表可以在空间上更加高效，因为它不需要额外的头节点。

缺点：
1. 在访问链表中的任何节点之前需要检查链表是否为空，因为没有头节点来作为起点。
2. 在查找链表中的任何节点时，必须从头开始遍历，因为没有头节点可以直接引用链表的起点。这可能会导致性能下降，特别是对于较大的链表来说。