链接列表是ADT还是数据结构,或两者兼而有之？

Question

如果我将抽象数据类型的标准定义用作提供管理数据集合的一些函数的黑盒子,则链接列表符合以下描述:

提供可用于维护对象列表的函数add(x)和get(i)(以及其他)的容器.

但是当你问这个问题时,这些操作的时间复杂度是多少,那么你就会意识到这取决于这个容器的实现方式:

如果您只是在内部维护到头节点的链接,则上述两个操作将在O(n)时间内执行.如果你另外维护一个到尾节点的链接,那么你将获得O(1)时间.

所以我的问题是,出于学习目的,您是否将链接列表视为ADT或数据结构？

当我试图从Skiena的算法设计手册中实现Stack ADT时,问题出现了,并且正在阅读它的put(x)和get()方法的性能将取决于选择什么数据结构来实现它.这本书说在这种情况下,如果你选择一个阵列或链表数据结构来实现这个ADT并不重要,它们都提供类似的性能.

但他们呢？是否取决于链接列表的实现方式？实现链表本身的方法有很多种,所以这不是另一个ADT本身吗？

Answer 1

来自维基百科的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关心.但它们是不同的数据结构!