查找：因为线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为
插入和删除：因为线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为
但是，如果要在单链表中进行前插或者删除操作，由于要从头查找前驱结点，所耗时间复杂度为
我觉得开头很重要：
typedef struct LNode{ ElemType data; //数据域，ElemType作用和int一样 struct LNode *next; //指针域 }LNode,*LinkList; //*LinkList为LNode类型的指针注意：上式是一个宏定义，相当于对结构体类型起了一个别名，LNode *与LinkList,两者本质上是等价的。
只不过（1）通常习惯上用LinkList定义单链表，强调定义的是单链表的头指针
（2）用LNode *定义指向单链表中任意结点指针变量
综合（1）（2） LNode *p <==> LinkList p
注意区分指针变量结点变量两个不同的概念，若用LNode *p语句定义，则p代表指针变量，*p代表结点变量
单链表的头插法（前插法）图示：
核心的代码有三句 ：
p->data = a; //p为新生成的结点,并输入数据值为a p->next = L->next //使新生成的结点的指针域始终指向空（开始头指针的指针域即是空） L->next = p //L为头结点，使新生成的新结点一直在头结点的紧邻后面下面贴上完整的代码（输入五个值，头插法建立链表逆序输出）：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; typedef struct LNode{ char data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; //*LinkList为LNode类型 void Reverse(LinkList &L,int n) { L = new LNode; //生成头结点，用头指针L指向它 L->next = NULL; //下面for循环是使用头插法创建单链表 for(int i=0;i<n;i++) { LinkList p; p = new LNode; //生成新结点 cin>>p->data; //输入元素值 p->next = L->next; //和下面一句一起插入到表头 L->next = p; } //下面这个while循环的作用是输出单链表中结点的值 while(L->next) { cout<<L->next->data<<" "; L->next = L->next->next; } } int main() { LinkList List; Reverse(List,5); return 0; }运行结果：
单链表的头插法（前插法）图示：
核心代码四句：
p = new LNode; //生成新结点 cin>>p->data; //输入数据值 p->next = NULL; //和下面一句一起实现插入到表尾的操作 r->next = p; r = p; //r指向新的尾结点完整代码的实现（输入五个值，尾插法建立链表顺序输出）：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; typedef struct LNode{ char data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; //*LinkList为LNode类型 LinkList r,p; void print(LinkList &L,int n) { L = new LNode; L->next=NULL; r = L; //尾指针r指向头结点 //下面for循环是使用尾插法创建单链表 for(int i=0;i<n;i++) { p = new LNode; //生成新结点 cin>>p->data; //输入数据值 p->next = NULL; //和下面一句一起实现插入到表尾的操作 r->next = p; r = p; //r指向新的尾结点 } //下面这个while循环的作用是输出单链表中结点的值 while(L->next) { cout<<L->next->data<<' '; L->next = L->next->next; } } int main() { LinkList lis; print(lis,5); return 0; }运行结果：
