一、为什么会有链表
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。就像小火车一样，一节一节的，可以很方便的插入数据，只需记住下一个数据块的地址就可以了
二、代码测试
首先就是单链表是如何开辟的，因为单链表数据不是放在同一个的地址空间中，所以先定义一个结构体如下：
typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode;
定义好了如何去进行头插尾插，先是头插，头插只需要在定义一个节点，然后把他的地址作为链表的头，它里面的next存入之前头的地址就可以，如下代码。
void SListPushFront(SListNode** pplist, SLTDateType x)// 单链表的头插 { assert(pplist); SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; }
BuySListNode是创建的专门去申请空间的函数，代码如下。
SListNode* BuySListNode(SLTDateType x)// 动态申请一个节点 { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc fail"); } newnode->data = x; newnode->next = NULL; return newnode; }
然后在定义一个函数去专门打印，直接定义一个结构体指针为tail然后判断指针是否为空，不是就把下一个数据的地址赋值给tail，然后一直打印，代码如下。
void SListPrint(SListNode* plist)// 单链表打印 { SListNode* tail = plist; while (tail) { printf("%d->", tail->data); tail = tail->next; } printf("NULL\n"); }
还有就是销毁的函数，这个就直接遍历销毁就可以了，代码如下，最后再把头置空。
void SLTDestroy(SListNode** pphead)//销毁 { SListNode* cur = *pphead; while (cur) { SListNode* tmp = cur->next; free(cur); cur = tmp; } *pphead = NULL; }
这时候就可以测试一下运行结果如图
然后就是尾插，尾插就是建立一个数据，然后两个节点的地址交换下，也就是把刚创建的数据块地址赋值给上一个节点的next，把刚创建的数据里的next置空，还需要判断下链表里是否有数据，所以先要判断一下是否为空，代码如下。
void SListPushBack(SListNode** pplist, SLTDateType x)// 单链表尾插 { assert(pplist); SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* tail = *pplist; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
测试运行结果如下
然后就是头删和尾删，头删就是把第一个节点删了，然后把第二个节点的地址赋值给头，然后之前的头释放内存，如果只有一个数据时直接释放然后置空，代码如下。
void SListPopFront(SListNode** pplist)// 单链表头删 { assert(pplist); assert(*pplist); if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SListNode* head = (*pplist)->next; free(*pplist); *pplist = head; } }
测试运行结果如下
尾删就是把最后一个节点的地址释放，然后倒数第二个的next中的地址置空，如果就剩一个时就是直接释放，把地址置空就行，代码如下。
void SListPopBack(SListNode** pplist)// 单链表的尾删 { assert(pplist); assert(*pplist); if ((*pplist)->next== NULL) { free(*pplist); *pplist = NULL; } else { SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
接着就是查找，这个直接遍历就行，找到了直接返回地址，然后就可以直接在这个地址上修改数据，可以相当于这个函数就是查找和修改结合了，然后这里和中间插入配合使用了，代码如下。
SListNode* SListFind(SListNode* plist, SLTDateType x)// 单链表查找 { SListNode* cur = plist; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SListInsertAfter(SListNode* pos, SLTDateType x)// 在pos的后面插入 { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } void SListEraseAfter(SListNode* pos)// 删除pos位置 { assert(pos); assert(pos->next); SListNode* next = pos->next; pos->next = next->next; free(next); } void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)// 在pos的前面插入 { assert(pphead); assert(pos); if (*pphead == pos) { SListPushFront(pphead, x); } else { SListNode* per = *pphead; while (per->next != pos) { per = per->next; } SListNode* newnode = BuySListNode(x); newnode->next = pos; per->next = newnode; } } void SLTErase(SListNode** pphead, SListNode* pos)// 删除pos位置 { assert(pphead); assert(pos); if (*pphead == pos) { SListPopFront(pphead); } else { SListNode* per = *pphead; while (per->next != pos) { per = per->next; } per->next = pos->next; free(pos); } }
上面是在pos位置前面和后面插入的两个写法，以及删除的写法，在前写入就是找到pos位置前面的一个节点，然后把新节点的地址赋值给他，然后新节点存入pos的地址，在后写入，就简单了，就是直接找到pos把新建立的节点地址赋值给pos，pos后面的地址赋值给新的节点，删除也是差不多原理，前删就是把pos节点前删除，然后把前面的地址赋值给pos，后删就是把后面的地址赋值给pos，测试结果如图
pos前删除
pos后删除
