[科普中国]-链式数据存储

链表概述

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

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

共用存储空间

链表的节点和其它的数据共用存储空间，优点是可以存储无限多的内容（不过要处理器支持这个大小，并且存储空间足够的情况下），不需要提前分配内存；缺点是由于内容分散，有时候可能不方便调试。

独立存储空间

一个链表或者多个链表使用独立的存储空间，一般用数组或者类似结构实现，优点是可以自动获得一个附加数据：唯一的编号，并且方便调试；缺点是不能动态的分配内存。当然，另外的在上面加一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法有时候被叫做数组模拟链表，但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种下标索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的（但是可以说成是用数组实现的链表）。

链式存储结构链式存储结构中每个结点除了包含信息域之外，还至少包含 一个指针域。链式存储结构是用指针来体现数据元素之间的逻辑关系的。利用这种结构，各个数据元素的存储单元不再要求是连续的，即可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中，还可以在线性编址的存储器中表示非线性关系的结点。

链式存储结构的主要特点为：

结点中除包含保存数据元素的自身信息的信息域外，还有表示数据元素之间的链接信息的指针域，因此比顺序存储结构的存储密度低，存储空间的利用率也较低。

逻辑上相邻的数据元素在物理上不一定相邻，可用于存储线性表、树、图等多种逻辑结构。

插入、删除操作比较灵活，不必移动数据元素，只要改变结点中的指针域的值即可。1

串的链式存储链串用单链表方式存储串值，串的这种链式存储结构简称为链串链串的结构类型定义 ：

typedef struct node{

char data;

struct node *next;

}LinkStrNode; //结点类型

typedef LinkStrNode *LinkString; //LinkString为链串类型

LinkString S; //S是链串的头指针

注意：①链串和单链表的差异仅在于其结点数据域为单个字符：

②一个链串由头指针唯一确定。

链串的结点大小通常，将结点数据域存放的字符个数定义为结点的大小。结点的大小的值越大，存储密度越高。

可以采取以下措施

①为了提高存储密度，可使每个结点存放多个字符。

②当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。

③虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。2