Linked Lists

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.

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!

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:

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 Restricted to Current CS 124 Students

A publicly-accessible version of this content is available at learncs.online.

Homework: SimpleLinkedList set

Created By: Geoffrey Challen

/ 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.

WorkingPrevious

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 add(

index: Int,

value: Any?,

) {

require(index == 0) { "Non-zero add not supported yet" }

start = Item(value, start)

size++

}

fun get(index: Int): Any? {

More Practice

Need more practice? Head over to the practice page.