In Kotlin, are data structures such as stack, queue, heap, tree, etc. supported through standard library?

Question

In Kotlin, are data structures such as stack, queue, heap, tree, etc. supported through standard library?

As a person mostly familiar with Python but didn't use Java before jumping into Kotlin, this question came to my mind.

For example, if one wants to use Kotlin for competitive programming, or if one doesn't want to reinvent the wheel implementing the common data structures, are these supported through the standard library? Or are they not supported due to some design reason of Kotlin? At least I wasn't able to find these in the documentation. Then if one is using Kotlin on JVM, do people usually use the implementations from Java's library?

Answer 1

Kotlin mostly reuses Java's Collection API in this case, so you can utilize it freely. Collection API has 4 major interfaces:

1. List - an ordered sequence of elements.
2. Set - collection that has no duplicates.
3. Queue - a collection designed for holding elements prior to processing. You can utilize it's FIFO interface. Also it is extended with Deque interface which supports elements' insertion and removal at both ends.
4. Map - an object that maps keys to values.

Most of the needs can be satisfied with this interfaces' implementations.

Such as LinkedList as a classic implementation in terms of Doubly Linked List data structure; also it implements Deque. ArrayList implements List interface using array internally; it has much faster elements access due to arrays' indexed access efficiency nature (except of the case when you are accessing either first or last elements, because than it's identical), but insertions can really cost you on insertions not in the end or on insertions when the capacity of the internal array is exceeded, because it then should get reinitialized and refilled, which is a hit for both time and space. Java's internal System#arraycopy is internally relatively fast though.

Stack and Queue both can be also fulfilled with ArrayDeque, which is, again, an array-backed implementation, but in this case of Deque.

TreeMap uses Red-Black tree algorithm internally; TreeSet uses TreeMap internally is you need single elements rather than associations.

For hashtable-based implementations you can use HashMap for associations and HashSet for sole elements respectively (same story with reuse as for tree-based implementations).

For all the other things (thread-safe too - designed for concurrency or simple locking-applying decorators) you can search for an appropriate implementations of these interfaces actually - the standard library is big enough.

Answer 2

Adding to the above answer, Java's implementation of Heap is PriorityQueue, passing a comparator appropriately, and you can use it in Kotlin no problem.

Docs: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Check more: https://www.geeksforgeeks.org/priority-queue-class-in-java-2/