Python中的数据结构
到目前为止，我读过的所有关于数据结构的书籍似乎都使用C/C++，而且它们很依赖于手动控制指针的功能。因为Python把这种内存管理和垃圾回收的工作都隐藏起来了，难道在这个语言中实现高效的数据结构还有可能吗？而且，除了使用内置的功能，还有必要这样做吗？
6 个回答
C/C++的数据结构书籍主要是想教你各种结构背后的基本原理，并不是让你去自己重新发明轮子，去建立自己的栈和列表库。
无论你使用的是Python、C++、C#、Java还是其他语言，首先应该看看内置的数据结构。它们通常是用你自己实现时需要用到的基本系统功能来做的，而且经过了很多测试，比较可靠。
只有在内置的数据结构无法满足你的需求，且没有其他可靠的库可以使用时，才应该考虑从头开始自己构建东西（或者在现有的基础上进行扩展）。
对于一些简单的数据结构（比如栈），你可以直接用内置的列表来完成你的任务。对于更复杂的结构（比如布隆过滤器），你就需要自己动手实现了，利用语言提供的基本功能。
如果内置的功能能满足你的需求，那就尽量使用它们，因为这些功能经过很多人长时间的调试和优化，效果会更好。自己从头做可能会导致你做出的数据结构不够好。
不过，如果你需要的功能在内置的选项中没有，或者内置的功能表现得不够好，那你就得自己实现一个新的类型。
像指针管理这些细节只是实现过程中的技术讨论，并不会限制语言本身的能力。
Python 提供了一些强大且经过优化的数据结构，这些数据结构既有内置的，也有一些模块中的标准库（比如 list 和 dict，当然还有 tuple、set、在 array 模块中的 array，以及在 collections 模块中的其他容器）。
这些数据结构的组合（也许还包括一些辅助模块中的函数，比如 heapq 和 bisect）通常足以实现大多数在实际编程中需要的复杂结构；不过，这并不总是适用。
当你需要的东西超出了丰富的库所提供的范围时，可以考虑一个对象的属性（以及集合中的项）本质上是指向其他对象的“指针”（没有指针运算），也就是说，在 Python 中就像在 Java 中一样，它们是“可重置的引用”。在 Python 中，通常使用 None 值来表示属性或项中的空值，这就像在 C++ 中的 NULL 或在 Java 中的 null。
所以，例如，你可以通过以下方式实现二叉树：
class Node(object):
__slots__ = 'payload', 'left', 'right'
def __init__(self, payload=None, left=None, right=None):
self.payload = payload
self.left = left
self.right = right
再加上用于遍历和类似操作的方法或函数（__slots__ 类属性是可选的——主要是为了优化内存，避免每个 Node 实例都携带自己的 __dict__，这会比需要的三个属性/引用大得多）。
其他可能更适合用专门的 Python 类来表示的数据结构，而不是直接组合其他现有的 Python 结构，包括 tries（例如可以参考 这里）和 graphs（例如可以参考 这里）。