参考:
ADT(abstract data type)是由用户定义的数据类型,它制定了一组数据值的集合及可作用在这些数据值上的一组操作。ADT的定义与它的具体实现无关,因此只关注如何使用它,无需关注它的具体实现。
ADT可以被看做一个黑盒子。用户程序与ADT实例的交互是通过调用定义在ADT接口上的操作进行的。操作集可以分为4类:
ADT将定义与实现进行了分离。自定义的ADT必须要有一个实现,而实现ADT时我们所做出的选择会影响实现的功能和效率。
数据结构可以通过以下两方面来描述:
1. 它们如何存储和组织单个数据元素
2. 提供哪些操作来存取和处理其上的数据
参考:
数组是最常用的一种线性结构,其实python内置了一个array模块,但是大部分人甚至从来没用过它。Python的array是内存连续、存储的都是同一数据类型的结构,而且只能存储数值和字符。
常用的是numpy.array
操作 | 平均时间复杂度 |
---|---|
list[index] | O(1) |
list.append | O(1) |
list.insert | O(n) |
list.pop(index), default last element | O(1) |
list.remove | O(n) |