使用链表结构可以克服
数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了
数组随机读取的优点,同时链表由于增加了结点的
指针域,空间开销比较大。链表最明显的好处就是,常规
数组排列关联项目的方式可能不同于这些数据项目在
记忆体或
磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的
节点,但是不允许
随机存取。链表有很多种不同的类型:
单向链表,
双向链表以及
循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建
数据类型中就包含了链表的存取和操作。程序语言或
面向对象语言,如C,C++和Java依靠易变工具来生成链表。
线性表的链式存储表示的特点是用一组任意的
存储单元存储
线性表的
数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个
数据元素与其直接后继数据元素 之间的逻辑关系,对数据元素 来说,除了
存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。由这两部分信息组成一个"结点"(如概述旁的图所示),表示线性表中一个
数据元素。线性表的链式存储表示,有一个缺点就是要找一个数,必须要从头开始找起,十分麻烦。
根据情况,也可以自己设计链表的其它扩展。但是一般不会在边上附加数据,因为链表的点和边基本上是一一对应的(除了第一个或者最后一个
节点,但是也不会产生特殊情况)。不过有一个特例是如果链表支持在链表的一段中把前和后
指针反向,反向标记加在边上可能会更方便。
对于非线性的链表,可以参见相关的其他
数据结构,例如树、图。另外有一种基于多个线性链表的
数据结构:跳表,插入、删除和查找等基本操作的速度可以达到O(nlogn),和
平衡二叉树一样。
其中存储
数据元素信息的域称作数据域(设域名为data),存储直接后继存储位置的域称为
指针域(设域名为next)。
指针域中存储的信息又称做指针或链。
由分别表示,,…,的N 个结点依次相链构成的链表,称为
线性表的链式存储表示,由于此类链表的每个结点中只包含一个指针域,故又称
单链表或线性链表。