Question

单链表的存储密度( )。

Answer 1

单链表的存储密度小于1。

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

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

原因：

“存储密度=单链表数据项所占空间/结点所占空间”，而“结点所占空间＝数据项所占空间＋存放后继结点地址的链域”；所以，存储密度小于1。

数据结构中单链表的存储密度：链表的每个节点除了数据域用来存储元素外，还要额外的设置指针域，用来存储用来存储指示元素之间的逻辑关系的指针。

存储密度是指数据元素本身所占的存储量和整个结点结构所占的存储量之比。

假设单链表数据元素本身的存储量为N，指针域所占的存储量为M，则存储密度为：N/（N+M）。而结点所占空间＝数据项所占空间＋存放后继结点地址的链域。