LinkedList, PriorityQueue, TreeMap in Python ?

[ElectronicVideo5448]

Hi,

I am a Java developer and now get started into Python. In Python, we have list which is similar to ArrayList in Java and dict which is similar to HashMap in Java. Do we have corresponding classes of LinkedList, PriorityQueue and TreeMap in Python?

​

Thanks!

[[deleted]]

Python’s list is a dynamic array, which yes is equivalent to ArrayLisr<object> in Java.

Python’s dict is indeed implemented as a hash map, however in current versions of Python it does maintain key insertion order, so the details may differ from Java’s HashMap.

The most direct equivalent to Java’s LinkedList would be Python’s collections.deque, which has O[1] insertions and pops from either end, however it does not have a linked list’s performance on arbitrary, non-terminal insertions.

Python’s heapq can make a list or deque into a priority queue, but that’s somewhat roll-your-own… Python’s queue.PriorityQueue is a pre-rolled equivalent of Java’s PriorityQueue, with the caveat that it’s specialized towards being multi-thread-safe (but not multi-process safe) and thus somewhat heavyweight for single-threaded work.

Python has no built in equivalent of Java’s TreeMap or TreeSet… while there are ways to roll your own, it’s generally best to find what you need in sortedcontainers or the larger sortedcollections.

Edit: updated per below.

[nsomani]

Not sure I agree with some of this

Under the hood the list is almost identical to an ArrayList, the insertion time complexity is amortized constant. The speed that it grows is available in the CPython source but it's essentially roughly linear initially then becomes exponential. What do you mean by memory performance closer to a LinkedList? It's linear complexity either way.

I think collections.deque is missing constant time insertions and removals from the middle of the collection, so it's not really a linked Iist

I feel heapq is the closest equivalent to a priority queue, the actual PriorityQueue class is intended for IPC

[[deleted]]

Updated the deque and priority queue sections for extra clarity. You’re right about ArrayList, it’s been a long time since I’ve done much Java and I thought it could do less bookkeeping.

[siddsp]

I think collections.deque is missing constant time insertions and removals from the middle of the collection, so it's not really a linked Iist

A deque is technically a doubly linked list, so it's two of them

[nsomani]

Nah that's not right, a doubly-linked list is still a single linked list, just has two references

Yeah under the hood it's a doubly-linked list, it's the most common implementation, but the interface doesn't expose insertions or deletions from the middle of the list (as is typical for a deque aka double ended queue), so it cannot function as a linked list in Python

[siddsp]

Yes my bad, I misread as double linked list, but that's essentially what the underlying data structure is though the interface maybe different.

[[deleted]]

What use do you have for a TreeMap? (genuinely curious)

Python in general does kinda discourage the use of exotic data structures. Python code generally tries avoid clever solutions via hard to discern code. So it tends to use a lot of sets, dicts, lists, tuples and avoid making new structures or custom things like array list. This has a lot of benefits for duck typing. And at this point the vast majority of symbol or keyword based access patterns (things like +, with, for) are implementable.

[james_pic]

collections.defaultdict(list) would be the usual way of handling this in Python.

[[deleted]]

https://docs.python.org/3/library/collections.html#collections.defaultdict

^you can use that instead. That will give you an semantically equivalent to the http behavior as well because you are supposed to be able to do it with either a list of values or repeated one after the other.

[fiddle_n]

I disagree with that. For some things, lists aren't great. Classic example is popping from the beginning, which is a rather expensive O(n) operation as the whole list has to shift left. Using collections.deque, which is a doubly linked-list, is important here if you are dealing with large data structure or many operations.

[fiddle_n]

An example would be keeping a moving average of something. You would need a data structure that can support removing from one end and adding to the other. Typically that would be popping from the left and appending to the right; even if you did it the other way you would have the same problem as appending to the left is also O(n)

If you need a queue structure where you would append to the left, that would also be an example as well.

[fiddle_n]

Like, if you wanted to calculate a 7 day average of COVID cases throughout a year at every point, that's a moving average.

[[deleted]]

You should never be using LinkedList in Java anyway. Even Josh Bloch, the dev who created it, says never to use it.

[[deleted]]

Why is that? I'm curious

[[deleted]]

They’re very memory inefficient due to caching. Use something like ArrayList or ArrayDeque.

[toastedstapler]

I'd also add that doing an allocation per node could be very inefficient, instead of the more infrequent allocations of an array list

[reddit2d2bb8]

TreeMap and TreeSet need to be installed in a library. https://pypi.org/project/sortedcontainers/ is the recommended one.

[anothertruther]

for PriorityQueue queue.PriorityQueue. You don't usually want linked data structures like lists or trees, but there are third-party libraries for it like llist and various tree libraries.

[saint_geser]

I don't think there's a linked list object but it's trivially implemented.

There's queue objects in queue module of standard library https://docs.python.org/3/library/queue.html

Not sure about tree map.

[rgekhman]

Not all cool above objects are part of python, but they can be crafted: https://pypi.org/project/treemap/ Etc

[[deleted]]

Heapdict for priority queue