Python ha una struttura dati linkedList integrata?

Question

Qualcuno sa se Python (forse 2.7) ha una struttura dati integrata linkedList? So che la coda è implementata usando la lista, e non c'è stack (c'è la coda LIFO).

Answer 1

non c'è costruito in lista collegata in Python, ma u possibile utilizzare dequeue, dà u accesso alla testa e la coda sia, ma se u desidera implementare la vostra propria lista collegata può essere u possibile utilizzare

Python Linked List

Answer 2

A meno che non si desideri effettivamente una struttura di elenco collegata esplicita per qualcosa di specifico, l'elenco integrato di Python ha tutte le funzionalità che si ottengono da un elenco collegato. Ad esempio, è possibile utilizzarlo come una pila, come segue:

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

Oppure, per inserire un elemento dopo un determinato elemento:

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

Si veda, ad esempio, la documentazione Python su data structures.

Tuttavia, questo sta utilizzando il tipo di dati astratto "elenco" (ADT). Al contrario, una "lista collegata" non è un ADT ma uno dei molti modi possibili per implementarla.

Answer 3

Credo che la classe deque nel pacchetto collezioni sia implementata come una lista doppiamente collegata, con protezioni testa e coda. Supporta tutte le normali API dell'elenco predefinito. Per aggiungere alla testa, utilizzare la funzione leftappend.

from colletions import deque 

Answer 4

Sì, Python collections module fornisce C-implementato deque oggetto, che utilizza l'elenco dei BLOCK s collegati internamente.

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;