1.引入单链表

顺序表对于中间或者头部的删除，时间复杂度为O(N)，增容需要申请新的空间，拷贝数据，释放就空间，消耗。增容一般是2倍的增长，会有空间的浪费。为了解决这些问题，引入了单链表。

2.单链表

链表是一种物理存储结构上非连续的，非顺序的存储结构，逻辑结构上通过链表中指针链接实现连续性。类似火车头，节。与顺序表不同的是，链表的每一结点都是独立申请的空间，结点一般包含当前结点要保存的数据与下一个结点的地址，一般是从堆上申请。

struct SListNode
{
int data;
struct SListNode* next;
};

这就是一个结点的结构体。

3.单链表的实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int sl;
typedef struct slist
{sl data;struct slist* next;
}listnode;
//申请一个节点
listnode* buylistnode(sl x)
{listnode* node=(listnode*)malloc(sizeof(listnode));if(node==NULL){perror("buylistnode");exit(-1);}node->next=NULL;node->data=x;return node;
}
//单链表打印
void listprint(listnode* p)
{while(p){printf("%d",p->data);p=p->next;}
}
//单链表尾插，为了改变真正的链表，要用二重指针。
//一重指针保存了数据的地址，我们要改变的是指针本身，不是它保存的地址，而是它本身的地址
void slpushback(listnode** pp,sl x)
{assert(pp);//头结点本身的地址不能为空，但是头结点保存的地址可以为空（起初链表为空）listnode* newnode=buylistnode(x);
//如果只有一个节点，那么直接在后面插入if(*pp==NULL){
*pp=newnode;}else{listnode* tail=*pp;while(tail->next){tail=tail->next;}tail->next=newnode;}
}
//单链表头插
void slpushfront(listnode** pp,sl x)
{assert(pp);listnode* newnode=buylistnode(x);newnode->next=*pp;*pp=newnode;
}
//单链表尾删
void slpopback(listnode** pp)
{assert(pp&&*pp);listnode* prev=NULL;listnode* tail=*pp;while(tail->next){
prev=tail;
tail=tail->next;}if(prev==NULL){*pp=NULL;}else{prev->next=NULL;}free(tail);
}
//单链表头删
void slpopfront(listnode** pp)
{assert(pp&&*pp);
//头结点本身的地址不能为空，而且保存的地址也不能为空，不然
//（*pp）->next对空指针解引用就错了listnode* next=(*pp)->next;free(*pp);*pp=next;
}
//单链表查找
listnode* slfind(listnode* p,sl x)
{while(p){if(p->data==x){return p;}p=p->next;}return NULL;
}
//单链表在pos之后插入
void slinsertafter(listnode* pos,sl x)
{assert(pos);listnode* newnode=buylistnode(x);newnode->next=pos->next;pos->next=newnode;
}
//删除pos后的值
void sleraseafter(listnode* pos)
{assert(pos&&pos->next);listnode* n=pos->next;pos->next=n->next;free(n);
}
//pos之前插入
void slinsertfront(listnode** pp,listnode* pos,sl x)
{assert(pp);if(pos==NULL){slpushback(pp,x);return;}listnode* newnode=buylistnode(x);if(*pp==pos){newnode->next=*pp;*pp=newnode;}else{listnode* prev=*pp;while(prev!=NULL&&prev->next!=pos){prev=prev->next;}newnode->next=pos;prev->next=newnode;}
}
//删除pos位置
void slerasepos(listnode** pp,listnode* pos)
{assert(pp&&pos);if(*pp==pos){*pp=pos->next;free(pos);}else{listnode* prev=*pp;while(prev!=NULL&&prev->next!=pos){prev=prev->next;}assert(prev!=NULL);prev->next=pos->next;free(pos);}
}
//删除整个
void slerase(listnode**pp)
{assert(pp);listnode* p=NULL;while(*pp){p=*pp;*pp=(*pp)->next;free(p);}
}
int main()
{return 0;
}