如果我使用抽象数据类型的标准定义作为提供一些功能来管理数据集合的黑匣子，则链表符合该描述:
提供可用于维护对象列表的函数 add(x) 和 get(i) (以及其他)的容器。
但是当你问这些操作的时间复杂度是多少时，你就会意识到这取决于这个容器是如何实现的:
如果只是在内部维护一个到头节点的链接，上面的两个操作将在 O(n) 时间内执行。如果您另外维护一个到尾节点的链接，您将在两者上获得 O(1) 时间。
所以我的问题是，出于学习目的，您认为链表是 ADT 还是数据结构？
当我试图从 Skiena 的算法设计手册中实现堆栈 ADT 并且正在阅读它的 put(x) 和 get() 方法的性能将如何取决于选择什么数据结构来实现它时，出现了这个问题。书中说，在这种情况下，选择数组或链表数据结构来实现此 ADT 并不重要，它们都提供相似的性能。
但是他们呢？这不取决于该链接列表的实现方式吗？有很多方法可以实现链表本身，那么这个事实是不是使它只是另一个 ADT 本身？
最佳答案
来自维基百科上的 ADT : In computing, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior 所以，链表是一个 ADT，每个 ADT 也是一个数据结构，所以链表是两者。
编辑:
但是需要注意的是，单链表和双链表的操作是一样的，复杂度也是一样的，所以都是链表ADT，作为ADT我们不区分。但它们是不同的数据结构!
关于arrays - 链表是 ADT 还是数据结构，或两者兼而有之？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6539126/