单链表基本操作函数
一、单链表初始化
Status InitList(LinkList &L)// { L=new LNode; if(!L) return(OVERFLOW); L->next=NULL; return OK; }
Status表状态，函数接收的返回值为OK或ERROR。
new为C++的操作符，在这里即定义一个新的指针L。
OVERFLOW字面意思为溢出，在函数头部分应该定义为-1，在这里想表示的是指针所指向的空间申请失败了。
NULL是指空指针，这里可以理解为L的下一个位置是空的。
大致思路为先定义一个新的指针L，如果创建失败的话，返回OVERFLOW（-1），成功的话L的位置就是空指针的前一个，或者可以理解为L的下一个是空指针。
二、单链表取值
Status GetElem(LinkList &L,int i,ElemType &e)//取值 { int j = 1; LNode *p; p = L->next; while(p && j<i) { p=p->next; j++; } if((!p) || j>i) return ERROR; e=p->data; return OK; }
单链表做取值操作只能从头开始依次向下寻找，所以说单链表是顺序存储，对于取值操作来说，顺序表比单链表更为适用，单链表取值操作时间复杂度O（n），而顺序表取值操作时间复杂度O（1）。
三、单链表插入
Status ListInsert(LinkList &L,int i,ElemType e)//插入 { LNode* p = L; int j = 0; while(p && j<i-1) { p=p->next; j++; } if(!p || j>i+1) return ERROR; LNode* s = new LNode; s->data = e; s->next = p->next; p->next = s; return OK; }
插入的核心算法就是s->next = p->next; p->next = s;这个前后顺序是不可以改变的，因为如果更改的话，s的下一个位置就找不到了，必须利用p->next更改之前找到s的下一个位置（p->next），这样才能完成插入操作。
取值操作中我们说顺序表比单链表更为适用，是因为单链表取值操作时间复杂度O（n），而顺序表取值操作时间复杂度O（1），而在插入操作中，无疑使用单链表更为合适，在顺序表中执行插入删除等动作时，还需要移动其他元素，而在单链表中就不存在这样的问题，只需要更改两个指针就可以了。
四、单链表删除
Status ListDelete(LinkList &L,int i)//删除 { LNode *q; LNode* p=L; int j = 0; while(p->next && j<i-1) { p = p->next; j++; } if(!(p->next) || j>i-1) return ERROR; q = p->next; p->next = q->next; delete q; return OK; }
q = p->next; 这个操作其实可以和插入那里一起理解，也是要提前保存一下p->next的地址，否则在未来改变指针后，这个地址就找不到了。
这里p->next = q->next;实际上就是p->next =p->next->next;相信这样写的话更助于理解，即将p->next直接连接到p->next->next上，之前p->next的那个位置的元素是不是就被删除到表外了呢，最后再将提前存储好的q（p->next）删除就好了
五、单链表按值插入
Status SeqInsert(LinkList &L,ElemType e)//按值插入 { LNode* p= L->next; int i=0; while(p && p->data < e) { p = p->next; i++; } ListInsert(L,i+1,e); }
前提时这个单链表是按大小排列好的，相信这个大家都可以看懂，我也就不多赘述了哈。
单链表完整程序
#include<stdio.h> #include<stdlib.h> #include<iostream> using namespace std; #define MAXSIZE 8 #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef int Status; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; }LNode,*LinkList; Status InitList(LinkList &L)//初始化 { L = new LNode; if(!L) return(OVERFLOW); L->next = NULL; return OK; } void PrintList(LinkList &L)//输出 { LNode* p; p = L->next; while(p) { cout<<p->data<<","; p = p->next; } cout<<endl; } Status GetElem(LinkList &L,int i,ElemType &e)//取值 { int j = 1; LNode* p; p = L->next; while(p && j<i) { p = p->next; j++; } if((!p) || j>i) return ERROR; e = p->data; return OK; } Status ListInsert(LinkList &L,int i,ElemType e)//插入 { LNode* p = L; int j = 0; while(p && j<i-1) { p = p->next; j++; } if(!p || j>i+1) return ERROR; LNode* s = new LNode; s->data = e; s->next = p->next; p->next = s; return OK; } Status ListDelete(LinkList &L,int i)//删除 { LNode* q; LNode* p = L; int j = 0; while(p->next && j<i-1) { p = p->next; j++; } if(!(p->next) || j>i-1) return ERROR; q = p->next; p->next = q->next; delete q; return OK; } Status Len(LinkList &L)//求表长 { int i=0; LNode* p=L; while(p) { p = p->next; i++; } return i-1; } Status SeqList(LinkList &L)//排序 { int i,j,a; LNode *q,*p,*tail; for(i=0;i<Len(L)-1;i++) { a = Len(L)-i-1; q = L->next; p = q->next; tail = L; while(a--) { if(q->data>p->data) { q->next = p->next; p->next = q; tail->next = p; } tail = tail->next; q = tail->next; p = q->next; } }PrintList(L); } Status SeqInsert(LinkList &L,ElemType e)//按值插入 { LNode* p = L->next; int i = 0; while(p && p->data<e) { p = p->next; i++; } ListInsert(L,i+1,e); } void CreateList_H ( LinkList &L, int n)//头插法 { L = new LNode; L->next = NULL; LNode* p; for(int i = 0; i<n; i++) { p = new LNode; cin>>p->data; p->next = L->next; L->next = p; } } int main() { LinkList L; InitList(L); cout<<"请输入链表元素:"; CreateList_H(L,6); PrintList(L); if(ListInsert(L,1,3)==OK)PrintList(L); if(ListInsert(L,8,21)==OK)PrintList(L); if(ListInsert(L,4,15) ==OK)PrintList(L); if(ListInsert(L,12,99) ==OK)PrintList(L); if(ListDelete(L,1) ==OK)PrintList(L); if(ListDelete(L,9) ==OK)PrintList(L); if(ListDelete(L,12) ==OK)PrintList(L); SeqList(L); SeqInsert(L,20);PrintList(L); SeqInsert(L,50);PrintList(L); return 0; }
总结
以上就是单链表最最最基本的操作啦，当然大家发现完整程序里面还有单链表排序，头插法，包括尾插法的一系列操作我会在下一篇文章继续分享😁😁😁
