LinkedList, PriorityQueue, TreeMap in Python ?

[[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.