链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的分类
链表有8种结构
1.单向、双向
2. 带头、不带头
3. 循环、非循环
本节我们主要介绍单链表(即单向不带头非循环链表)的接口实现
单链表的声明
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
具体的逻辑结构如图：
物理结构(假设链表中的值为1,2,3,4)：
单链表的接口实现
1.SListNode* BuySListNode(SLTDataType x)
描述：动态申请一个结点
实现：
SListNode* BuySListNode(SLTDataType x)
{ //申请一个节点
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc node fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
2.void SListPrint(SListNode* phead)
描述：对单链表进行打印
实现：
//根据指针的next，一直向后走到空，进行遍历
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
3.void SListPushBack(SListNode** phead, SLTDataType x)
描述：对单链表进行尾插
实现：
//即申请一个新的节点，然后让原来指针的最后一个指向该节点，然后改节点的next指针指> 向NULL
//因为是对指针的修改，因此要用二级指针**phead，以下同理。
void SListPushBack(SListNode** phead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*phead == NULL)
{
*phead = newnode;
}
else
{
//找尾
SListNode* tail = *phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
4. void SListPushFront(SListNode** phead, SLTDataType x)
描述：对单链表进行头插
实现：
//将头指针指向新的节点，然后新的节点的next指针指向之前phead->next。
void SListPushFront(SListNode** phead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*phead == NULL)
{
*phead = newnode;
}
else
{
*phead = newnode;
}
}
5. void SListPopFront(SListNode** phead)
描述：对单链表进行头删
实现：
//将头指针指向phead->next->next，然后free掉phead->next即可（用temp来保存）
void SListPopFront(SListNode** phead)
{
if (*phead == NULL) //空
{
return;
}
else if ((*phead)->next == NULL) //一个结点
{
free(*phead);
*phead = NULL;
}
else//多个结点
{
SListNode* next = (*phead)->next;
free(*phead);
*phead = next;
}
}
6.void SListPopBack(SListNode** phead)
描述：对单链表进行尾删
实现：
void SListPopBack(SListNode** phead)
{
// 链表为空
if (*phead == NULL)
{
return;
}
else if ((*phead)->next == NULL) // 只有一个节点
{
free(*phead);
*phead = NULL;
}
else // 多个节点
{
SListNode* prev = NULL;
SListNode* tail = *phead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
7.void SListInsertAfter(SListNode* pos, SLTDataType x)
描述：在单链表的pos位置之后进行插入操作。
解释：为何不在pos之前进行插入—> 在pos后插入
- 若要在pos之前插入，对于单链表而言，算法会相对比较复杂，首先需要找到pos之前的位置；
- 因为单链表没有指向前面的指针，因此就需要在定义一个指针用来存放pos之前的指针，然后再插入元素，再用新插入的节点的next指向pos，即可实现前插。
- 而后插相对而言就比较简单，直接到pos位置，然后插入，再完成next指向的变化即可。
实现：
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
8. void SListEraseAfter(SListNode* pos)
描述：删除单链表中pos位置之后的结点
实现：
void SListEraseAfter(SListNode* pos)
{
if (pos->next == NULL) {
return;
}
SListNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}
//创建动态的节点
SListNode* BuySListNode(SLTDataType x)
{ //申请一个节点
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc node fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
9. SListNode* SListFind(SListNode* plist, SLTDataType x)
描述：寻找单链表中值为x的结点
实现：
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* head = plist;
while (head)
{
if (head->data == x)
{
return head;
}
head = head->next;
}
return NULL;
}
顺序表（数组）和链表的区别和联系
顺序表（一白遮百丑）
缺点：(百丑)
- 头部或中间插入删除数据，时间复杂度为o(n)
- 当空间不够时，需要增容，而在增容时会存在相应的消耗，一般增容时都是增容1.5倍或2倍，这样做可能会存在一定程度的空间浪费
优点：(一白)
- 相对于链表而言空间利用率高，不需要额外的空间，占用的空间小
- 物理空间是连续的。
a. 支持随机访问，可以用下标进行访问
b. 相比链表结构，缓存命中率比较高，访问更高效
链表(一黑毁所有)
缺点：(一黑)
- 以结点为单位存储，不支持随机访问
- 缓存命中率低
优点：(所有)
- 支持任意位置的插入，时间复杂度为o(1) (双向带头循环链表)
- 不存在增容的问题，插入一个就新开辟一个空间
对于缓存命中率的一些解释：
CPU在取数据进行运算时，先看数据在不在缓存
- 若在缓存中(缓存命中)，则直接运算，再写回内存
- 若不在缓存中(缓存未命中)，则先从加载一段的连续的内存数据到缓存中，再进行运算，然后再写回内存。(这样做的后果是可能会带来缓存污染)
因为顺序表的物理空间是连续的，因此CPU在数据运算时，数据存储空间都在一起连着，因此缓存的命中率就会高，而对于链表而言，由于物理空间是不连续的，出现缓存未命中的情况会多一些，因此缓存命中率会低一些。