手写单链表（指针）（next域）附图

目录

创建文件：

具体实现：

首先是头插。

注意：一定要注意：再定义tmp时，要给它赋一个初始值（推荐使用 new list_next)

接着是尾插：

随后是中间插：

然后是最简单的改值：

随后是删头：

 一定要注意（size--) 

删中间：

末尾：

oh,对了：

---

我们知道单链表，今天博主（也就是我）自己手写了一个单链表（用指针写的）现在我来分享一下。

创建文件：

我用三个来写（list.h,listfun.h,run.cpp)（run.cpp)用来调试

具体实现：

list.h

#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<limits.h> struct list_next{//链表的一个值 int value; struct list_next *next; }; struct list_make{//一条链表的结构 list_next *head; list_next *tail; int size; }; //void head_add(list_next* &head,int v,int &size);//头插 //void tail_add(list_next* &tail,int v,int &size);//尾插 //void add_node(list_next* head,int p,int v,list_next* tail,int &size);//插入 //void change(list_next* head,int p,int v);//改值 //void head_del(list_next* &head,int &size);//头删 //void del_node(list_next* head,int p,list_next* &tail,int &size);//删除 //void init(list_make &p,int v) //初始化

接下来就是核心的listfun.h

首先是头插。

函数定义：

void head_add(list_next* &head,int v,int &size)

(这里用了引用，不会的童鞋们请看->引用教程 ）

先用图来演示：（左边是值，右边是next域）

上图是原来的样子，tmp是要插入的数。

list_next* tmp=new list_next; tmp->value=v;

 接着把tmp的next改成head。

tmp->next=head;

再把头换成tmp。

head = tmp;

 最后，size+1(因为长度增加了）

size++;

所以头插代码就是：

void head_add(list_next* &head,int v,int &size) { list_next* tmp=new list_next; tmp->value=v; tmp->next=head; head = tmp; size++; } 注意：一定要注意：再定义tmp时，要给它赋一个初始值（推荐使用 new list_next) 接着是尾插：

函数定义：

void tail_add(list_next* &tail,int v,int &size)

还是回到那张图：

把tmp初始化：

​​list_next* tmp=new list_next; tmp->value=v; tmp->next=NULL;

把尾的next变成tmp。

tail -> next=tmp;

把tmp变成尾：

tail = tmp;

最后size++;

整理后代码：

void tail_add(list_next* &tail,int v,int &size) { list_next* tmp=new list_next; tmp->value=v; tmp->next=NULL; tail -> next=tmp; tail = tmp; size++; } 随后是中间插：

函数定义：

void add_node(list_next* head,int p,int v,list_next* &tail,int &size)

几句可以加快速度的代码：

if(p == 0) { head_add(head,v,size); } if(p == size) { tail_add(tail,v,size); return ; }

来正式的：

首先找到第p个：

list_next* tmp=new list_next;//初始化 tmp->value = v; int x=1;//第几个 for(list_next* i=head;i!=NULL;i=i->next,x++) { if(x == p) { ... } }

将第tmp的next=第p个的next：

​​​​​​​

将第p个的next变为tmp:

​​​​​​​就好了：

tmp->next = i->next; i->next=tmp; break;//省时

最后是size++;

void add_node(list_next* head,int p,int v,list_next* &tail,int &size) { if(p == 0) { head_add(head,v,size); } if(p == size) { tail_add(tail,v,size); return ; } list_next* tmp=new list_next; tmp->value = v; int x=1; for(list_next* i=head;i!=NULL;i=i->next,x++) { if(x == p) { tmp->next = i->next; i->next=tmp; break; } } size++; } 然后是最简单的改值：

没啥好说：

void change(list_next* head,int p,int v) { int x=1; for(list_next* i=head;i!=NULL;x++,i=i->next) { if(x == p)//找到第p个值 { i->value=v;//改值 break; } } } 随后是删头：

永恒的那张图：

​​​​​​​

我们可以直接把头变成头的next。

void head_del(list_next* &head,int &size) { head = head->next; size--; }  一定要注意（size--)  删中间：

函数定义：

void del_node(list_next* &head,int p,list_next* &tail,int &size)

加速代码：

if(p == 1) { head_del(head,size); return ; }

永恒之图：

先找到第p-1个，再把第p-1个的next变为第p个的next（也就是第p-1的next的next）。

但是，如果删尾部的话要有个特判，把第p-1个的next设为NULL，tail = 第p-1个。

然后：

就ok了。

void del_node(list_next* &head,int p,list_next* &tail,int &size) { if(p == 1) { head_del(head,size); return ; } int x=1; for(list_next* i=head;i!=NULL;i=i->next,x++) { if(x == p-1) { if(p == size)//如果删尾巴的话 { i->next = NULL;//那么这个就是尾巴，next是NULL tail = i;//尾巴变成i break; } i->next = i->next->next; break; } } size--; }

这时所有的链表操作都好了，上总体代码。

#include"list.h" using namespace std; void head_add(list_next* &head,int v,int &size) { list_next* tmp=new list_next; tmp->value=v; tmp->next=head; head = tmp; size++; } void tail_add(list_next* &tail,int v,int &size) { list_next* tmp=new list_next; tmp->value=v; tmp->next=NULL; tail -> next=tmp; tail = tmp; size++; } void add_node(list_next* head,int p,int v,list_next* &tail,int &size) { if(p == 0) { head_add(head,v,size); } if(p == size) { tail_add(tail,v,size); return ; } list_next* tmp=new list_next; tmp->value = v; int x=1; for(list_next* i=head;i!=NULL;i=i->next,x++) { if(x == p) { tmp->next = i->next; i->next=tmp; break; } } size++; } void change(list_next* head,int p,int v) { int x=1; for(list_next* i=head;i!=NULL;x++,i=i->next) { if(x == p)//找到第p个值 { i->value=v;//改值 break; } } } void head_del(list_next* &head,int &size) { head = head->next; size--; } void del_node(list_next* &head,int p,list_next* &tail,int &size) { if(p == 1) { head_del(head,size); return ; } int x=1; for(list_next* i=head;i!=NULL;i=i->next,x++) { if(x == p-1) { if(p == size)//如果删尾巴的话 { i->next = NULL;//那么这个就是尾巴，next是NULL tail = i;//尾巴变成i break; } i->next = i->next->next; break; } } size--; } 末尾：

细心的小朋友会发现：我再list.h还写了一个struct，make_list，这个结构体包含了一条链表所要的基本属性（头，尾，长度）所以我写了一个初始化函数：

void init(list_make &p,int v) { p.head=new list_next; p.tail=new list_next; p.head->value = v; p.head->next = NULL; p.tail = p.head; p.size = 1; }

最后：listfun.h的代码应是：

#include"list.h" using namespace std; void head_add(list_next* &head,int v,int &size) { list_next* tmp=new list_next; tmp->value=v; tmp->next=head; head = tmp; size++; } void tail_add(list_next* &tail,int v,int &size) { list_next* tmp=new list_next; tmp->value=v; tmp->next=NULL; tail -> next=tmp; tail = tmp; size++; } void add_node(list_next* head,int p,int v,list_next* &tail,int &size) { if(p == 0) { head_add(head,v,size); } if(p == size) { tail_add(tail,v,size); return ; } list_next* tmp=new list_next; tmp->value = v; int x=1; for(list_next* i=head;i!=NULL;i=i->next,x++) { if(x == p) { tmp->next = i->next; i->next=tmp; break; } } size++; } void change(list_next* head,int p,int v) { int x=1; for(list_next* i=head;i!=NULL;x++,i=i->next) { if(x == p)//找到第p个值 { i->value=v;//改值 break; } } } void head_del(list_next* &head,int &size) { head = head->next; size--; } void del_node(list_next* &head,int p,list_next* &tail,int &size) { if(p == 1) { head_del(head,size); return ; } int x=1; for(list_next* i=head;i!=NULL;i=i->next,x++) { if(x == p-1) { if(p == size)//如果删尾巴的话 { i->next = NULL;//那么这个就是尾巴，next是NULL tail = i;//尾巴变成i break; } i->next = i->next->next; break; } } size--; } void init(list_make &p,int v) { p.head=new list_next; p.tail=new list_next; p.head->value = v; p.head->next = NULL; p.tail = p.head; p.size = 1; } oh,对了：

附上一句话和代码：遍历链表元素时：

for(list_next* i=head;i!=NULL;i=i->next)

i就是当前链表的其中一个的元素