链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。
- 中文名
- 链表
- 外文名
- linked list
- 分 类
- 计算机数据结构
- 构 成
- 一系列结点组成
- 类 型
- 计算机结构术语
特点
播报编辑
根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向，反向标记加在边上可能会更方便。
基本操作
播报编辑
建立
第一行读入n，表示n个数
第二行包括n个数
以链表的形式存储输出这些数
program project1;
type
point=^node;
node=record
data:longint;
next:point;
end;
var
i,n,e:longint;
p,q,head,last:point;
begin
write('Input the number count:');
readln(n);
i:=1;
new(head);
read(e);
head^.data:=e;
head^.next:=nil;
last:=head;
q:=head;
while i<n do
begin
inc(i);
read(e);
new(p);
q^.next:=p;
p^.data:=e;
p^.next:=nil;
last:=p;
q:=last
end;
//建立链表
q:=head;
while q^.next<>nil do
begin
write(q^.data,'');
q:=q^.next;
end;
write(q^.data);
//输出
readln;
readln
end.
删除
在以z为头的链表中搜索第一个n，如果找到则删去，返回值为1，否则返回0
function delete(n:longint;var z:point):longint;
var
t,s:point;
begin
t:=z;
while(t^.next<>nil)and(t^.data<>n)do
begin
s:=t;
t:=t^.next;
end;
if t^.data<> nthen exit(0);
s^.next:=t^.next;
dispose(t);
exit⑴
end;
查找
类似于删除，只需要找到不删即可
插入
插入，在以zz为头的链表第w个的前面插入nn元素，函数返回值正常是0，如果w超过了链表的长度，函数返回链表的长度
function insert(w,nn:longint;var zz:point):longint;
var d:longint;v,vp,vs:point;
begin
v:=zz;
for d:=1 to w do
if v^.next=nil
then exit(d)
else
begin
vp:=v;
v:=v^.next;
end;
new(vs);
vs^.data:=nn;
vp^.next:=vs;
vs^.next:=v;
exit(0)
end;
链表函数
播报编辑
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
usingnamespacestd;
structNode
{
intdata;//数据域
structNode*next;//指针域
};
/*
Create
*函数功能：创建链表.
*输入：各节点的data
*返回值：指针head
*/
Node*Create()
{
intn=0;
Node*head,*p1,*p2;
p1=p2=newNode;
cin>>p1->data;
head=NULL;
while(p1->data!=0)
{
if(n==0)
{
head=p1;
}
else
p2->next=p1;
p2=p1;
p1=newNode;
cin>>p1->data;
n++;
}
p2->next=NULL;
returnhead;
}
/*
insert
*函数功能：在链表中插入元素.
*输入：head链表头指针，p新元素插入位置，x新元素中的数据域内容
*返回值：无
*/
voidinsert(Node*head,intp,intx)
{
Node*tmp=head;//for循环是为了防止插入位置超出了链表长度
for(inti=0;i<p;i++)
{
if(tmp==NULL)
return;
if(i<p-1）
tmp=tmp->next;
}
Node*tmp2=newNode;
tmp2->data=x;
tmp2->next=tmp->next;
tmp->next=tmp2;
}
/*
del
*函数功能：删除链表中的元素
*输入：head链表头指针，p被删除元素位置
*返回值：被删除元素中的数据域.如果删除失败返回-1
*/
intdel(Node*head,intp)
{
Node*tmp=head;
for(inti=0;i<p;i++)
{
if(tmp==NULL)
return-1;
if(i<p-1）
tmp=tmp->next;
}
intret=tmp->next->data;
tmp->next=tmp->next->next;
returnret;
}
voidprint(Node*head)
{
for(Node*tmp=head;tmp!=NULL;tmp=tmp->next)
printf("%d",tmp->data);
printf("\n");
}
intmain()
{
Node*head;
head=newNode;
head->data=-1;
head->next=NULL;
return0;
}
例子
#include<iostream>
#defineNULL0
structstudent
{
longnum;
structstudent*next;
};
intmain()
{
inti,n;
student*p=(structstudent*)malloc(sizeof(structstudent));
student*q=p;
printf("输入几个值");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&(q->num));
q->next=(structstudent*)malloc(sizeof(structstudent));
q=q->next;
}
printf("值第几个");
intrank;
scanf("%d%d",&(q->num),&rank);
student*w=p;
for(i=1;i<rank-1;i++)
{
w=w->next;
}
q->next=w->next;
w->next=q;
for(i=1;i<=n+1;i++)
{
printf("%d",p->num);
p=p->next;
}
return0;
}//指针后移麻烦链表形式循环链表
循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。
在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。
应用举例概述
约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。例如：n = 9,k = 1,m = 5
参考代码
#include<stdio.h>
#include<malloc.h>
#defineN41
#defineM5
typedefstructnode*link;
structnode
{
intitem;
linknext;
};
linkNODE(intitem,linknext)
{
linkt=malloc(sizeof*t);
t->item=item;
t->next=next;
returnt;
}
intmain(void)
{
inti;
linkt=NODE（1,NULL);
t->next=t;
for(i=2;i<=N;i++)
t=t->next=NODE(i,t->next);
while(t!=t->next)
{
for(i=1;i<M;i++)
t=t->next;
t->next=t->next->next;
}
printf("%d\n",t->item);
return0;
}
其他相关结语与个人总结
插入操作处理顺序：中间节点的逻辑，后节点逻辑，前节点逻辑。按照这个顺序处理可以完成任何链表的插入操作。
删除操作的处理顺序：前节点逻辑，后节点逻辑，中间节点逻辑。
按照此顺序可以处理任何链表的删除操作。
如果不存在其中的某个节点略过即可。
上面的总结，大家可以看到一个现象，就是插入的顺序和删除的顺序恰好是相反的，很有意思！
操作
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedefstructSlist
{
intdata;
structSlist*next;
}
SLIST;
SLIST*InitList_Sq()/*初始化函数*/
{
inta;
SLIST*h,*s,*r;
h=(SLIST*)malloc(sizeof(SLIST));/*建立头指针，头指针不可以更改！！！*/
r=h;
if(!h)
{
printf("分配失败");
exit(0);
}
scanf("%d",&a);
for(;a!=-1;)
{
s=(SLIST*)malloc(sizeof(SLIST));/*每次都开辟一个结点空间并赋值*/
s->data=a;
r->next=s;
r=s;
scanf("%d",&a);
}
r->next='\0';
returnh;
}
voidprint_list(SLIST*finder)/*打印函数*/
{
while(finder!='\0')
{
printf("->%d",finder->data);
finder=finder->next;
}
printf("->end\n");
}
intDeleteNode(SLIST*killer)//删除节点函数
{
inti,j=0;
SLIST*p,*q;
intx;
p=killer;
q=killer->next;
printf("请输入您要删除的节点序号：");
scanf("%d",&i);
while((p->next!='\0')&&(j<i-1））
{
p=p->next;
j++;
q=p->next;
}
if(p->next=='\0'||j>i-1）
{
printf("\nerror");
return-1;
}
else
{
p->next=q->next;
x=q->data;
free(q);
returnx;
}
}
voidInsert_Node(SLIST*jumper)//插入函数，本算法为前插结点法
{
intt,e,j=0;
SLIST*p,*q;
p=jumper;
printf("请输入要插入位置的序号：");
scanf("%d",&t);
printf("请输入要插入的元素：");
scanf("%d",&e);
while(p->next!='\0'&&j<t-1）
{
j++;
p=p->next;
}
if(p=='\0'||j>t-1）
printf("插入的目的位置不存在");
else
{
q=(SLIST*)malloc(sizeof(SLIST));
q->data=e;
q->next=p->next;
p->next=q;
}
}
voidLocate_List(SLIST*reader)//查找值为e的元素
{
inte,i=0;
SLIST*p;
p=reader;
printf("请输入要查找的元素：");
scanf("%d",&e);
while(p->next!='\0'&&p->data!=e)
{
i++;
p=p->next;
}
if(p->data==e)
printf("此元素在%d号位置\n",i);
else
printf("无此元素！");
}
voidmain()
{
inti,k,y;
SLIST*head;
printf("\n1.建立线性表");
printf("\n2.在i位置插入元素e");
printf("\n3.删除第i个元素，返回其值");
printf("\n4.查找值为e的元素");
printf("\n5.结束程序运行");
printf("\n===================================================");
printf("请输入您的选择：");
scanf("%d",&k);
switch(k)
{
case1:
{
head=InitList_Sq();
print_list(head->next);
}break;
case2:
{
head=InitList_Sq();
print_list(head->next);
Insert_Node(head);
print_list(head->next);
}
break;
case3:
{
head=InitList_Sq();
print_list(head->next);
y=DeleteNode(head);
print_list(head->next);
if(y!=-1）
printf("被删除元素为：%d",y);
}break;//头结点不算，从有数据的开始算第一个
case4:
{
head=InitList_Sq();
print_list(head->next);
Locate_List(head);
}break;
}
}
使用方法简介：运行程序后，先打数字1，然后回车，这样就可以先创建一个新的链表，比如你要创建一个
4->5->6->7这样一个链表，你就输入数字4回车，输入5回车，输入6回车，输入7回车，最后输入-1回车，这个-1就是告诉程序到此为止的标志
假如你要使用插入的功能位置插入，就输入3，回车，程序会问你插入的数值是什么，比如你要插入999，然后回车，999就被插进去了
其他的功能都大同小异
