初识链表（7.25）

前面我们学习了顺序表，但顺序表其实存在一些问题

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

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗（尤其是异地扩容）。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

优点：

1.尾插尾删足够快

2.下标的随机访问和修改

如何改善顺序表的这些问题呢？那么看看远处的链表吧

3.1 链表的概念及结构

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

链表在内存中是什么样的呢？
以往在数组中内存空间是连续的，通过一个指针和 size 就能够找到并管理所有值；

在链表中的空间是多段不连续的，空间之间也没有大小关系，链表也定义一个头指针指向第一个空间，第一个空间中存放一个指针指向第二个空间，每个空间都有一个指针指向下一个空间，而最后一个空间的指针指向NULL（空）。

形如：

物理形态：（箭头是臆想的）

节点的空间是从堆上随机申请的，两次申请的空间可能连续，可能不连续。

3.2 链表的初步实现

初级单向链表举例：

//single link table
typedef int SLTDateType;
typedef struct SListNode //(链表节点)
{//数据SLTDateType data;//结构体类型的指针，能够找到下一个结构（节点）SLTDateType* next;
}SLTNode;//将结构体简写，等同于下一行
//typedef struct SListNode SLTNode;//打印链表
void PrintSList(SLTNode* phead)
{//拷贝头指针SLTNode* cur = phead;while (cur!=NULL){printf("%d ", cur->data);//指针指向节点中的下一个节点的地址cur = cur->next;}printf("NULL\n");
}
int main()
{//插入节点SLTNode* p1 = (SLTNode*)malloc(sizeof(SLTNode));p1->data = 10;SLTNode* p2 = (SLTNode*)malloc(sizeof(SLTNode));p2->data = 20;SLTNode* p3 = (SLTNode*)malloc(sizeof(SLTNode));p3->data =30;//让上一个节点指向下一个节点p1->next = p2;p2->next = p3;p3->next = NULL;PrintSList(p1);return 0;
}