Welcome back! Today we'll continue discussing lists, but explore a new approach: linked lists. No arrays required! Let's get to it...
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.
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.
Confused? OK! Let's look at the same code but using a diagram!
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!
Next let's go on and implement
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.
But what about
We'll get there!