数据结构之单链表_数据结构单链表

前言：

    之前的文章，我们了解了顺序表，包括静态顺序表和动态顺序表。具体可以看我的上两篇文章

1.静态顺序表知识及代码实现：静态顺序表

2.动态顺序表知识及代码实现：动态顺序表

   既然顺序表已经能存储数据，那么我们什么又要引入链表呢？   首先，我们要知道顺序表的优缺点：

   优点：空间连续，支持随机访问

   缺点： 1.中间或头部分的插入删除的时间复杂度为O(N)  2.增容的代价比较大

如何解决？

1.空间上，按需给空间

2.不要求物理空间连续，头部和中间的插入就不用挪动数据

为了解决上述问题，我们引入了链表的概念。

---

目录

前言：

一:什么是链表

二:链表的种类

三:单链表的特点

四：创建项目

五：接口实现

1.创建结构体类型

2. 链表开辟空间

带头和不带头（使用头指针）的有什么区别？

3.打印数据

4.创建节点

5.尾插数据

6.头插数据

7.尾删数据

8.头删数据

9.查找数据所在位置

10.在pos位置之前插入数据

11.删除pos位置

12.判断单链表是否为空

13.计算单链表长度 

14.销毁单链表 

六.精华总结：

附：源码链接 

---

---

一:什么是链表

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

---

这里简单介绍一下逻辑结构和物理结构

• 逻辑结构: 人为想象出来的,实际并不存在.
• 物理结构: 实际存在,可以被观察到

---

二:链表的种类

共有8种链表结构，请看图！

根据排列组合，2*2*2共有八种情况。

---

三:单链表的特点

特点

(1)用链表存储实现的线性结构

(2)一个结点存储一个数据元素

(3)各结点之间先后关系用一个指针表示

     下面我们实现的是无头单向非循环链表

   结构体数据域存数据，指针域存下一个节点的地址。 

   无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

---

四：创建项目

五：接口实现

1.创建结构体类型

        为了后续我们想更改数据类型时方便，我们一般对类型进行typedef操作。

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;		//存放数据
	struct SListNode* next;	//指向下一个节点
}SLTNode;

---

2. 链表开辟空间

我们接下来实现的是不带哨兵位的，即不带头节点。 我们要定义结构体指针。

SLTNode* phead = NULL;	//头指针 

---

带头和不带头（使用头指针）的有什么区别？

带头：使用哨兵位（头节点） 

    此时phead指向的下一个节点才是单链表的第一个节点，带头结点就不需要改变传过来的指针，也就意味着不需要传二级指针。

---

不带头：使用头指针

此时phead指向的就是单链表的第一个节点。因为若要对phead的指向做修改，若传一级指针，就相当于传值，形参的改变并不会影响实参！所以我们应该把phead的地址传过去，用二级指针接收！

           像打印数据，查找数据这一类并不会对单链表内容修改的，我们传值也可以，传址也可以。

---

3.打印数据

只需要遍历链表，把每个节点的数据打印出来。最后一个节点的next为NULL跳出循环。

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

---

4.创建节点

使用malloc动态开辟节点！要判断空间开辟是否成功！    新节点的next要置空

//创建节点(带值)
SLTNode* BuySlistNode(SLTDataType x)
{
	//malloc一个节点 开辟空间
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc is fail\n");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

---

5.尾插数据

尾插：

情况1：链表为空时：直接将phead指向新开的节点

情况2：链表有节点了，->遍历链表找到尾指针，将尾指针的next链接新节点。

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);//防止pphead为空指针
	//先新建一个节点
	SLTNode* newnode = BuySlistNode(x);
	
	//当链表为空时，直接将phead指向新节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾指针,进行链接
		SLTNode* tail = *pphead;
		//遍历链表找尾指针
		while (tail->next)
		{
			tail = tail->next;
		}
		//链接新节点
		tail->next = newnode;
		//newnode->next = NULL;  newnode 初始化时next已经置空
	}
}

---

6.头插数据

头插：

1.新开一个

2.newnode先链接原来的第一个节点

3.phead指向newnode

顺序不可以反转，不然就找不到原来的第一个节点了。 按照上面的顺序，链表为空也无影响。原来第一个节点为NULL。

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
	//先新建一个节点
	SLTNode* newnode = BuySlistNode(x);
	
	//phead指向的节点给newnode->next		链表为空也无影响
	newnode->next = *pphead;
	//phead指向新节点
	*pphead = newnode;
}

---

7.尾删数据

尾删：

情况1：链表为空就不删了

情况2：只有一个节点时，free掉第一个节点，然后phead 置空

情况3：多节点时，找到尾节点，把尾节点空间释放掉，把还要找到尾节点前面的节点，将该节点的指向下一个节点的指针置空！否则会造成野指针情况！

//尾删
void SListPopBack(SLTNode** pphead)
{
	//1.链表为空就不删了
	if (*pphead == NULL)
		return;
	//2.只有一个节点   //！！！容易忽略		
	else if ((*pphead) ->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//3.多节点
	else
	{
		//找到尾指针及尾指针前面的指针  
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
			//将尾指针前面的指针置NULL  否则会造成野指针 
			prev->next = NULL;
			free(tail);
		}
}

---

8.头删数据

头删：

情况1：链表为空不删

情况2：有节点（1个或多个）

先保存第二个节点，然后释放掉第一个节点，phead指向原来的第二个节点。（只有一个节点也没问题，第一个节点的next为NULL）

//头删
void SListPopFront(SLTNode** pphead)
{
	//链表为空就不删了
	if (*pphead == NULL)
		return;
	else
	{
		SLTNode* next = (*pphead)->next;	//先保存第二个节点的位置
		free(*pphead);	//释放第一个节点  注意释放的是*pphead 不是pphead！！
		*pphead = next;
	}	
}

---

9.查找数据所在位置

遍历查找即可，找到了返回所在的位置，找不到返回空指针。

//查找位置
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	//遍历查找
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	//找不到/空链表返回NULL
	return NULL;
}

---

10.在pos位置之前插入数据

情况1：在第一个节点前插入：相当于头插，直接调用头插的接口

情况2：多节点

1.找到pos位置前的节点

2.创建新节点 

3.目标节点前的结点链接新节点

4.新节点链接目标节点

//在pos位置前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//当在第一个节点前插入：头插
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		//开辟新节点
		SLTNode* newnode = BuySlistNode(x);
		//找到pos前面的节点
		SLTNode* prev = *pphead;	
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//此时prev在pos前面
		prev->next = newnode;
		newnode->next = pos;
	}
}

---

11.删除pos位置

情况1：链表为空 不删除

情况2：删除的是第一个节点        ->相当于头删 ->调用头删接口

情况3：多节点

1.找到pos位置前的节点

2.pos位置前的节点链接pos位置后的节点

3.free掉pos位置节点

//删除pos位置的节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//空链表时不删除
	if (*pphead == NULL)
		return;
	//删除第一个节点时
	if (pos == *pphead)
	{
		SListPopFront(pphead);		//头删
	}
	else
	{
		// 找到pos前的节点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

---

12.判断单链表是否为空

 若phead指向的为空指针就说明为空链表

bool SListEmpty(SLTNode* phead)
{
	return phead == NULL;                 //phead== NULL为真则返回真
}

---

13.计算单链表长度 

使用计数器计数。因为不改变头指针phead，所以传值传址都可以。我们这里选择传值方式

int SListSize(SLTNode* phead)
{
    SLTNode* cur = phead;
    int size = 0;
    while(cur->next != NULL)
    {
        size++;
        cur = cur->next;
    };
    return size;
}

---

14.销毁单链表 

使用两个指针，一个保存下一个节点，一个用来遍历。free即可，最后把phead置空

void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;    //保存下一个节点
		free(cur);
		cur = next;
	}
 
	*pphead = NULL;
}

---

六.精华总结：

注意事项：

1.使用头指针  or   使用头节点

2.插入删除注意分情况讨论！如：链表为空。只有一个节点，多节点情况！不然容易出BUG

3.注意链接顺序！防止找不到上一个/下一个节点。

---

附：源码链接 

单链表（头指针+C语言实现）