Jez*_*ust 4 python data-structures
我正在阅读一本关于数据结构和基本算法的书，以更好地掌握编程。我正在阅读的这本书定义了一些数据结构，例如列表、数组等，并指定了这些数据结构的接口，以及如何使用不同语言的现有数据结构来实现（或构造）它们。例如，它讨论了如何将列表构造为数组或链接单元格。
然而，当我开始查看不同语言中的这些数据类型时，我发现它们并不总是遵循书中定义的接口。
例如，这本书说，在一个列表中，你应该能够一次遍历不同的元素，只从两端开始。例如，如果我想要第三个元素，我必须从第一个元素开始并使用“下一个”操作，直到找到我想要的元素。但是 Python 中的列表具有整数索引，我可以通过使用相应的索引直接访问任何元素。在本书中，索引类型只需是带有比较操作的有序类型即可。（我认为这本书试图通过抽象事物来保持一般性）。
这是否意味着 Python 的列表不是“真正意义上的”列表？还是书中定义的数据结构只是对这些接口的外观的建议，在实践中可能会有很多变化？
我理解这本书的想法是为了更好地理解如何思考数据结构，并介绍一些典型的，所以我倾向于认为后一个答案是正确的。
许多数据结构有多个名称（想到hash[map/table] /dictionary/associative array）。您指的是两个不相关的数据结构，除了它们都存储项目的线性序列这一事实之外。名称相似性是一个令人遗憾的混淆源，但 TL;DR 是Python 术语中的列表与数组非常相似，并且建立在数组之上，而链接列表（您的文本称为“列表”）不是。
将实现与接口分开很重要：例如，队列背后的底层数据结构可以是数组或链表，但这应该是接口客户端不知道或不关心的实现细节。接口应该强制保证各种操作的时间复杂度。数据结构文本使用各种底层“原始”数据结构（如数组或链表）来实现抽象数据类型是很常见的，其中许多可能会影响各种操作的结果复杂性（促使学生分析）。
链表是简单、动态（可扩展）的数据结构，在两端提供快速的 O(1) 添加和删除操作。它们的节点可能是双向链接的，通常是内存中的结构或对象，带有指向next和（如果双向链接）previous元素的指针或引用，以及data每个节点的属性。链表没有随机访问——您必须从端点遍历列表以通过跟随指针定位单个元素。
链表通常用于实现队列、堆栈和更复杂的数据结构，如 Java 的LinkedHashMap，它结合了双向链表和哈希映射。Python 提供collections.deque和Queue，它们是基于链表的数据结构，提供对前端和后端元素的快速访问。其他库，如 Java 的ArrayDeque，使用循环数组来实现相同的双端队列接口。
树节点是单链表节点的变体，具有两个子指针而不是单个下一个指针。与链表（及其节点）一样，通常树节点和树将是诸如 C++ 之类的接口背后的实现细节map。例如，您可以使用数组实现树，就像heaps 的典型情况一样。
Python 的列表（也称为ArrayLists(Java)、数组 (JS/Ruby)、向量 (C++/Haskell) 和List(C#)）是对大小固定的原始数组的动态抽象。列表抽象增加了一个length特性和许多功能，用于操纵基础数组像append/ push/ push_back，pop，shift，splice，等（名称取决于语言）。底层数组将自动调整大小以适应它包含的元素数量。在列表的前面或中间插入或删除元素是一个 O(n) 操作，因为需要移动尽可能多的元素以适应对数组的调整。这种转移是抽象的一部分，对客户端是隐藏的。
列表的优点与数组的优点相同：快速随机访问任何元素。添加到列表的末尾也是快速且恒定时间的，因为底层数组的偶尔重新分配会在多个追加操作中分摊。
列表与原始数组的一个重要考虑因素是内存方案。Python 列表由对象组成，并且存在链表的许多问题，因为指向堆分配数据的指针需要被引用并且可能具有较差的局部性。使用numpy 数组提供了 C 数组的优点，因为您可以获得从快速访问（扫描数据上的内存对齐偏移量）和局部性中受益的顺序内存块。增加的开销是列表等抽象的典型成本，它会对某些应用程序产生重大的性能影响。
更令人困惑的是，至少有两种高级语言 C++ 和 Haskell 具有“列表”数据结构，但这些实际上是链表而不是动态数组（列表）。
无论您使用哪种语言，重要的是要区分您真正使用的数据结构是什么（主要是在典型操作的时间复杂度方面），以避免无意中误用并为工作选择正确的工具。