SimpleLinkedList set
Geoffrey Challen // 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.
public class SimpleLinkedList {
private class Item {
private Object value;
private Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
private Item start;
private int size;
public SimpleLinkedList(Object[] values) {
assert values != null;
for (int i = values.length - 1; i >= 0; i--) {
add(0, values[i]);
}
}
public int size() {
return size;
}
private void add(int index, Object value) {
assert index == 0 : "No support for general add yet";
start = new Item(value, start);
size++;
}
public Object get(int index) {
assert index >= 0 && index < size;
int currentIndex = 0;
for (Item current = start; current != null; current = current.next) {
if (currentIndex == index) {
return current.value;
}
currentIndex++;
}
assert false : "Couldn't find item";
return null;
}
public void set(int index, Object newValue) {
assert false : "Not implemented";
}
}