I know in c++ it already exist
#include <list>
Now I am curious to know if it exist in python also.
2 Answers
You can also take a look at llist python package, which provides some useful features that deque does not. There are not only doubly linked lists, but also single linked lists data structure in that package. IMHO, one of the biggest advantages of this package is the ability to store a reference to the llist elements.
1 Comment
Mugen
There's another answer here: stackoverflow.com/questions/280243/…
It appears that collections.deque is a doubly-linked-list library in Python. According to the documentation, it should have approximately O(1) cost when appending or popping from the head or the tail, as well as O(n) for regular inserts (which matches what we'd expect from a linked list).
API: http://docs.python.org/2/library/collections.html#collections.deque
8 Comments
Mugen
I went through the document for deque. It seems like deque is more like a FIFO or LIFO. You cannot insert elements in the middle of the queue. You can only insert them at the beginning or the end.
Alex Reinking
@winni2k - only if you don't do something smart, like keep a reference to a particular node that represents a known insertion point. With a doubly linked list, you can get O(1) insertions to intelligently defined points and only pay an O(n) cost of finding those points up front.
gdlamp
i disagree, insert/remove should be O(1) for a linkedlist given a reference to the element
jackieyang
@Mugen True for python 2. But for Python 3.5, you can insert element in deque. See: docs.python.org/3.7/library/…
fortea
Linked lists should insert in O(1)
|
listtype.listis equivalent to an array, not a linked list, it's a different data type.