Question

单链表的存储密度是多少

Answer 1

单链表的存储密度是：

假设单链表数据元素本身的存储量为N，指针域所占的存储量为M，则存储密度为：N/（N+M）。

链表的每个节点除了数据域用来存储元素外，还要额外的设置指针域，用来存储用来存储指示元素之间的逻辑关系的指针。存储密度是指数据元素本身所占的存储量和整个结点结构所占的存储量之比。

存储密度越大，空间利用率越高，显然顺序表的存储密度为1，如果单纯的从存储密度来讲，链表的这种存储方式是不经济的，基于此，如线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素数据元素的映象指针指示后继元素存储位置。

元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。