KotlinCS 124 LogoJava

Linked Lists

interface SimpleList {
fun get(index: Int): Any?
fun set(index: Int, value: Any?)
fun remove(index: Int): Any?
fun add(index: Int, value: Any?)
}
class SimpleLinkedList(values: Array<Any?>) : 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! Next we’ll continue discussing lists, but explore a new approach: linked lists. No arrays required! Let’s get to it…

Linked Lists
Linked Lists

So far we’ve seen how to implement a list using an array to store the references. However, the array was also maintaining the order!

But this is not the only way! Let’s look at another approach that uses references to link items together into a chain. First we’ll explore it on paper, and then start our implementation, and check out a few diagrams along the way.

https://www.youtube.com/watch?v=XArdwd-iZ-0

Linked List Constructor
Linked List Constructor

Next, let’s look at how to create our linked list constructor, and a simple version of add that only supports adding items to the front of the list.

// SimpleLinkedList constructor and add to front

Confused? OK! Let’s look at the same code but using a diagram!

https://www.youtube.com/watch?v=y8wCYLaN-rQ

Inner Classes
Inner Classes

We promised that as we continue building data structures and implementing and analyzing algorithms, we’d also meet some new Kotlin syntax along the way. You may have noticed our implementation uses something called an inner (or nested) class. Let’s examine that more carefully!

// Inner Classes

SimpleLinkedList get
SimpleLinkedList get

Next let’s go on and implement get. But first, we need to think about how we are actually going to walk the list! Let’s see that in a diagram first:

https://www.youtube.com/watch?v=6o7mR23LBKA

And now, we’ll complete our implementation of get and consider its performance.

// SimpleLinkedList get

But what about add and remove? We’ll get there! Next time…

Homework: SimpleLinkedList set

Created By: CS 124 Staff
/ Version: 2020.10.0

Let's implement a list using a different strategy. Instead of an internal array, we'll link items together into a chain using references. Our list class will only maintain a reference to the start of the list and walk the list to perform list operations. This approach will have interesting tradeoffs compared to our implementation that used arrays.

Starting with the SimpleLinkedList class below, complete the code for set. You'll want to review get and the rest of the code to understand how this list implementation works and how to walk a linked list.

More Practice

Need more practice? Head over to the practice page.

˝