使用Python的数据结构

Question

Python有很多方便的数据结构（列表、元组、dict、set等），它们可以用来生成其他“常规”数据结构（例如，我可以使用Python列表创建堆栈和集合.出列排好队，用口述造出树和图形等）。在

甚至还有第三方数据结构可用于特定任务（例如Pandas、pytables等中的结构）。在

所以，如果我知道如何使用列表、dict、set等，那么我是否应该能够实现任意的数据结构，如果我知道它应该实现什么呢？在

换句话说，Python数据结构不能用于什么类型的数据结构？在

谢谢

Answer 1

您可以使用Python数据结构执行任何您喜欢的操作。整个编程语言Lisp（现在人们使用通用Lisp或Scheme）都是围绕链表数据结构构建的，Lisp程序员可以构建他们选择的任何数据结构。在

也就是说，对于某些数据结构，Python数据结构不是最佳选择。例如，如果你想构建一个展开树，你应该自己滚或者使用一个开源项目，比如pysplay。如果内置数据结构，解决你的问题，使用它们。否则，请超越内置的数据结构。像往常一样，使用最好的工具来完成工作。在

Answer 2

对于一些简单的数据结构（例如堆栈），您可以使用内置列表来完成工作。对于更复杂的结构（例如bloom过滤器），您必须使用语言支持的原语自己实现它们。在

你应该使用内置的，如果他们真的为你的目的，因为他们调试和优化了一大群人很长时间。你自己从头开始做可能会产生一个劣质的数据结构。无论你使用的是Python、C++、C语言、java，不管怎样，你都应该首先查看内置的数据结构。它们通常会使用与您必须自己使用的相同的系统原语来实现，但其优点是已经过尝试和测试。在

这些数据结构的组合（可能还有一些helper模块中的函数，比如heapq和{a2}）通常足以实现实际编程中可能需要的最丰富的结构；然而，情况并非总是如此。在

只有当所提供的数据结构不允许您完成所需的工作，并且没有其他可靠的库可供使用时，您才应该考虑从头开始构建（或扩展所提供的内容）。在

假设您需要比丰富的python库提供的更多的东西，考虑这样一个事实：一个对象的属性（和集合中的项）本质上是指向其他对象的“指针”（没有指针算术），即python中的“可重设表引用”（reseatable references），就像在Java中一样。在Python中，通常在属性或项中使用^ {< CD1> }值来表示在爪哇中，^ { CD2}}将意味着C++或^ {CD3}}将意味着什么。在

例如，您可以通过以下方式实现二叉树：

class Node(object):

  __slots__ = 'data', 'left', 'right'

  def __init__(self, data=None, left=None, right=None):
    self.data  = data
    self.left  = left
    self.right = right

以及用于遍历和类似操作的方法或函数（__slots__类属性是可选的，主要用于内存优化，以避免每个Node实例携带自己的{}，这将大大大于所需的三个属性/引用）。在

其他可以用专用Python类而不是直接组合其他现有Python结构的示例包括tries（参见例如here）和{}（参见例如here）。在

Answer 3

假设所有的数据结构都存在于内存中，而内存实际上只是一个list（数组）。。。没有一种数据结构不能用基本的Python数据结构来表示（使用适当的代码与它们交互）。在