python是否内置了LinkedList数据结构？

Question

有谁知道Python(可能是2.7)是否有内置的linkedList数据结构？我知道队列是使用list实现的,并且没有堆栈(有LIFO队列).

Answer 1

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

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;

Answer 2

除非你真的想要一个显式的链表结构用于特定的东西，否则 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是使用链表实现的。As Using Lists as Queues注意：

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

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

为了测试使用listvs.的效率影响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花费较少的时间，以预定（即追加到左），而不是追加。

Answer 3

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

from collections import deque

Answer 4

python中没有内置的链表，但你可以使用出队，它让你可以访问头和尾，但如果你想实现自己的链表，你可以使用

Python 链表