链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。

特点

扩展

链表基本操作（pascal语言）(建立一个链表 基本操作-删除 基本操作-查找 基本操作-插入)

三个链表函数（C/C++语言描述）

结语与个人总结

两种链表形式

链表的应用举例

VC6.0下链表的查插删改

概况

链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个用来指向明上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

特点

线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如概述旁的图所示），表示线性表中一个数据元素 。

扩展

根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向，反向标记加在边上可能会更方便。

对于非线性的链表，可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn)，和平衡二叉树一样。

其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

由分别表示,,…, 的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。

链表基本操作（pascal语言）

建立一个链表

第一行读入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<>n then exit(0);

s^.next:=t^.next;

dispose(t);

exit(1)

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;

三个链表函数（C/C++语言描述）

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

struct Node{

int data;//数据域

struct Node * next;//指针域

};

/**************************************************************************************

*函数名称:Create

*函数功能:创建链表.

*输入:各节点的data

*返回值:指针head

*************************************************************************************/

Node * Create()

{

int n = 0;

Node *head,*p1,*p2;

p1= new Node;

cin>>p1->data;

head = NULL;

while(p1->data!=0)

{

if(n == 0)

{

head = p1;

}

else

p2->next = p1;

p2 =p1;

p1 = new node;

cin>>p1->data;

n++;

}

p2->next = NULL;

return head;

}

/**************************************************************************************

*函数名称:insert

*函数功能:在链表中插入元素.

*输入:head 链表头指针,p新元素插入位置,x 新元素中的数据域内容

*返回值:无

*************************************************************************************/

void insert(Node * head,int p,int x){

Node * tmp = head;

//for循环是为了防止插入位置超出了链表长度

for(int i = 0;i<p;i++)

{

if(tmp == NULL)

return ;

if(i<p-1)

tmp = tmp->next;

}

Node * tmp2 = new Node;

tmp2->data = x;

tmp2->next = tmp->next;

tmp->next = tmp2;

}

/**************************************************************************************

*函数名称：del

*函数功能:删除链表中的元素

*输入:head 链表头指针,p 被删除元素位置

*返回值:被删除元素中的数据域.如果删除失败返回-1

**************************************************************************************/

int del(Node * head,int p){

Node * tmp = head;

for(int i = 0;i<p;i++)

{

if(tmp == NULL)

return -1;

if(i<p-1)

tmp = tmp->next;

}

int ret = tmp->next->data;

tmp->next = tmp->next->next;

return ret;

}

void print(Node *head){

for(Node *tmp = head; tmp!=NULL; tmp = tmp->next)

printf("%d ",tmp->data);

printf("\");

}

int main(){

Node * head;

head = new Node;

head->data = -1;

head->next=NULL;

return 0;

}

例子：

#include<iostream>

#define NULL 0

struct student

{

long num;

struct student* next;

};

int main()

{

int i,n;

student* p=(struct student*)malloc(sizeof(struct student));

student* q=p;

printf("输入几个值");

scanf("%d",&n);

for(i=1;i<=n;i++)

{

scanf("%d",&(q->num));

q->next=(struct student*)malloc(sizeof(struct student));

q=q->next;

}

printf("值 第几个");

int rank;

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;

}

return 0;

}

//指针后移麻烦

结语与个人总结

C语言是学习数据结构的很好的学习工具。理解了C中用结构体描述数据结构，那么对于理解其C++描述，Java描述都就轻而易举了！链表的提出主要在于顺序存储中的插入和删除的时间复杂度是线性时间的，而链表的操作则可以是常数时间的复杂度。对于链表的插入与删除操作，个人做了一点总结，适用于各种链表如下：

插入操作处理顺序：中间节点的逻辑，后节点逻辑，前节点逻辑。按照这个顺序处理可以完成任何链表的插入操作。

删除操作的处理顺序：前节点逻辑，后节点逻辑，中间节点逻辑。

按照此顺序可以处理任何链表的删除操作。

如果不存在其中的某个节点略过即可。

上面的总结，大家可以看到一个现象，就是插入的顺序和删除的顺序恰好是相反的，很有意思！

两种链表形式

一、循环链表

循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。

2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

二、双向链表

双向链表其实是单链表的改进。

当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

链表的应用举例

约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。例如：n = 9, k = 1, m = 5

参考代码：

#include<stdio.h>

#include<malloc.h>

#define N 41

#define M 5

typedef struct node *link;

struct node{

int item;

link next;

};

link NODE(int item, link next)

{

link t = malloc(sizeof *t);

t->item = item;

t->next = next;

return t;

}

int main(void)

{

int i;

link t = 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\", t->item);

return 0;

}

VC6.0下链表的查插删改

-----悉尼大学工程学院张志刚（Stone Cold）作品

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

typedef struct Slist

{int data;

struct Slist * next;

}SLIST;

SLIST * InitList_Sq()/*初始化函数*/

{ int a;

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';

return h;

}

void print_list(SLIST *finder)/*打印函数*/

{

while(finder!='\\0')

{printf("->%d",finder->data);

finder=finder->next;}

printf("->end\");

}

int DeleteNode(SLIST *killer)//删除节点函数

{int i,j=0;SLIST *p,*q;int x;

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("\ error");

return -1;

}

else

{p->next=q->next;

x=q->data;

free(q);

return x;

}

}

void Insert_Node(SLIST *jumper)//插入函数，本算法为前插结点法

{int t,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;

}

}

void Locate_List(SLIST *reader)//查找值为e的元素

{

int e,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号位置\",i);

else printf("无此元素！");

}

void main()

{int i,k,y;SLIST *head;

printf("\ 1.建立线性表");

printf("\ 2.在i位置插入元素e");

printf("\ 3.删除第i个元素，返回其值");

printf("\ 4.查找值为e的元素");

printf("\ 5.结束程序运行");

printf("\ ===================================================");

printf("请输入您的选择：");

scanf("%d",&k);

switch(k){

case 1:{head=InitList_Sq();print_list(head->next);}break;

case 2:{head=InitList_Sq();

print_list(head->next);

Insert_Node(head);

print_list(head->next);

}break;

case 3:{head=InitList_Sq();

print_list(head->next);

y=DeleteNode(head);

print_list(head->next);

if(y!=-1)printf("被删除元素为：%d",y);

}break;//头结点不算，从有数据的开始算第一个

case 4:{head=InitList_Sq();

print_list(head->next);

Locate_List(head);

}break;

}

}

本程序可在微软VC++下编译通过并且运行

使用方法简介：运行程序后，先打数字1，然后回车，这样就可以先创建一个新的链表，比如你要创建一个

4->5->6->7这样一个链表，你就输入数字4回车，输入5回车，输入6回车，输入7回车，最后输入-1回车，这个-1就是告诉程序到此为止的标志

假如你要使用插入的功能，就在运行程序后输入2，回车，像上面所说的一样方法创建一个新链表，然后程序会出现提示，问你在哪个位置插入，比如你要在第三个位置插入，就输入3，回车，程序会问你插入的数值是什么，比如你要插入999，然后回车，999就被插进去了

其他的功能都大同小异