pythonには組み込みのlinkedListデータ構造がありますか？

Question

Python（おそらく2.7）に組み込みのlinkedListデータ構造があるかどうかは誰にも分かりますか？私はキューがリストを使って実装されていることを知っているし、スタックがありません（LIFOキューがあります）。 pythonでリンクリストに建てられたが、uはデキューを使用することができます何が

Answer 1

ありませんが、それはuは頭と尾の両方にアクセスすることができますが、uはあなたがリンクリストを所有して実装する場合uが

Python Linked List

を使用することができかもしれ

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] 
>>> 

は、例えば、data structures上のPythonドキュメントを参照してください。

ただし、これは "リスト"抽象データ型（ADT）を使用しています。対照的に、「リンクされたリスト」はADTではなく、そのADTを実装する多くの可能な方法の1つです。

Answer 3

私は、コレクションパッケージのdequeクラスが、頭と尾のガードを持つ二重リンクリストとして実装されていると思います。これは、デフォルトのリストのすべての通常のAPIをサポートしています。頭に追加するには、leftappend機能を使用してください。

from colletions import deque 

Answer 4

はい、Pythonのcollections moduleは内部BLOCK秒のリンクリストを使用してC-実装dequeオブジェクトを提供します。

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;