31

I know in c++ it already exist #include <list> Now I am curious to know if it exist in python also.

user2947416
  • 325
  • 1
  • 4
  • 6
  • 3
    Welcome to SO! Could you elaborate why you need this? Python already has the `list` type. – georg Nov 03 '13 at 10:55
  • 8
    A Python `list` is equivalent to an array, not a linked list, it's a different data type. – Leigh Nov 03 '13 at 10:56
  • 3
    Possible duplicate of http://stackoverflow.com/questions/280243/python-linked-list – Tim Nov 03 '13 at 10:56
  • 1
    This question should be reopened - it's clear what the user is asking for. As @Leigh mentioned, a list in Python is something very different from a linked list. Maybe it's a duplicate, but the close reason given is wrong. – Cornelius Roemer Aug 21 '22 at 15:29

2 Answers2

20

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.

ardito.bryan
  • 429
  • 9
  • 22
Alexander Zhukov
  • 4,357
  • 1
  • 20
  • 31
  • There's another answer here: http://stackoverflow.com/questions/280243/python-linked-list?noredirect=1&lq=1 – Mugen Sep 05 '16 at 11:47
-1

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

Source: https://stackoverflow.com/a/282238/2441252

Community
  • 1
  • 1
Leigh
  • 12,038
  • 4
  • 28
  • 36
  • 19
    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. – Mugen Sep 05 '16 at 11:24
  • 1
    @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. – Alex Reinking Jun 01 '19 at 02:24
  • 7
    i disagree, insert/remove should be O(1) for a linkedlist given a reference to the element – gdlamp Jul 24 '19 at 23:57
  • 3
    @Mugen True for python 2. But for Python 3.5, you can insert element in deque. See: https://docs.python.org/3.7/library/collections.html#collections.deque.insert – jackieyang Sep 01 '19 at 07:21
  • 3
    Linked lists should insert in O(1) – fortea Mar 05 '20 at 12:24
  • @Mugen ...isn't that normal behavior for a linked list? You can't insert into the middle without walking to that position. – user3932000 Nov 29 '20 at 00:27
  • 1
    @user3932000 But suppose you walk up to that position you should be able to insert right? – Mugen Dec 14 '20 at 07:20
  • This is untrue, please edit – Tomer Gal Mar 11 '22 at 11:24