单链表-基本结构_插入查找

「这是我参与2022首次更文挑战的第4天，活动详情查看：2022首次更文挑战」

不带头单向非循环单链表

顺序表的缺陷

• 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
   再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

链表是什么

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

顺序表：空间连续

链表：结点的地址随机

逻辑结构和物理结构

• 现实中的结点一般都是从堆上申请出来的
• 从堆上申请空间，是按照一定的策略来分配，两次申请的空间可能连续，也可能不连续

链表种类

• 单向/双向
• 带头/不带头
• 循环/非循环

3者互相组合，又2*2*2 = 8种链表

00.基本结构

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;

带头与不带头的问题：

• ==不带头==：用头指针，指针指向的就是第一个结点
  • 因为函数中可能要修改一级指针plist，所以我们要传plist的地址进行操作，即要使用二级指针
• ==带头==：plist指向的就是哨兵位结点，这个结点不存储有效数据。哨兵位的next，是第一个结点
  • 因为函数中不会修改plist，插入和删除都不会改变plist，因此不需要使用二级指针。插入删除改变的是plist指向的哨兵位的内容，plist本身不被修改

*函数内部要改变int类型的变量 ->传int **(传int的地址)

函数内部要改变int*类型变量->传int**(传int*的地址)

我们选择的是不带头的链表，也就是使用头指针，头指针指向的就是第一个结点

01.创建结点

每一个结点都是动态开辟的 动态开辟的变量放在堆区

1M = 1024KB = 1024*1024 Byte

栈区：8M 堆区：2M 栈的空间比堆的空间大

//创建新节点函数
SLTNode* BuyList(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);//退出整个程序
	}
	//开辟成功
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}

02.打印链表

由于打印不改变plist，所以可以传一级指针

• 遍历打印即可，最后指针走到NULL结束

//打印 
//因为不改变头指针，所以传值传地址都可以
void SListPrint(SLTNode* phead)
{
	//遍历链表进行打印 
	//可以打印空链表 所以不能断言assert(phead !=NULL)
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

03.尾插

• 考虑链表为空的情况：直接把新节点赋给头指针
• 多个结点：
  • ==方法==：遍历链表找到尾结点(特点：tail->next == NULL)
  • 尾结点的next链接新新节点

//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyList(x);
	//情况1：当链表为空
	if (*pphead == NULL)
	{
		//头指针指向新结点
		*pphead = newnode;
	}
	//情况2：一个或者多个结点
	//找到尾结点
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		//跳出循环时,tail就是尾结点
		//尾结点链接新结点
		tail->next = newnode;
	}
}

04.头插

头插要改变plist，所以传二级指针

• 新节点的next链接第一个结点
• 头指针指向新结点

当链表为空时，新节点的next指向NULL，然后头指针指向新结点 符合！不需要单独判断

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyList(x);
	//新结点链接第一个结点
	newnode->next = *pphead;
	//新节点成为新的头
	*pphead = newnode;
	//当链表为空，一个或多个结点上述都正确
}