Linked Lists

Created By: Geoffrey Challen
/ Updated: 2022-05-23

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

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.

Provide an overview of the difference between array lists and linked lists using a paper diagram.

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.

Set up the linked list class and implement the constructor and add but only at the front.

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

Use a diagram to help explain how add to front works.

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!

Discuss the use of inner classes, and their application in this case to hide private state.

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:

Explain how to walk a list using a diagram.

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

Implement get by walking the list using a loop. Analyze its performance.

But what about add and remove? We'll get there! Next time...

Show how to complete the homework problem above. Feel free to cover multiple approaches!

More Practice

Need more practice? Head over to the practice page.