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;
}