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.
We promised that as we continue building data structures and implementing and analyzing algorithms, we’d also meet some new Java 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 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
Click on an icon below to start!
But what about add and remove?
We’ll get there!
Homework: SimpleLinkedList set
Created By: learncs.online 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.