Python 中的 List 是封装了顺序存储结构还是链表存储结构？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 2283 天前的主题，其中的信息可能已经有所发展或是发生改变。

最近在重温大学的数据结构突然想到一个问题，我们平时在使用的 List 到底是封装了顺序存储结构还是单链还是其他的结构，毕竟每一种结构都有其使用场景

另外想请教一下，Python 里面有相关的顺序存储结构或者链的相关库吗，可以方便直接拿来用的

结构

Python

存储

顺序

23 条回复 • 2018-09-03 18:00:32 +08:00

dbow

2018-08-29 21:47:58 +08:00

数组实现的

zhengxiaowai

2018-08-29 21:48:58 +08:00

collections

Alerta

2018-08-29 21:51:58 +08:00

@zhengxiaowai collections 没有链表的实现方式吧？ https://docs.python.org/2/library/collections.html

zhzer

2018-08-29 22:04:00 +08:00 via Android

结合顺序和链表的一种动态类型，类似 stl 的 vector

bobuick

2018-08-29 22:07:15 +08:00

楼上说的没错 +1

单单的数组当然不行了，py 是不是静态类型的。

Alerta

2018-08-29 22:49:33 +08:00

@bobuick 最后一句你是想说 py 不是静态类型？

d18

2018-08-29 22:58:14 +08:00

cpython 就是动态数组，一个 struct，里面有动态数组和类似 size，used 之类的属性。不够了就 realloc。
jython 是用了 arraylist，其实也是动态数组。

n2ex2

2018-08-29 23:16:22 +08:00 via Android

肯定是链表，不然怎么 append。

wwqgtxx

2018-08-29 23:31:01 +08:00

@n2ex2 自己看看 python list 的实现，还真的不是链表
https://github.com/python/cpython/blob/3.7/Include/listobject.h#L23

wwqgtxx

2018-08-29 23:35:12 +08:00

至于 append 怎么实现的，基本上就是和 c++的 vector 一样，开个大数组，不够用就再扩容呗
https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L301
扩容因子在这里定义的
https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L59

@n2ex2

Alerta

2018-08-30 00:20:08 +08:00 via iPhone

@wwqgtxx 老哥看源码看得不是很明白可以解释一下吗

lance6716

2018-08-30 00:53:25 +08:00 via Android

@Alerta 哪里没看明白，不看异常检查的话就是调整 list 长度，调整引用计数，执行 append

lance6716

2018-08-30 01:01:57 +08:00 via Android

@wwqgtxx 不是很明白扩容里面的 growth pattern 具体指什么，算不出这个序列

wwqgtxx

2018-08-30 06:36:16 +08:00 via iPhone

@lance6716 就是说他的容量递增永远是按照这个序列来
0, 4, 8, 16, 25, 35, 46, 58, 72, 88,
至于这个序列就是从 (newsize >> 3) + (newsize < 9 ? 3 : 6) 算出来的呀

lance6716

2018-08-30 09:49:09 +08:00 via Android

我想错了…白打了这么多字就不删了，给不明白的同学看看

初始化长度为 0，当想要 resize 为 1 的时候，实际 allocated 为 1+0+3=4
resize 为 5，allocated 为 5+0+3=8
resize 为 9，allocated 为 9+1+6=16
resize 为 17，allocated 为 17+2+6=25
@wwqgtxx

zhengxiaowai

2018-08-30 10:17:27 +08:00

@Alerta deque

bany

2018-08-30 10:45:01 +08:00

动态数组实现的。在 Python 中 list 的操作涉及到 list 长度改变的，在底层（ CPython ）中都会调用 list_resize(PyListObject *self, Py_ssize_t newsize) 这个方法，这个方法也是 list 长度改变的核心算法实现；如果是当前 list 的长度大于了之前申请的内存空间了，那么新的长度通过这个表达式得出 new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)（也就是#14 楼说的那个序列值），然后在动态申请内存；

Alerta

2018-08-30 10:48:18 +08:00

@bany 那这个动态 list 的插入删除操作是用顺序结构还是用链式结构来实现的呀请问

bany

2018-08-30 11:12:20 +08:00

@Alerta 这里是 list.insert 的实现，我把关键的实现挑出来：
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;

/* 这里重新计算长度 */
if (list_resize(self, n+1) < 0)
return -1;

if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
if (where > n)
where = n;
/* items 可以理解为一个数组，items 这个数组里存放的是 PyObject 这样的结构体（也就是 Python 中的数据） */
items = self->ob_item;
/* where 是要插入的位置 */
for (i = n; --i >= where; )
/* 将要插入位置之后的元素往后移一位 */
items[i+1] = items[i];
Py_INCREF(v);
/* 插入元素 */
items[where] = v;
return 0;
}

这里是通过数组实现的，也就是顺序结构。

Alerta

2018-08-30 14:43:58 +08:00

@bany 要是我插入删除操作多的话，现在有没有一些库是支持链表实现的呀

Alerta

2018-08-30 14:47:35 +08:00

为什么 Python 标准库没有内置链表的库？？是因为 python 里面有什么神奇的地方吗

Alerta

2018-08-30 15:01:06 +08:00

21 楼属自问自答系列，标准答案在这： http://blog.suchasplus.com/2011/03/why-python-Standard-library-does-not-implement-the-list.html

thautwarm

2018-09-03 18:00:32 +08:00

python list 类似 arraylist，
python 中链表实现多用 nested list/tuple.