【数据结构】单链表

一 概念结构

概念：

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

结构：

【头】-【】-【】-【】-【】-【】-【】-【】-【尾】

链表的打印

尾插

创建SLTBuyNode函数，开辟新空间，创建一个新的结点，方便后续操作。

注意：

因为要改变原链表（指针），所以要使用传址调用，那么就是传指针的地址，所以要使用双指针（**pphead）。

要多注意ptai与pphead的对应关系

ptail -> *pphead

时间复杂度：O（n）

头插：

相对尾插较为简单。

时间复杂度：O（1）；

尾删：

注意判断是否是只有一个结点即可

时间复杂度：O（n）

头删：

时间复杂度：O（1）

由此看来，单链表的头部操作要优于顺序表的头部操作，但单链表的尾部操作是没有顺序表快的。所以要看使用情况，再决定使用什么工具。

查找:

注意：未找到时，要返回NULL;

时间复杂度：O（n）

指定位置之前插入数据

注意：

判断是否是第一个和结点。

如果是第一个结点，就相当与头插。不是第一个节点，需要找到pos位置，并且保留pos前一个位置prev，最后连接，prev->newnode->pos

时间复杂度：O（n）

指定位置之后插入数据

相对于之前，之后要简单点，且传入的参数不需要原头节点了，因为此操作只影响pos之后的链表，只需要传入pos指针即可。

时间复杂度：O（1）

删除pos位置的结点 

同样是先判断pos是否是头结点

若不是头结点，则需要找到pos前一个的位置，通过更改prev->next的数据，实现删除pos

free后要记得 = NULL；

时间复杂度：O（n）

删除pos位置之后的结点

注意：pos位置和pos->next都不能是NULL。

时间复杂度：O（1）

对于单链表pos之后的操作，时间复杂度都是O（1），因为不需要遍历。

销毁链表

与顺序表不同，顺序表是连续的空间，只需要free（arr）即可，单链表每一个结点都是单独的空间，所以需要把每一个结点都free掉。

时间复杂度：O（n）

单链表总结：

链表头部的插入删除O（1）

链表尾部的插入删除O（n）

链表无需扩容

链表不存在空间浪费