https://kotlinlang.org logo
Join SlackCommunities
Powered by
Learning data structures in kotlin and was curious...
# getting-started
c
Learning data structures in kotlin and was curious if/why there wasn't a LinkedList impl in kotlin. Anyone know what 
@elizarov
was talking about here that itd be "harmful" to have it?
e
in theory, there could be some unique advantages to 
LinkedList
. however, by conforming to the 
List
interface, none of those are realized in Java at all
instead, you have a strange list where 
get()
is linear-time, unlike every other list in existence
c
in addition to the extra memory overhead for storage - each entry requires additional references to the next item.
e
correct, the memory overhead per element is ~quadruple what an ArrayList needs (with allocator metadata included), and the additional reference-following required is more overhead as well
LinkedBlockingQueue shows some of what you can do with a linked list that doesn't conform to the List interface
c
So... if I needed to use a linked list... is the general concensus that you'd just implement your own?
e
but in Kotlin we can just treat that as an internal implementation detail of Channel
c
Oh LinkedBlockingQueue is a thing?
c
depends what the need really is
e
in almost all circumstances I'd just use an ArrayList (e.g. normal list in Kotlin), or possibly an ArrayDeque if you have mutation at both ends
c
I suppose so 😂 Right now... I'm studying data structures for whiteboarding style interview questions (unfortunately)
c
or possibly a Kotlin channel if the structure is intended to drive concurrent workloads.
c
So if someone said "does kotlin have a linkedList impl" the answer would be no?
What about stack or queue? I suppose you can use a Deque and it can be a stack, queue, or LL?
e
I would say no, it does not.
❤️ 1
a MutableList is a completely serviceable stack
➕ 1
c
Thanks for teaching btw. Datastructures scare me. 🙃 so interviewing has not been fun. lol
c
at least not part of the Kotlin standard library. You can use Java’s LinkedList or other 3rd party libs that implement it.
👍 1
e
and ArrayDeque is a completely serviceable queue (or stack, but you don't need its double-ended-ness)
k
You have Stack in Java right? But it uses the vector interface and should not be used?
e
yes, Vector and other old Java collections such as Stack have internal synchronization which both unnecessary for almost all purposes and insufficient when it actually matters
c
along with their sickly cousin, Hashtable…
e
feels like Java 1.0's classpath library was made from a CS101 course 😓
c
textbook -> java library. 🤦
e
something I do think is missing from kotlin stdlib is a priority queue (usually implemented with a binary heap). but you can usually just use Java's, and it's like 30 lines of code if you can't, so it's not that bad
👍 1
k
Yeah, that is probably the only one I have used outside of the kotlin stdlib.
e
f
Nitpick, 
storage
should be 
val
in that gist
c
wow. thanks everyone. learning a ton. i very much am brushing up on datastructures and learning more about java and kotlin
j
In that Kotlin thread Elizarov explains why indeed
@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.
t
As long as you can increase the size of the arrays in amortized constant time (which ArrayList does), and can keep track of where you are at each end, a doubly-linked list can be faked with an array very nicely. The only disadvantage is that you could end up with an array where lots of the elements are unused. At that point, you have a choice between resizing or wasting the memory. So one advantage of a true linked list implementation is that adding and deleting elements is constant time for every operation, whereas they’ll be mostly constant time for an array-based implementation with occasional pauses when the array needs to be resized either larger or smaller. If you don’t mind those occasional hiccups, use the array.
e
allocating the memory for a new link node can also result in pauses, so that isn't as large of an advantage as it sounds
being able to atomically insert without locks is a thing that linked lists could do over array lists, but that is not something that Java's LinkedList is capable of due to its interface
a

https://youtu.be/YQs6IC-vgmo▾

p
In functional programming linked lists are always used as the #1 data structure.
t
ephemient [8:07 PM]
allocating the memory for a new link node can also result in pauses, so that isn’t as large of an advantage as it sounds
But only if there’s garbage collection or a similar issue. If you have an array representing a list of 10k items, and you’ve run out of space, the default code for ArrayList is going to allocate an array of size 20k and copy all 10k elements of the first array into it. Adding to either end of a linked list (assuming you have references to both ends) will involve allocation of a new node and the setting of three references: the previous end gets a reference to the new node, the new node gets a reference to the previous end, and the new node gets a reference to whatever is used to indicated end-ness, null or a dummy reference. The work is literally constant every time. It’s true that the JVM could decide to do something else during that time, but it’s a guarantee with an array implementation that every so often, you will be doing a lot more work for some operations because of the way that add works on ArrayList.
👍 1
e
by the time you've gotten to 10k elements, a linked list is much more likely to have added significant memory pressure to the rest of your program than an ArrayList (which is a lot less work for GC to scan). the work is "constant", but that's a simplification. amortized work is what makes GC faster at allocation under most common circumstances.
Pavel, true in that it works well as an immutable, recursive data structure. but a. that is not what is presented by LinkedList, and b. even in functional programming languages, we recognize that (linked) lists are not a good data structure for many purposes. as a long-time Haskell programmer, I can confidently state that the most important use of a linked list there is for control flow. you should expect that most "lists" get fused and thus are never materialized in full; if a non-trivial list grows to any significant size, it is a code smell or a design error
👍 1
a
The most important reason is that because elements of linked lists are not compact in memory, linked lists greatly increase cache misses, which is why even traversing linked lists (or searching for the position to insert or delete) is much slower than traversing array lists (50~100 times slower according to the talk I posted above). This makes the usage of linked lists very very limited.
k
On the subject of cache misses, simply traversing an ArrayList, without actually looking at the content of each element, does indeed make good use of the CPU cache. However, on the JVM an ArrayList is a list of Objects; even integers are boxed when put into an ArrayList. This means that reading each element of an ArrayList can end up in lots of cache misses because the elements' contents may be stored all over the heap, instead of being contiguous. For better performance there are primitive collection libraries, such as Trove, Fastutil and Eclipse Collections.
p
@ephemient how often do you deal with arrays of 10k elements anyways? Maybe once a year you will write a program that does that. I never do that and I work in big data. In Scala I always use lists.
e
back when I worked with Scala, we used 
Seq
for almost everything. but even so: Scala's 
List
isn't 
SeqLike
so it doesn't suffer the stupid API issues that Java's 
LinkedList
does
p
@ephemient java’s linked list mostly useless indeed, although i hear that LinkedHashMap uses it to preserve insertion order, you can remove a node from LinkedList in O(1) time
c
Java’s LinkedHashMap doesn’t use LinkedList; the code shows it’s own, internal, use-case-specific linking structure.
p
@Chris Lee thanks for pointing out, but still, that structure is a linked list, even though it isn’t java.util.LinkedList, I meant that in general there are use cases for linked lists,
e
there are uses for data structures with internal links. but what LinkedHashMap does with its nodes cannot be done with an external linked list, so a LinkedList ADT has very little utility
this is consistent with Roman's position in the thread as well
c
ADT?
e
as opposed to https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction for example - that's much more useful for linked lists
but it's not something that can be represented in Java/Kotlin in a way that fits in with the rest of the language
4 Views
Open in Slack
PreviousNext
Powered by