https://kotlinlang.org logo
#getting-started
Title
# getting-started
o

oday

07/01/2021, 5:00 PM
something really weird is happening here https://paste.ofcode.org/uf6LdvHyQQfTpNYmVKR2nE
reverseIterative()
is changing the Node object for some reason..
k

Klitos Kyriacou

07/01/2021, 5:14 PM
Why are you expecting it not to? As a hint, try making your structure immutable by changing the fields to
val
instead of
var
and see where it complains.
o

oday

07/01/2021, 5:19 PM
hmm
why was expecting it not to..
well it complains where I reassign next and prev
oh you mean Node’s
value
and
next
k

Klitos Kyriacou

07/01/2021, 5:22 PM
yes
o

oday

07/01/2021, 5:23 PM
well yea now the whole algorithm for reverseRecursive complains since I do a lot of those changes in there, also
current.next = prev
will complain
i can use copy
well that did it
so its pass by value
ok so I’m stuck on this, how can I make this edit
Copy code
node.next?.next = node
when
next
is now a val this is the code for this one https://paste.ofcode.org/umxk2HQsUHM7XGMCs6phK7
k, moving on
r

Roukanken

07/01/2021, 7:45 PM
Note that a) you changed the condition when you return
Copy code
if (head?.next != null)
        return head
you should return when it is null, same as before b)
head = head?.next.copy(next = head)
this line does NOT do what you think it does: it's same as
head = (head?.next).copy(next = head)
which means you will assign modified copy of
head?.next
to head, and not copy of
head
c) if you look how to fix
b)
you notice that you can't really easily do "add head at last of the list returned" without a lot of overhead - you would likely need a helper function to return 2 nodes: start and end, and then just forget the one on top-level function
o

oday

07/01/2021, 10:25 PM
I see, yes I am copying from Java actually, pasted it and got the first iteration that im trying to modify, the modified version is mine
I don’t see how immutability helps here
it’s a massive pain
who doesn’t use
head.next = somethingElse
when working with LinkedLists..
r

Roukanken

07/02/2021, 6:28 AM
tbh, immutable LinkedList is fairly impossible to handle, as you would need to copy entire list for every little change you do in it. BUT, if you want to create a reversed list, then you DO need create a copy of it, if you still want the original to exist
o

oday

07/02/2021, 6:59 AM
agreed on both points thanks for pitching in
r

Roukanken

07/02/2021, 7:03 AM
what you should be doing is basically, creating a (reversed) copy as you iterate trough the list (by recursion or w/e), and then just return the newly created list when you reach the end of it
k

Klitos Kyriacou

07/02/2021, 8:41 AM
I don't agree that with immutable linked lists "you would need to copy the entire list for every little change". If you're adding an element to the front of the list, all you need to do is create a new node that has
.next
assigned to the existing list. For most other modifications, maybe you're right.
r

Roukanken

07/02/2021, 8:45 AM
*copy every entry in before the place you are changing Happy? 😄 Only thing you can do effectively with immutable LinkedList is a Stack basically
o

oday

07/02/2021, 9:06 AM
the thing is, I have a technical interview soon with big corp, and I would like to choose Kotlin as a main language
if something like this comes up and I start copying and going all over the place…yea
r

Roukanken

07/02/2021, 9:25 AM
Well... as I said, to reverse a Linked list you need to copy: otherwise you destroy the previous list Here is some quick solution, using recursion: https://pl.kotl.in/geLwiQIYW
o

oday

07/02/2021, 11:48 AM
@Roukanken is there a resource where common data structures are implemented in Kotlin from a reputable source?
I was going over Raywenderlich’s “Data Structures and Algorithms in Kotlin” book and they implement the LinkedList as a MutableCollection, I want the raw version of the implementation
r

Roukanken

07/02/2021, 12:19 PM
uuuuh... not sure what you mean by "raw" version? I briefly looked into the book you mentioned and I don't see anything wrong with it...
o

oday

07/02/2021, 12:44 PM
hm
yea I think I don’t understand the core properties that make a LinkedList what it is, I mean they just added an iterator and now it’s a literal list, I thought it was a proverbial list cause there’s a pointer to the next node and so they follow each other in a list fashion
r

Roukanken

07/02/2021, 12:53 PM
whatcha think a "List" is?
o

oday

07/02/2021, 12:53 PM
memory with pointer to next memory
how the hell am I gonna pass 🤦🏻‍♂️
r

Roukanken

07/02/2021, 12:55 PM
that's just an (example of) implementation of a List List itself is just "Structure that holds variable amount of items with specified order"
a LinkedList is a List (holds item, and pointer to next) an ArrayList is a List (is an Array - an fixed amount of items, and it doubles it's size when needed, magic math ensures it's effective) you could think up your own List implementation, for example let's think up FileList - it holds it's items in several files, only working with 1 at time to save memory, and when it needs to work with another it saves the file, and loads the other one. There are thousands of different ways to make a List (ofcourse not all of them are effective!) Anyways the point is: List is just a concept of "multiple items in specified order". And LinkedList definitely fits this concept
o

oday

07/02/2021, 1:52 PM
Thanks a lot for elaborating, I think what’s confusing me is that book’s approach, and now look at this which I think is more akin to the approach that I was going with without any iterator or any utility to help, just 1 by 1 going through the list changing
current
to the next and so on https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Kotlin/blob/master/Chapter03/LinkyList.kt
ok so before turning it to a Collection they mention
Copy code
At this point, you've defined an interface for a linked list that most programmers around the world can relate to. However, there's work to be done to adorn the Kotlin semantics. In the next half of the chapter, you'll focus on making the interface better by bringing it closer to idiomatic Kotlin.
the part after that tripped me up, making it kotliny
alright I get it now 💪🏻
r

Roukanken

07/02/2021, 2:25 PM
they basically want to make it easily useable by users If you wanted to use a List, you would for example expect to be able to do:
Copy code
class LinkedList<T> {
    // TODO
}

val data: LinkedList<Int> = TODO()
for (item: Int in data) {
    println(item)
}
Kotlin will not allow you to do this - it does not know how to get and fill the
item
variable from the
data
structure This will throw you an
For-loop range must have an 'iterator()' method
error
o

oday

07/02/2021, 2:27 PM
that’s why they went for MutableCollection and provided an iterator and everything that comes with that interface, makes sense for the scope of the interview, I will be more facing stuff like the logic behind push and remove and insertAt, etc.. I think
if that even
r

Roukanken

07/02/2021, 2:28 PM
ye, basically to make it more user friendly the functions on how LinkedList works are properly implemented even before that - the Iterator/Collection stuff is so the rest of Kotlin knows how to properly work with the new structure
for example, the
Iterable<T>
forces you to implement the
iterator()
method, and when you do that, then the for cycle above will work properly
also Kotlin's stdlib defines function
Iterable<Int>.sum(): Int
which would mean that this would work too: (ofc after being implemented properly, instead of TODO)
Copy code
class LinkedList<T>: Iterable<T> {
    // TODO

    override fun iterator(): Iterator<T> {
        TODO()
    }
}

val data: LinkedList<Int> = TODO()
println(data.sum())
as the implementation of
sum()
function does not need to know how structure works, only be able to know it's contents (handled by
Iterable<T>
) and be able to sum it's items (it's collection of
Int
so it can sum)
4 Views