https://kotlinlang.org logo
Join Slack
Powered by
```fun foo(lastEntry: Entry) { val myList = mutab...
# announcements
l
Copy code
fun foo(lastEntry: Entry) {
	val myList = mutableListOf<Entry>()
	var currentEntry = lastEntry
	do {
		myList.add(currentEntry)
		currentEntry = currentEntry.parent
	} while (currentEntry != null)
	myList.reverse()
}
how can i simplify this pseudo code so I don't have to perform 
.reverse()
at the end ?
k
try myList.add(0, currentEntry)
l
but wouldnt that be very poor performance wise since i'd move all elements in the list every time i add a new one?
k
myList.add(0, currentEntry) it always add new element on first index
what do you mean by “move all elements in the list every time i add a new one”?
l
lists are usually backed by an array (unless you're using a linked list) which means all elements are stored in an array until its full, at which point a new (larger) array is allocated. inserting an element at index 0 would mean moving all other elements in that array by one
your proposal does do what i want, but with even worse performance than what i currently have
k
so whyn’t you try LinkedList here?
l
linked lists are slow in other ways, eg accessing the 57th element requires following 57 pointers whereas in an arraylist the target location in memory is calculated (index*size)
k
yes right, then your own code seems correct here 🙂 but if you find more optimise approach then please do share here too
l
i figured out a recursive approach, but im not sure if its optimal yet:
Copy code
fun foo(lastElement: Element) {
	val myList = mutableListOf<Element>()
	fun addAfterParent(element: Element) {
		if (element.parent != null) addAfterParent(element.parent)
		myList.add(element)
	}
}
d
Copy code
val list = generateSequence(lastEntry) { it.parent }.toMutableList().reverse()
I think the reverse is fine. You're converting a linked list (of unknown size) to a fixed size array. It can't be helped.
l
you're converting a linked list
thats not necessarily the case
i might be starting out with an arraylist already
d
Oh. I mean the whole 
currentEntry.parent
is of unknown size right?
l
ah thats what you meant
yes, we initially dont have any information how long the chain goes
but that doesnt imply the necessity of a reversal after we've already navigated all the way through it
d
There's the option of returning a reverse "view" of the list.
You might run out of stack if you use recursion though.
l
thats why im not happy with the recursive approach. what does "reverse view" mean?
d
Implement an 
AbstractList
wrapper that accesses the underlying 
List
with the reverse index. 😛
Like this.
Copy code
class ReverseList<T>(private val list: List<T>) : AbstractList<T>() {
	override val size: Int get() = list.size
	override fun get(index: Int): T = list.get(list.lastIndex - index)
}
l
thats an interesting approach. but what if the order (time, not index) in which the elements are added to the list is relevant ? (this can sometimes be the case with observable lists)
d
Ah. I think you'll need a temporary list in that case. To correct the insertion order. In the end the reversal can't be helped, whether you do it with the stack or an explicit List.
l
wdym it cant be helped? the recursive approach doesnt require a reversal
d
The recursive approach, puts all the elements onto the stack (instead of a 
MutableList
) and then iterates through in the reverse order.
l
yes, but the only part that is inevitable is that we need to navigate through the entire chain. in your first example however we end up doing that PLUS a reversal in post
d
Do you just literally want to not call the 
reverse
function? Or are you trying to optimise?
l
optimise
d
Idk, best to benchmark at this point. I think reversal is the simple way to go but you can get numbers to give you an objective answer.
2 Views
Open in Slack
PreviousNext
Powered by