程序员是如何在面向对象范式之前实现链表思想的？

Question

据我所见，链接列表主要是使用面向对象的思想实现的。(有一个保存某些信息和下一个链接地址的对象)。在面向对象的范例出现之前，链接列表是如何实现的？他们只是发明了(？)一旦OOP被开发出来？

Answer 1

链接列表与OOP无关，实际上它们比OOP早很多。链表是通过具有递归结构来实现的，在我看来，在组装中，这在概念上是最容易理解的--您分配一些内存，而该内存的第一个字节作为指向下一个/前一个的指针。在程序集中，您不必担心“类型”，只需将其视为另一个指针，因此，它是递归的这一事实并不是您需要考虑的问题--您不必考虑在其定义中如何引用某物。

Answer 2

例如，在C中，他们使用struct来模拟节点，并使用指针来链接节点。

Answer 3

据我所见，链接列表主要是使用面向对象的思想实现的。(有一个保存某些信息和下一个链接地址的对象)。

你看过什么不是面向对象的？如果您只看到了OO，那么您看到的唯一的简单数据结构的实现就是OO，这一点也就不足为奇了。

他们只是发明了(？)一旦OOP被开发出来？

链接列表比OO编程早几十年。

在面向对象的范例出现之前，链接列表是如何实现的？

1950年，S在IBM 704上实现了Lisp编程语言。Lisp的基本数据结构是cons单元，它是一个由两个值组成的组。IBM 704的机器字大小为36位，还有一些特殊的指令，CAR和CDR，它们将从36位字中提取15位值。存储在CAR位中的值是列表的头，而存储在CDR中的值是尾，因此在这种情况下，cons单元格可以用作链接列表中的节点。

有关如何在1950年代的IBM704上实现链接列表的更详细的讨论，请参见http://en.wikipedia.org/wiki/CAR_和_CDR。