数据结构：Abstract data type(ADT)与Concrete data type(CDT)概念及实例讲解

我们常说的抽象数据类型（ADT）只定义数据类型的行为规范：只说明要支持哪些操作、操作要满足什么逻辑约束（比如栈的后进先出规则），完全不涉及底层怎么存储数据、操作怎么用代码实现，相当于只定「接口规范」。
而CDT就是ADT的具体落地实现：它把ADT定义的所有约束、操作都用明确的存储结构、可执行的代码逻辑实现，是可以直接在程序中实例化、调用的实体数据类型。

核心特征 #

• 实现逻辑完全确定：使用者可以明确知道CDT底层的数据存储结构、每个操作的执行逻辑，进而准确评估操作的时间、空间复杂度
• 无抽象待实现的方法：可以直接实例化使用，不需要额外补充实现逻辑

实际案例说明 #

我们拿最常见的栈（Stack）ADT举例：栈ADT的规范非常简单，只要求满足后进先出（LIFO）的访问顺序，支持push（入栈）、pop（出栈）、peek（取栈顶元素不弹出）、isEmpty（判空）4个核心操作，完全不限制实现方式。
对应这个ADT，就有两种常见的CDT实现：

1. 数组实现的顺序栈 #

底层用固定容量/可动态扩容的连续内存数组存储元素，额外用一个整型变量记录当前栈顶的下标位置
操作的具体实现逻辑：

• push：先判断数组剩余容量，足够的话把元素写入栈顶下标对应的位置，栈顶下标+1；容量不足时先触发数组扩容再执行写入
• pop：栈顶下标-1，返回原栈顶位置存储的元素

简易Python实现示例：

class ArrayStack:
    def __init__(self):
        self._storage = [] # 底层用Python动态数组存储元素
        self._top_idx = -1 # 记录栈顶下标

    def push(self, val):
        self._storage.append(val)
        self._top_idx += 1

    def pop(self):
        if self._top_idx < 0:
            raise IndexError("栈为空")
        res = self._storage.pop()
        self._top_idx -= 1
        return res

这个ArrayStack就是一个标准CDT：它完全符合栈ADT的所有规范，同时明确了底层是数组实现，使用者可以知道它的push操作均摊时间复杂度为O(1)，支持O(1)时间随机访问数组内的任意元素（如果开放访问权限的话）。

2. 链表实现的链式栈 #

底层用单向链表存储元素，默认把链表头结点作为栈顶，每个节点存储元素值和指向后一个节点的指针
操作的具体实现逻辑：

• push：新建节点，把新节点的next指针指向原链表头结点，再将链表头结点更新为新节点
• pop：取出当前头结点的元素值，将头结点更新为原头结点的next节点，返回取出的元素

简易Python实现示例：

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedStack:
    def __init__(self):
        self._head = None # 链表头结点，同时是栈顶

    def push(self, val):
        new_node = ListNode(val)
        new_node.next = self._head
        self._head = new_node

    def pop(self):
        if not self._head:
            raise IndexError("栈为空")
        res = self._head.val
        self._head = self._head.next
        return res

这个LinkedStack同样是栈ADT对应的CDT，和顺序栈相比底层实现完全不同：它没有数组扩容的额外开销，push/pop最坏时间复杂度都是O(1)，但存储密度更低，需要额外占用空间存储每个节点的next指针，也不支持随机访问。

除此之外，大部分编程语言的内置基础类型本质都是CDT，比如Python的list就是基于动态数组实现的CDT，Java的ArrayList、LinkedList也都是对应列表ADT的CDT实现。

内容的提问来源于stack exchange，提问作者Muhammad Banhawy