为什么链接列表实现被认为是线性的？

Question

通常，计算机内存总是线性的。那么，在逻辑意义上，“非线性”一词是否用于数据结构？如果是这样的话，在逻辑上实现线性计算机内存中的非线性，我们使用指针。是那么回事吗？

在这种情况下，如果指针是实现非线性的虚拟实现，那么为什么像链表这样的数据结构被认为是线性的，如果在现实中节点从来没有物理上相邻？

Answer 1

我认为它们所指的“线性”很可能是链接列表的性能特征。要访问链接列表的第n个元素，您需要逐个遍历它之前的每个元素。因此，这样做所需的时间是n的线性函数(其上限是列表大小)。与之相反的是，数组是随机访问，即按索引访问任何数组元素都需要几乎相同的恒定时间。

OTOH在链接列表中间的已知位置插入一个新元素需要恒定的时间，而在数组中这样做需要将数组的其余部分移动到内存中，这与后续元素的数量成线性关系(以数组的大小为界)。所以链接列表确实有性能上的好处。

Answer 2

非线性倾向于暗示一个结构超越一个简单的顺序模式.指针是一个用来通过类似数组的简单结构的概念。如果您想要另一个例子，关系数据库也可以被看作是一个非线性结构。

如果每个节点指向另一个节点，而树和其他数据结构中可能存在多个指针，则链接列表可以被认为是线性的。例如二叉树，很难想象成一行。另一个问题是，一些算法，如在未排序列表中找到最大元素，是如何具有线性时间复杂度的。

Answer 3

一个可能的原因--因为节点在内存中的位置并不是真正相关的。更重要的是如何从概念上看待列表。

在更具体的术语中，考虑一下通常如何将线性列表表示为一个图表。因为内存中的安排并不重要--这纯粹是一个实现细节--所以在图中并不表示这一点。您通常根据列表顺序对项目进行排序，因此它们形成了一条线，每个项目的顺序是沿着这条线再走一步。

另一个想法是，与循环链表相比，它纯粹是“线性”的。

佩特也提出了一个好的观点--可能比我的更好。但我怀疑我们都只是在编造合理的理由。有些名字没有很深的意义，但只是别人想出来的东西，没有花太多心思，然后这个名字就被卡住了。