链表与数组：
数组------>需要一段连续的内存空间来实现存储功能，对内存要求比较高!
链表------>不需要一段连续的内存空间，通过" 指针 "将零散内存单元串联！
图解链表与数组：
单链表：
习惯把第一个结点叫作头结点，把最后一个结点叫作尾结点！
链表的创建：
#includeusing namespace std;struct Node{ int data;//值域，存放数据值 Node *next;//指针域，存放指向下一个节点的地址};//结构体；号不能少//定义链表的头、尾以及游标指针Node *head,*tail,*p;int main(){ int n; cin>>n;//存入链表的数据值 //第一步：初始化链表，头既是尾，尾既是头！ head=new Node; tail=head; //第二步：定义规则，实现链表创建 while(n!=-1){ p=new Node; p->data=n; //第三步：实现链接功能,新节点地址放入链表尾部当中的指针域 tail->next=p; //第四步：链表尾巴向后移动 tail=p; //第五步：链表尾巴地址域置空 tail->next=NULL; //第六步：输入要保存的数据值,同时也是结束的标志 cin>>n; }}
链表的遍历：
//第一步：拿到车头后第一个节点，链表需要从头开始遍历,通过指针域一个个遍历节点数据值p=head->next;//第二步：判断当前节点是否是尾节点while(p->next!=NULL){ cout<data<<""; //第三步：节点向后移动 p=p->next;}//第四步：如果跳出循环说明遇到了尾节点，那么就需要把尾节点的数据值打印输出cout<data<
空链表危害：
如果什么数据值都没有保存，直接遍历，那么就会因为最开始没有对tail->next或者head->next没有进行初始化为NULL，造成指针域随机指向。
链表的创建和遍历完整程序：
#includeusing namespace std;struct Node{ int data;//值域，存放数据值 Node *next;//指针域，存放指向下一个节点的地址};//结构体；号不能少//定义链表的头、尾以及游标指针Node *head,*tail,*p;int main(){ int n; cin>>n;//存入链表的数据值 //第一步：初始化链表，头既是尾，尾既是头！ head=new Node; tail=head; //防止出现空链表 tail->next=NULL; //第二步：定义规则，实现链表创建 while(n!=-1){ p=new Node; p->data=n; //第三步：实现链接功能,新节点地址放入链表尾部当中的指针域 tail->next=p; //第四步：链表尾巴向后移动 tail=p; //第五步：链表尾巴地址域置空 tail->next=NULL; //第六步：输入要保存的数据值,同时也是结束的标志 cin>>n; } if(head->next!=NULL){ //第一步：拿到车头后第一个节点，链表需要从头开始遍历,通过指针域一个个遍历节点数据值 p=head->next; //第二步：判断当前节点是否是尾节点 while(p->next!=NULL){ cout<data<<" "; //第三步：节点向后移动 p=p->next; } //第四步：如果跳出循环说明遇到了尾节点，那么就需要把尾节点的数据值打印输出 cout<data<<endl; }else{ cout<<"我是空链表"<<endl; }}
功能测试空链表过滤：
链表的插入：
代码功能实现：
//如果想要实现插入x,那么需要明确前面的b(pre)和后面c(next)void insert_data(int v,int position){ Node *pre=head,*is; int k=0;//负责记录要插入的位置0或者1都行 //第一步：判断是否为空链表，如果为空链表那么直接插入 if(head->next!=NULL){ p=head;//1对应--->p=head->next; //第二步：当前节点不是尾节点，那么遍历链表 while(p->next!=NULL){ k++; //第三步：如果刚好适合插入，那么直接前后链接 if(k==position){ is=new Node; is->data=v; is->next=p; pre->next=is; break; }else{ pre=p; p=p->next; } } //如果链表长度小于插入位置 if(k<5){ is=new Node; is->data=v; is->next=NULL; pre->next=is; } }else{//否则插入位置是在尾部插入 is=new Node; is->data=v; is->next=NULL; pre->next=is; } }
链表的删除：
代码功能实现：
//如果想要实现删除b,那么需要明确前面的a(pre)和后面c(next)void delete_data(int v){ Node *pre=head; //第一步：判断是否为空链表 if(head->next!=NULL){ p=head->next; //第二步：当前节点不是尾节点 while(p->next!=NULL){ //第三步：如果满足条件，那么删除p,pre直接和next链接 if(p->data==v){ pre->next=p->next; delete p; p=pre->next; }else{ //如果不满足条件，那么p就成为了下一个pre，p->next就成为了下一个p pre=p; p=p->next; } } //第四步：如果是尾节点 if(p->data==v){ delete p; pre->next=NULL; } }else{ cout<<"我是空链表，不能完成删除！"< } }
链表与数组的性能对比：
其他链表类型：
循环链表：
双向链表：
双向循环链表：