20

有谁知道 Python（可能是 2.7）是否有内置的linkedList数据结构？我知道队列是使用列表实现的，并且没有堆栈（有 LIFO 队列）。

4

5 回答 5

15

是的，Python 的集合模块提供了 C 实现的对象，它在内部使用了 s 的deque链表 。BLOCK

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;          /* maxlen is -1 for unbounded deques */
    PyObject *weakreflist;
} dequeobject;

static PyTypeObject deque_type;
于 2016-09-05T20:50:06.767 回答
6

除非你真的想要一个明确的链表结构，否则 Python 的内置列表具有你从链表中获得的所有功能。例如，您可以将其用作堆栈，如下所示：

>>> x = []
>>> x.append(1)
>>> x.append(2)
>>> x
[1, 2]
>>> x.pop()
2
>>> x
[1]
>>>

或者，在给定元素之后插入一个元素：

>>> x = [1,2,3,4,5,6,7]
>>> x.insert(3,"a")
>>> x
[1, 2, 3, 'a', 4, 5, 6, 7]
>>>

例如，请参阅有关数据结构的 Python 文档。

但是，这是使用“列表”抽象数据类型 ( ADT )。相反，“链表”不是 ADT，而是实现该 ADT 的许多可能方式之一。

如果前置效率是一个问题，Łukasz Rogalski 的回答指出这collections.deque是使用链表实现的。正如使用列表作为队列注释：

也可以将列表用作队列，其中添加的第一个元素是检索到的第一个元素（“先进先出”）；但是，列表对此目的无效。虽然从列表末尾追加和弹出很快，但从列表开头插入或弹出很慢（因为所有其他元素都必须移动一个）。

要实现队列，请使用 collections.deque，它旨在从两端快速追加和弹出。

list为了测试使用vs.的效率影响deque，我使用了以下程序：

import timeit, sys

print ("append to list: %f" % (timeit.timeit ('x.append("x")', 'x = ["y"]')))
print ("insert to list element 0: %f" % (timeit.timeit ('x.insert(0,"x")', 'x = ["y"]')))
print ("append to deque: %f" % (timeit.timeit ('x.append("x")', 'import collections; x = collections.deque(["a","b","c"])')))
print ("append left to deque: %f" % (timeit.timeit ('x.appendleft("x")', 'import collections; x = collections.deque(["a","b","c"])')))

if (sys.version_info[0]+sys.version_info[1]/10) > 3.4999:
    print ("insert in deque: %f" % (timeit.timeit ('x.insert(2,"x")', 'import collections; x = collections.deque(["a","b","c"])')))

...并得到 Python 3.6 和 Python 2.7 的以下结果：

$ python3 testList.py
append to list: 0.113031
insert to list element 0: 191.147079
append to deque: 0.058606
append left to deque: 0.064640
insert in deque: 0.160418

$ python testList.py
append to list: 0.102542
insert to list element 0: 191.128508
append to deque: 0.083397
append left to deque: 0.064534

因此，list追加元素所花费的时间大约是追加元素的两倍，并且deque与deque追加相比，追加（即追加到左侧）所需的时间更少。

于 2013-02-03T02:12:43.667 回答
5

我相信 collections 包中的 deque 类是作为双向链表实现的，带有头部和尾部保护。它支持默认列表的所有常用 API。要附加到头部，请使用leftappend函数。

from collections import deque
于 2015-04-26T08:57:58.567 回答
4

python中没有内置的链表，但你可以使用dequeue，它让你可以访问head和tail，但是如果你想实现你自己的链表，你可以使用

Python 链表

于 2013-02-03T02:09:43.643 回答
0

Python 有 collections.deque，它是一个小 list()s 的双向链表。

不过，您几乎总是最好使用 Python list() 而不是链表。尽管链表对某些操作有更好的大 O，但 list() 通常更快，因为引用的局部性更好。

我实际上在 Python 中使用了链表：http: //stromberg.dnsalias.org/~strombrg/linked-list/ ...在进行性能比较之前。

我使用我的“计数”程序作为测试平台；使用链表，它比使用 list() 的版本更慢并且使用更多的 RSS (RAM)。count 在http://stromberg.dnsalias.org/~strombrg/count.html 我扔掉了它的链表版本；它不是非常有用。

list() 有时会更快是有道理的。考虑在 list() 和链表中从第一个元素到最后一个元素进行遍历。list() 倾向于对 n 个元素引用进行一次 RAM 缓存命中，而链表倾向于对每个元素进行一次 RAM 缓存命中。这是因为 list() 引用在 RAM 中都彼此相邻，但链表引用对于每个值都位于不同的类实例中。由于缓存比普通 RAM 快得多，这可能很重要。

collections.deque 并不会成为这种情况的牺牲品，因为链表中的每个节点都是由小数组组成的。

另一方面，如果您想避免人们使用随机访问您的值集合，链接列表可能是一个好主意。也就是说，有时为了抽象起见，您可能更喜欢链表而不是 list()。但是 Python 开发人员倾向于假设“我们都是成年人”。

此外，插入列表中间，如果您已经知道将新值放在哪里（也就是说，您不需要 O(n) 搜索来确定将它放在哪里），它会更快一些一个链表。

于 2020-01-16T21:20:13.580 回答