提示：文章参考王道的课程，相当于课程笔记
目录
一、单链表的定义及初始化
1、定义
2、初始化
1)不带头结点的单链表
2)带头节的单链表
二、单链表插入和删除
1)插入
1、按位序插入（带头结点）
2、按位插入（不带头结点）
3、指定结点的后插操作
4、指定结点的前插操作
2）删除
1、按位序删除（带头结点）
2、指定结点删除
3、指定最后结点的删除
三、查找
1）按位查找
2）按值查找
四、建立
1）头插法
2）尾插法
六、补充求单链表长度
一、单链表的定义及初始化
首先介绍一个关键字typedef ——数据类型重命名
typedef < 数据类型> <别名>
typedef struct LNode LNode
1、定义
typedef sturct LNode{ //定义单链表结点类型 ElemType date ; //每个结点存放一个数据元素 struct LNode *next; //指针指向下一个结点}LNode, *LinkList;typedef LNode{ //定义单链表结点类型 ElemType date ; //每个结点存放一个数据元素 struct LNode *next; //指针指向下一个结点};typedef struct LNode LNode;typedef struct LNOde *LinkList;//上面俩个是等价的struct LNode *p = (struct LNode*) malloc(sizeof(struct LNode)); /*增加一个新结点：在内存中申请一个结点所需空间，并用指针p指向这个结点 */要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个节点
LNode *L ; //声明一个指向单链表第一个结点的指针 （强调这是一个结点用LNode*）
或： LinkList L； //声明一个指向单链表的第一个结点的指针 （强调这是一个单链表LinkList）
2、初始化
1)不带头结点的单链表
bool InitList(LinkList &L) //初始化空链表{ L = NULL; //空表没有任何结点 return true; }void test(){ LinkList L ; //声明一个指向单链表的指针 //初始化一个空表 InitList (L);}判断是否为空
bool Empty(LinkList L){ if(L == NULL) return true; else return false;}//或：bool Empty(LinkList L){ return (L == NULL);}2)带头节的单链表
//初始化一个单链表（带头结点）bool InitList (LinkList &L){ L = (LNode * ) malloc (sizeof(LNode)); //分配一个头结点 if (L == NULL) //内存不足分配失败 return false; L->next = NULL; return true;}判断是否为空
bool Empty(LinkList L){ if(L->next == NULL) return true; else return false;}二、单链表插入和删除
1)插入
1、按位序插入（带头结点）
//在第i个位置插入元素ebool ListInsert(LinkList &L, int i,,ElemType e){ if( i < 1) return false; LNode *p; //指针p指向当前扫描借点钱 int j = 0; //当前p指向是第几个结点 p = L; L指向头结点，头结点是第0个结点 while( p! = NULL && j < i - 1) //循环找到第i-1个结点 { p = p->next; j ++; } if(p == NULL) //i值不合法 return false; LNode *s = (LNode*)malloc(sizeof(LNode)); s->date = e; s->next = p->next; p->next = s; //将结点s连到p之后 return true;}2、按位插入（不带头结点）
bool ListInsert(LinkList &L, int i,,ElemType e){ if( i < 1) return false; if(i == 1){ LNode *s = (LNode *s)malloc(sizeof(LNode)); s->date = e; s->next = L; L = s; return true; } LNode *p; //指针p指向当前扫描借点钱 int j = 0; //当前p指向是第几个结点 p = L; L指向头结点，头结点是第0个结点 while( p! = NULL && j < i - 1) //循环找到第i-1个结点 { p = p->next; j ++; } if(p == NULL) //i值不合法 return false; LNode *s = (LNode*)malloc(sizeof(LNode)); s->date = e; s->next = p->next; p->next = s; //将结点s连到p之后 return true;}3、指定结点的后插操作
bool InsertNextNode (LNode *p ,Elemtype e){ if( p == NULL) return false； LNode *s = (LNode *) malloc(sizeof(LNode)); if (s == NULL) //内存分配失败 return false; s->date = e; //用结点s保存数据元素e s->next = p->next; p->next = s; //将结点s连接到p之后 return true;}4、指定结点的前插操作
bool InsertPriorNode (LNode *p,ElemType e){ if(p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if(s == NULL) return false; s->next = p->next; p->next = s; //新节点s连到p之后 s->date = p->date; //将p之中元素复制到s中 p->date = e; //p中元素覆盖W为e}//时间复杂度为O(1)2）删除
1、按位序删除（带头结点）
//按位序删除（带头结点）bool ListDelete(LinkList &L,int i,ElemType &e){if(i<1) return false;LNode *p; //指针p指向当前扫描到的节点int j = 0; // 当前p指向的是第几个节点p = L; //L指向头节点，头节点是第0个节点（不存数据）while(p!=NULL && j<i-1){ //循环到第i-1个节点 p = p->next;j++;} if(p==NULL) return false; //i值不合法 if(p->next == NULL) return false; //第i-1个节点之后没有其他节点 LNode *q = p->next; //q指向被删除的节点 e = q->data;p->next = q->next;free(q);return true;} 2、指定结点删除
//指定节点的删除bool DeleteNode(LNode *p){if(p==NULL) return false;LNode *q = p->next; //q指向*p的后继节点 p->data = p->next->data; //p的后继节点数据赋值给p p->next = q->next; //q节点从链中断开 free(q); //释放 return true;}3、指定最后结点的删除
//指定节点的删除bool DeleteNode(LNode *p){if(p==NULL) return false;LNode *q = p->next; //q指向*p的后继节点 p->data = p->next->data; //p的后继节点数据赋值给p p->next = q->next; //q节点从链中断开 free(q); //释放 return true;}
三、查找
1）按位查找
//按位查找，返回第i各元素带头节点LNode * GetElem(LinkList L,int i){if(i<0){return NULL;}LNode *p; // 指针p指向当前扫描到的结点int j = 0;p = L; //L指向头结点 , L是第0个结点（不存放数据）while(p!=NULL && j < i){ //循环到第i个结点 p = p->next;j++;}return p; } 2）按值查找
//按值查找，返回e元素//带头节点LNode * GetElem(LinkList L,ElemType e){LNode *p = L->next; //从第一个结点开始查找数据域为e的结点while(p!=NULL && p->data != e){p = p -> next;} return p; } 四、建立
1）头插法
//头插法 LinkList List_HeadInsert(LinkList &L){int x; //假设ElemType为整型 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 LNode *s; //r为表尾指针L->next = NULL; //初始尾空链表 （必须初始化） scanf("%d",&x);while(x!=9999) {s = (LNode*)malloc(sizeof(LNode));s->next = L->next;s->data = x;L->next = s; //头结点指向新的结点 scanf("%d",&x); } return L; } 2）尾插法
typedef struct LNode{int data;struct LNode *next; }LNode,*LinkList;//初始化一个单链表（带头节点）bool InitList(LinkList &L){L = (LNode*)malloc(sizeof(LNode));if(L == NULL){return false; //内存不足分配失败 }L->next = NULL; //头结点之后暂时没有结点 return true; } //尾插法建立单链表： 初始化单链表长度/*while 循环{每次取一个数据元素eListInsert(L,length+1,e) ;length++;} 时间复杂度：O（n2） */ LinkList List_TailInsert(LinkList &L){int x; //假设ElemType为整型 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 LNode *s,*r=L; //r为表尾指针scanf("%d",&x);while(x!=9999) {s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s; //r始终指向表尾 scanf("%d",&x); }r->next = NULL; //尾结点置空 return L; } int main(){LinkList L; //声明一个指向单链表的指针InitList(L);//初始化一个空表 List_TailInsert(L);return 0;} 六、补充求单链表长度
//求单链表的长度int Length (LinkList L){int len = 0; //统计表长LNode *p = L;while(p->next != NULL){p = p->next;len++;} return len;}