As far as I know, kotlin doesn’t provide LinkedList (Sequential Access variant of ArrayList) implementation.
I want to understand the reason behind this ? What makes designer not to implement this ?
2 Likes
It does support it. When you are using KotlinJvm you can simply use javas LinkedList. On Js and Native I’m currently not aware of any LinkedList implementations. Looking through the issue list on https://youtrack.jetbrains.com/issues/KT I can’t find any current plans on implementing a LinkedList for the other platforms, so if you realy need it and you are using Kotlin MPP, Kotlin JS or K/N you probably need to implement it yourself (for now). I’d also suggest you create an issue (linke see above).
This is all a guess, but here it is: At the beginning there was only Kotlin JVM so there was no need to implement any List implementation since Kotlin just uses the java implementations. Later when Js was added I just don’t think there was a big focus on it. The fact that the issue tracker has nearly no mentions of LinkedList means that people just don’t really use it (or at least not on js/native). Compared with other List implementations LinkedList just has realy bad performance and get’s outperformed by ArrayList in nearly every situation, even used as a Dequeue.
1 Like
Thanks for your answer, gave me some hint, but not so clear about kotlin designer intentions yet. Modified question wordings to make it more clear.
Nobody needs it. Java’s LinkedList is close to useless, and in JS it would also be very inefficient.
8 Likes
This. It is a conscious decision not to include LinkedList. It is not just useless, it is actually harmful, since people start using it where they should not have been.
8 Likes
There is a project to reproduce some core Java functionality on kotlin-multiplatform here: GitHub - kotlin-extra-library/kotlin-extlib: Kotlin community common multiplatform library. But when it comes to LinkedList I agree with @elizarov and @mtimmerm. It is just not usable. Fast injection of elements inside the list (the only think LinkedList is good for) is almost never used and could be done by other means.
1 Like
Linked lists are extremely efficient for sequentially accessing elements from one end or for adding elements to one end. They are not for accessing elements by index or for some bulk operations like reversing. But they are never dangerous. Only programmers can be dangerous.
Immutable linked lists are missing in Kotlin. They are easy to implement, but it would be better if they were standard, since they are much better for some use cases than what Kotlin offers. Adding an element in front of a “non-modifiable” list is painful and inefficient. How should we do it? Should we use a mutable list? But what if we need to share the list? Or simply reuse it later? Should we make defensive copies?
In my opinion, using “non modifiable” lists as if they where immutable, or using mutable lists when you need immutable ones, is far more dangerous than using immutable, data sharing, linked lists, specifically if the “dangerous” operations have not been implemented on them. And no, fast injection of elements inside the list is not the only thing LinkedList is good for. On the contrary, it may be the worst thing to do with a linked list, depending upon how it is implemented.
Sure, bad Java mutable data structures should not be reproduced. But on the other end fact, all immutable data structures are missing (linked list, doubly linked list, heap, finger trees and more).
3 Likes
If you are looking for immutable collections you should take a look at this. However this is not really what was talked about here. I’m not an expert on immutable data structures, but I can see the advantage on one, based on a LinkedList. However a mutable version of LinkedList (like the one in java) is not a good idea for the standard library as pointed out above.
Respect your thoughts @elizarov
But most of good things in real world or programming world can be used in harmful way, we can’t stop people mis-using it and we must not stop providing good things in fear of being misused.
LinkedList can be used for Queue, Deque or Stack implementation avoiding static continuous memory allocation/deallocation overhead, b’coz it works on dynamic memory allocation. And in these cases, we never require direct access which may be harm for performance.
If I use Kotlin for competitive programming, then I would expect that some basic functionality like LinkedList must be available handy for my long algorithms. Don’t you agree with this ?
Can someone point to some reliable benchmark where a linked-bucket data structure cleanly outperforms an array-based one in a common use case?
I’m really interested.
Thank you in advance.
2 Likes
I decided not to write a reply about it. But in general linked structure will be slower because of additional memory indirection. I think that modern JVM could optimize it away, but it will be definitely not faster.
@sandeep549 I cannot agree with you. All deques (incl. queues and stack) are much faster when they are based on arrays. You should never use linked lists for that purpose, especially if you do competitive programming where performance is important.
You only need linked lists when you need to insert into the middle in O(1). This almost never happens in practice and extremely rarely needed in competitive programming. When it does happen you usually need an “intrusive list” which Java’s LinkedList does not provide anyway.
3 Likes
I totally agree with the fact, that LinkedList as implemented in java is suboptimal in nearly all cases. That said, I just looked through the kotlin standard library and there doesn’t seems to be any Queue or Stack interfaces nor implementations. I know that kotlin-extlib(linked by @darksnake) provides those, but I wonder why they aren’t part of the standard library already. Stuff like this would definetly help kotlin mpp. Maybe this library should be incorporated into an offical kotlin library (at least parts of it). Otherwise we will just end up with a JS like situation where everyone end everything is providing similar solutions to the same problems.
@elizarov Thanks for your reply !!! Seems like you caught me here.
I was under impression that array based Queue, Stack Implementation(i.e ArrayDeque) will be slower compared to LinkedList based, because of array resize overhead involved.
But I see (checked some benchmarks online), despite of this resize overhead in array based implementation, ArrayDeque is faster for stack and queue operations, even when there is no iteration involved at all.
Thanks a ton for letting me know designer thoughts behind this.
1 Like
Thanks for this interesting discussion. Only thing I would like to say is that I subscribe to the notion that Deque / Queue / Stack interfaces would be nice to have in stdlib - although they are so trivial we can implement them ourselves.
I have a problem with that idea. While this might be ok if you are developing an application this will lead to problems if multiple libraries add their own versions of the interfaces, because combining those libraries will require some sort of bridge between the interface.
While I don’t dislike the idea of libraries like kotlin-extlib, it still leads to problems. One is that the intefaces there aren’t the same as the jvm ones which can only be done in the standard library I think.
The other issue is that it isn’t that well known and therefor has a small impact.
About the jvm interfaces, this isn’t really part of this discussion, but can you have an expect interface like
// common code
expect interface Queue<T> {
fun push(element: T)
...
}
// jvm code
actual typealias Queue<T> = java.lang.Queue<T>
This would at least sovle one problem I have with this being implemented outside of the standard library.
Linked lists are extremely efficient for sequentially accessing elements from one end
In fact they are pretty inefficient even for this access pattern, due to pointer chasing.
But they are never dangerous. Only programmers can be dangerous.
Another funny quote: “Guns don’t kill people. People kill people.” Giving the user a means to do damage is dangerous, especially when the user is not even aware of it.
In fact they are pretty inefficient even for this access pattern, due to pointer chasing.
It could have been interesting to compare your implementation of an immutable persistent (non-linked) list to the common implementation of an immutable persistent linked list, but
Another funny quote: “Guns don’t kill people. People kill people.” Giving the user a means to do damage is dangerous, especially when the user is not even aware of it.
Is it possible to have an interesting discussion with someone who:
-
thinks the comparison between the danger of guns and the danger of linked list is relevant to the discussion,
-
implies that I would be pro-guns (base upon what?) and that this would be relevant to the discussion,
-
implies that programmers are too stupid to be given tools that could be as dangerous as linked lists,
Seriously? Given the utmost irrelevance of these arguments, implying that programmers might not be as smart as you are is really insulting.
I wonder how a person with such a profuse inability to comprehend analogies gets by in everyday life.
4 Likes
This may not prevent you feeling insulted, but … @mtopolnik might have been including himself. I consider myself a reasonably smart developer, but the world of software is ridiculously complicated these days, and I’m sure I do the wrong thing at least once a week, if not once a day. Generally I welcome anything which by default avoids programmers, including me, doing the wrong thing in the majority of cases. I certainly would have picked a linked list for some use cases but now, reading this, I’ll be more likely to do performance tests where I think it might matter.
4 Likes