Kotlinlearncs.online LogoJava

Lists Review and Performance

interface SimpleList {
fun get(index: Int): Any?
fun set(index: Int, value: Any?)
fun remove(index: Int): Any?
fun add(index: Int, value: Any?)
fun size(): Int
}
class SimpleLinkedList(values: Array<Any?> = arrayOf()) : SimpleList {
private inner class Item(var value: Any?, var next: Item?)
private var start: Item? = null
private var size = 0
init {
for (i in values.indices.reversed()) {
add(0, values[i])

Welcome back! In this lesson we’re going to wrap up our discussion of lists. First, we’ll make some forward progress on our linked list implementation. Then, we’ll compare and contrast the two performance of our two approaches.

Warm Up Debugging Challenge
Warm Up Debugging Challenge

But! Let’s warm up with another debugging challenge!

Declare a function named adder. adder takes a single Int parameter and returns a method that implements the Modify functional interface:

The returned "function" should implement modify so that it adds the value passed to adder. So, for example:

The correct solution to this problem is a single line lambda expression!

Linked List Remove
Linked List Remove

At this point we can initialize our linked lists and get and set items. But what about add and remove? It’s not a list yet!

Both add and remove require adjusting the linkage to either insert or delete elements. This is tricky! Let’s start with remove. First, let’s look at what needs to happen using a diagram.

OK, now let’s take a stab at this in code!

// SimpleLinkedList remove

Linked List Add
Linked List Add

What about add? We’ll leave that for you to work on… But, to help you get started, let’s diagram it first:

ArrayList v. LinkedList Performance
ArrayList v. LinkedList Performance

Let’s examine the performance tradeoffs of our ArrayList versus our LinkedList.

Now, you might be wondering why anyone would use a linked list, ever! However, there are applications that only ever modify the ends of the list!

For example, consider a help queue. Requests are added at one end and removed from the other. So we are only ever modifying the front or the end of the list.

Modifying the front of a linked list is O(1). But what about the end? Could we make that O(1) too? Sure! Let’s see how.

// Optimizing addToEnd

Homework: SimpleLinkedList add

Created By: learncs.online Staff
/ Version: 2020.10.0

Continuing with the SimpleLinkedList class below, complete the code for add. You'll want review the rest of the code to understand how this list implementation works and how to walk a linked list and manipulate the references properly.

class SimpleLinkedList(values: Array<Any?>) {
private inner class Item(var value: Any?, var next: Item?)
private var start: Item? = null
private var size = 0
init {
for (value in values.reversed()) {
add(0, value)
}
}
fun size() = size
private fun walkTo(index: Int): Item {
require(index in 0 until size)
var current = start
repeat(index) {
current = current!!.next
}
return current!!
}
fun add(index: Int, value: Any?) {

More Practice

Need more practice? Head over to the practice page.