黑马程序员技术交流社区

标题: 【成都校区】 Python的列表(List)的底层实现原理 [打印本页]

作者: 小刀葛小伦 时间: 2019-6-12 18:29
标题: 【成都校区】 Python的列表(List)的底层实现原理
   列表实现可以是数组和链表。
   顺序表是怎么回事？顺序表一般是数组。
   列表是一个线性的集合，它允许用户在任何位置插入、删除、访问和替换元素。
   列表实现是基于数组或基于链表结构的。当使用列表迭代器的时候，双链表结构比单链表结构更快。
   有序的列表是元素总是按照升序或者降序排列的元素。
   实现细节
   python中的列表的英文名是list，因此很容易和其它语言(C++, Java等)标准库中常见的链表混淆。事实上CPython的列表根本不是列表（可能换成英文理解起来容易些：python中的list不是list）。在CPython中，列表被实现为长度可变的数组。
   从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。幸运的是，Python在创建这些数组时采用了指数分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。
   不幸的是，在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。
   列表和元组
   列表和元组的区别是显然的：
   列表是动态的，其大小可以该标 (重新分配)；
   而元组是不可变的，一旦创建就不能修改。
   list和tuple在c实现上是很相似的，对于元素数量大的时候，
   都是一个数组指针，指针指向相应的对象，找不到tuple比list快的理由。
   但对于小对象来说，tuple会有一个对象池，所以小的、重复的使用tuple还有益处的。
   为什么要有tuple，还有很多的合理性。
   实际情况中的确也有不少大小固定的列表结构，例如二维地理坐标等；
   另外tuple也给元素天然地赋予了只读属性。
   认为tuple比list快的人大概是把python的tuple和list类比成C++中的数组和列表了。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2