Does python have built-in linkedList data structure?

Question

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

Answer 1

Yes, Python's collections module provides C-implemented deque object, which uses linked list of BLOCKs internally.

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

Unless you actually want an explicit linked list structure for something specific, Python's built-in list has all the functionality that you get from a linked list. For example, you can use it as a stack, as follows:

>>> 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 on data structures.

However, this is using the "list" abstract data type (ADT). In contrast, a "linked list" is not an ADT but one of many possible ways of implementing that ADT.

If efficiency of prepending is an issue, Łukasz Rogalski's answer points out that collections.deque is implemented using a linked list. As Using Lists as Queues notes:

It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).

To implement a queue, use collections.deque which was designed to have fast appends and pops from both ends.

To test the efficiency impacts of using list vs. deque, I used the following program:

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"])')))

... and got the following results for Python 3.6 and 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

Thus, list takes roughly twice as much time to append an element as does deque and deque takes less time to prepend (i.e. append to left) than to append.

Answer 3

I believe the deque class in the collections package is implemented as a doubly linked list, with head and tail guards. It supports all the usual API of the default list. To append to the head, use leftappend function.

from collections import deque

Answer 4

There is no built in linked list in python but u can use dequeue, it gives u access to head and tail both, but if u want to implement yours own linked list may be u can use

Python Linked List

Answer 5

Python has collections.deque, which is a doubly linked list of small list()s.

You're almost always better off using a Python list() instead of a linked list though. Even though linked lists have a superior big-O for some operations, the list() is frequently faster because of better locality of reference.

I actually played with linked lists in Python a bit: http://stromberg.dnsalias.org/~strombrg/linked-list/ ...prior to doing a performance comparison.

I used my "count" program as a test bed; with a linked list, it was both slower and used more RSS (RAM) than a version that used list(). count is at http://stromberg.dnsalias.org/~strombrg/count.html I threw away the linked list version of it; it wasn't terribly useful.

It kind of makes sense that a list() would be faster at times. Consider doing a traversal from the first element to the last in both a list() and a linked list. list() tends to do a single RAM cache hit for n element references, while a linked list tends to do a single RAM cache hit for every element. That's because the list() references are all next to each other in RAM, but the linked list references are in a different class instance for every value. With caches being much faster than regular RAM, that can matter quite a bit.

collections.deque does not fall prey to this as much, because of the small arrays making up each node in the linked list.

On the other hand, if you want to avoid people using random access to your collection of values, a linked list might be a good idea. That is, sometimes for the sake of abstraction you may prefer the linked list over a list(). But Python developers tend to assume that "we're all adults."

Also, inserting in the middle of a list, if you already know where to put your new value (that is, you don't need an O(n) search to figure out where to put it), it's quite a bit faster with a linked list.