【数据结构】单链表

---

1.为什么存在链表

我们在学习顺序表的时候，了解到顺序表有一定的缺陷：（1）在中间插入数据和删除数据需要挪动数据，时间复杂度是O（N），效率低下。（2）realloc会异地扩容，需要申请新空间，拷贝数据，释放旧空间。有不小的消耗。（3） realloc扩容后，难免有一定的空间浪费（数据删除后的空间或者扩容后不用的空间）。而链表就能弥补顺序表的缺点。

---

2.链表的概念

链表是一种物理存储结构上非连续（地址非连续）、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表就是在逻辑结构上就是一条链，链接着一个个节点，每个节点就是一个结构体，包含数据和指向下一个节点的地址。

节点的定义

typedef int SLTDataType;//方便后面更改数据的类型，//比如你存储的数据不是整形而是浮点型就可以在这里修改
typedef struct SListNode//链表的节点
{SLTDataType data;//数据struct SListNode* next;//指向下一个节点的指针
}SLTNode;//重命名：有意义的、简短的名字

---

3.单链表的实现

1. 打印链表（假设现在有一个现成的链表（上图））

void SLTPrint(SLTNode* plist)//plist是头节点
{while (plist!=NULL){printf("%d->", plist->data);plist = plist->next;}printf("NULL\n");
}

结果

1->2->3->4->NULL

疑惑
（1）plist = plist->next;是什么意思？能不能写成plist++;？
a.plist是头节点，指向第一个节点，节点的成员next是指针，指向第二个节点，将next存储的地址赋值给plist，plist就指向第二个节点。以此类推，直到plist指向最后一个节点的空指针。b.不能。plist++跳到物理地址上的下一个结构体。而链表的各节点在物理地址上是不连续的。

（2）循环体的判断条件能否改成whlie(plist->next!=NULL)？
不能，因为最后一个元素没有打印。

2. 单链表尾插
   （1）首先在找到最后一个节点，然后接上要插入的新节点。
   （2）其次，要考虑特殊情况，如果单链表是空链表该如何解决？

void SLTPushBack(SLTNode** pplist, SLTDateType x)//pplist是指向头节点的指针，x是新节点的数据
{assert(pplist);//pplist接收plist的地址，一定不是NULL，就更要断言，防止函数传参传个NULL过来//首先获得一个新节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL)//检查是否申请空间失败{perror("malloc");return;}newnode->data = x;//记得把数据放入新节点newnode->next = NULL;//记得将next置为NULL//考虑是空链表if (*pplist == NULL){*pplist = newnode;//直接让头指针接上新的节点就行return;}//不是空链表else{//首先找到链表的尾巴SLTNode* tail = *pplist;while (tail->next != NULL)//当tail指向最后一个节点时停止循环，因为最后一个节点的next是NULL{tail = tail->next;}//然后接上新节点tail->next = newnode;}
}

画图分析

疑惑
（1）在函数开头对pplist进行断言，有没有必要对*pplist断言？
没有，这个链表是空的，我们就是要对其进行尾插，才不为空，断言了就不能对空链表进行尾插。
（2）为什么函数传参要传头节点的地址？
我们都知道形参是实参的临时拷贝，形参的改变不影响实参。如果要改变实参，就是传实参的地址。在单链表不为空时，直接传头节点可以实现尾插，但在单链表为空时，则不能实现，如图。

3. 单链表头插
   同样需要考虑两种情况：单链表为空或者单 链表不为空。

// 单链表的头插
void SLTPushFront(SLTNode** pplist, SLTDateType x)
{assert(pplist);//获得一个新的节点，直接将这个功能封装成一个函数SLTNode* newnode = GetNewNode(x);//先考虑普通，再考虑特殊SLTNode* tmp = *pplist;//加入一个临时变量，保存旧的头节点*pplist = newnode;newnode->next = tmp;//最终我们发现，链表为空也适用，不用考虑特殊情况
}//获得新节点
SLTNode* GetNewNode(SLTDateType* x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;
}

4. 单链表尾删

void SLTPopBack(SLTNode** pplist)
{assert(pplist);//空链表就没必要删除//找到尾巴SLTNode* tail = *pplist;SLTNode* tailFront = tail;同时需要记录尾巴前一个节点while (tail->next)//当tail指向最后一个节点时tailFront指向上一个节点{tailFront = tail;}free(tail);tail = NULL;tailFront->next = NULL;
}

是不是这样做就完成了？并没有，当只有一个节点时，就会这个函数就不能实现尾删。

//正确做法
void SLTPopBack(SLTNode** pplist)
{//空链表就没必要删除assert(*pplist);//找到尾巴SLTNode* tail = *pplist;SLTNode* tailFront = tail;同时需要记录尾巴前一个节点//只有一个节点if (tail->next == NULL){*pplist = NULL;free(tail);tail = NULL;return;}while (tail->next)//当tail指向最后一个节点时tailFront指向上一个节点{tailFront = tail;tail = tail->next;}free(tail);tail = NULL;tailFront->next = NULL;
}

5. 单链表头删

void SLTPopFront(SLTNode** pplist)
{//防止为空assert(*pplist);SLTNode* first = *pplist;//记录要删除的头节点*pplist = first->next;//适用于所有特殊情况：包括只有一个节点。free(first);first = NULL;
}

6. 单链表查找

SLTNode* SLTFind(SLTNode* plist, SLTDateType x)
{SLTNode* tmp = plist;while (tmp){if (tmp->data == x){return tmp;}tmp = tmp->next;}return tmp;
}

7. 单链表在pos之后插入

void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);//首先获得一个新节点SLTNode* newnode = GetNewNode(x);newnode->next  = pos->next;pos->next = newnode;
}

疑惑
为什么不在pos位置之前插入？
当pos刚好是第一个节点时，插入新的节点后，由于函数并没有传头节点过来，所以头节点将无法指向新的节点。其实也可以在pos这个位置插入，只要将pos这个位子的数据和插入节点的数据交换一下，然后插入节点继续在pos之后插入，这样数据就像在pos之前的节点插入一样。

8. 单链表删除pos位置之后的值

void SListEraseAfter(SLTNode* pos)
{assert(pos);//要考虑pos指向最后一个节点的情况if (pos->next == NULL){return;}SLTNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

疑惑
为什么不删除pos位置？
当pos是第一个节点时，被释放后，由于函数没有传头节点，头节点将指向野指针，同时无法指向新的链表

9. 单链表的销毁

void SLTDestroy(SLTNode* plist)
{assert(plist);SLTNode* tmp = plist->next ;//用来遍历链表while (tmp){free(plist);plist = tmp;tmp = tmp->next;}free(plist);plist = NULL;
}

分析
当只有一个节点时，tmp = NULL，不进入循环，直接将头节点释放；当有多个节点，tmp进入循环，在tmp = NULL时，plist指向最后一个节点，并没有在while中释放，所以出了循环之后还要释放一次。

---

4.测试