Geek asks and answers

Does python have a built-in data structure associated with a List?

Does anyone know if Python (possibly 2.7) has a built-in data structure linkedList? I know that a queue is implemented using a list, and there is no stack (there is a LIFO queue).

+5
source share
4 answers

Yes, Python provides a C-implemented object dequethat uses a linked list internally. 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;
+4
source

There is no built-in linked list in python, but you can use dequeue, it gives you access to the head and tail, but if you want to implement your own linked list, you can use

Python linked list

+1
source

- , Python , . , , :

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

Or, to insert an element after a given element:

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

See, for example, the Python documentation in data structures .

However, it uses an abstract list data type ( ADT ). In contrast, a β€œlinked list” is not an ADT, but one of many possible ways to implement this ADT.

+1
source

I believe that the deque class in the collection package is implemented as a doubly linked list, with head and tail protection. It supports all the usual default list APIs. To add to the head, use the function leftappend.

from colletions import deque
0
source

More articles:


All Articles