历史

链表开发于1955-56，由当时所属于兰德公司（ 英语： RAND Corporation ）的艾伦纽维尔（Allen Newell），克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）在他们编写的信息处理语言（IPL）中做为原始数据类型所编写。IPL被作者们用来开发几种早期的人工智能程序，包括逻辑推理机，通用问题解算器和一个计算机象棋程序。

结构

单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要储存反向的指针，见下面的双向链表）节点。

相对于下面的双向链表，这种普通的，每个节点只有一个指针的链表也叫 单向链表 ，或者 单链表 ，通常用在每次都只会按顺序遍历这个链表的时候（例如图的邻接表，通常都是按固定顺序访问的）。

链表也有很多种不同的变化：

双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）

在一些低级语言中, XOR-linking 提供一种在双向链表中通过用一个词来表示两个链接（前后），我们通常不提倡这种做法。

双向链表 也叫 双链表 。 双向链表 中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会或者移动的虚拟节点，形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数组里的情况，也可以直接用这个数组表示链表并用第0个或者第-1个（如果编译器支持）节点固定的表示这个虚拟节点。

循环链表

在一个 循环链表 中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

指向整个列表的指针可以被称作访问指针。

循环链表 中第一个节点之前就是最后一个节点，反之亦然。循环链表的 无边界 使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。

另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

块状链表

块状链表 本身是一个链表，但是链表储存的并不是一般的数据，而是由这些数据组成的顺序表。每一个块状链表的节点，也就是顺序表，可以被叫做一个 块 。

块状链表通过使用可变的顺序表的长度和特殊的插入、删除方式，可以在达到 O ( n ) {\displaystyle O({\sqrt {n}})} 的复杂度。块状链表另一个特点是相对于普通链表来说节省内存，因为不用保存指向每一个数据节点的指针。

其它扩展

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

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

存储结构

链表中的节点不需要以特定的方式存储，但是集中存储也是可以的，主要分下面这几种具体的存储方法：

链表的应用

链表用来构建许多其它数据结构，如堆栈，队列和他们的派生。

节点的数据域也可以成为另一个链表。通过这种手段，我们可以用列表来构建许多链性数据结构；这个实例产生于Lisp编程语言，在Lisp中链表是初级数据结构，并且现在成为了常见的基础编程模式。 有时候，链表用来生成联合数组，在这种情况下我们称之为联合数列。这种情况下用链表会优于其它数据结构，如自平对分查找树（self-balancing binary search trees）甚至是一些小的数据集合。不管怎样，一些时候一个链表在这样一个树中创建一个节点子集，并且以此来更有效率地转换这个集合。

C代码实例

范例代码是一个ADT（抽象数据类型）双向环形链表的基本操作部分的实例（未包含线程安全机制），全部遵从ANSI C标准，由User:JohnBull贡献，代码遵从GPL版权许可。

接口声明

#ifndef LLIST_H#define LLIST_Htypedefvoidnode_proc_fun_t(void*);typedefintnode_comp_fun_t(constvoid*,constvoid*);typedefvoidLLIST_T;LLIST_T*llist_new(intelmsize);intllist_delete(LLIST_T*ptr);intllist_node_append(LLIST_T*ptr,constvoid*datap);intllist_node_prepend(LLIST_T*ptr,constvoid*datap);intllist_travel(LLIST_T*ptr,node_proc_fun_t*proc);voidllist_node_delete(LLIST_T*ptr,node_comp_fun_t*comp,constvoid*key);void*llist_node_find(LLIST_T*ptr,node_comp_fun_t*comp,constvoid*key);#endif

接口实现

类型定

structnode_st{void*datap;structnode_st*next,*prev;};structllit_st{structnode_sthead;intlmsize;intelmnr;};

初始化和销毁

LLIST_T*llist_new(intelmsize){structllist_st*newlist;newlist=malloc(sizeof(structllist_st));if(newlist==NULL){returnNULL;}newlist->head.datap=NULL;newlist->head.next=&newlist->head;newlist->head.prev=&newlist->head;newlist->elmsize=elmsize;return(void*)newlist;}intllist_delete(LLIST_T*ptr){structllist_st*me=ptr;structnode_st*curr,*save;for(curr=me->head.next;curr!=&me->head;curr=save){save=curr->next;free(curr->datap);free(curr);}free(me);return0;}

节点插入

intllist_node_append(LLIST_T*ptr,constvoid*datap){structllist_st*me=ptr;structnode_st*newnodep;newnodep=malloc(sizeof(structnode_st));if(newnodep==NULL){return-1;}newnodep->datap=malloc(me->elmsize);if(newnodep->datap==NULL){free(newnodep);return-1;}memcpy(newnodep->datap,datap,me->elmsize);me->head.prev->next=newnodep;newnodep->prev=me->head.prev;me->head.prev=newnodep;newnodep->next=&me->head;return0;}intllist_node_prepend(LLIST_T*ptr,constvoid*datap){structllist_st*me=ptr;structnode_st*newnodep;newnodep=malloc(sizeof(structnode_st));if(newnodep==NULL){return-1;}newnodep->datap=malloc(me->elmsize);if(newnodep->datap==NULL){free(newnodep);return-1;}memcpy(newnodep->datap,datap,me->elmsize);me->head.next->prev=newnodep;newnodep->next=me->head.next;me->head.next=newnodep;newnodep->prev=&me->head;return0;}

遍历

intllist_travel(LLIST_T*ptr,node_proc_fun_t*proc){structllist_st*me=ptr;structnode_st*curr;for(curr=me->head.next;curr!=&me->head;curr=curr->next)proc(curr->datap);/* proc(something you like)*/return0;}

删除和查找

voidllist_node_delete(LLIST_T*ptr,node_comp_fun_t*comp,constvoid*key){structllist_st*me=ptr;structnode_st*curr;for(curr=me->head.next;curr!=&me->head;curr=curr->next){if((*comp)(curr->datap,key)==0){structnode_st*_next,*_prev;_prev=curr->prev,_next=curr->next;_prev->next=_next,_next->prev=_prev;free(curr->datap);free(curr);break;}}return;}void*llist_node_find(LLIST_T*ptr,node_comp_fun_t*comp,constvoid*key){structllist_st*me=ptr;structnode_st*curr;for(curr=me->head.next;curr!=&me->head;curr=curr->next){if((*comp)(curr->datap,key)==0){returncurr->datap;}}returnNULL;}

C宏实例

以下代码摘自Linux内核2.6.21.5源码(部分)，展示了链表的另一种实现思路，未采用ANSI C标准，采用GNU C标准，遵从GPL版权许可。

structlist_head{structlist_head*next,*prev;};#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)staticinlinevoidINIT_LIST_HEAD(structlist_head*list){list->next=list;list->prev=list;}staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next){next->prev=new;new->next=next;new->prev=prev;prev->next=new;}staticinlinevoidlist_add(structlist_head*new,structlist_head*head){__list_add(new,head,head->next);}staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next->prev=prev;prev->next=next;}staticinlinevoidlist_del(structlist_head*entry){__list_del(entry->prev,entry->next);entry->next=NULL;entry->prev=NULL;}#define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)#define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))

常见用途

常用于组织 删除、检索较少，而添加、遍历较多 的数据。 如果与上述情形相反，应采用其他数据结构或者与其他数据结构组合使用。

参见

其他数据结构

线性表

顺序表

基本数据结构

树 (数据结构)

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。