Recursion : 47
Lists Review and Performance : 46
Linked Lists : 45
Algorithms and Lists : 44
Lambda Expressions : 43
Anonymous Classes : 42
Practice with Interfaces : 41
Implementing Interfaces : 40
Using Interfaces : 39
Working with Exceptions : 38
Throwing Exceptions : 37
Catching Exceptions : 36
References and Polymorphism : 35
References : 34
Data Modeling 2 : 33
Equality and Object Copying : 32
Polymorphism : 31
Inheritance : 30
Data Modeling 1 : 29
Static : 28
Encapsulation : 27
Constructors : 26
Objects, Continued : 25
Introduction to Objects : 24
Compilation and Type Inference : 23
Practice with Collections : 22
Maps and Sets : 21
Lists and Type Parameters : 20
Imports and Libraries : 19
Multidimensional Arrays : 18
Practice with Strings : 17
null : 16
Algorithms and Strings : 15
Strings : 14
Functions and Algorithms : 13
Practice with Functions : 12
More About Functions : 11
Errors and Debugging : 10
Functions : 9
Practice with Loops and Algorithms : 8
Algorithms I : 7
Loops : 6
Arrays : 5
Compound Conditionals : 4
Conditional Expressions and Statements : 3
Operations on Variables : 2
Variables and Types : 1
Hello, world! : 0
Lists Review and Performance
public interface SimpleList {
Object get(int index);
void set(int index, Object value);
Object remove(int index);
void add(int index, Object value);
int size();
}
public class SimpleLinkedList implements SimpleList {
private class Item {
private Object value;
private Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
Welcome back!
In this lesson we’re going to wrap up our discussion of lists.
First, we’ll make some forward progress on our linked list implementation.
Then, we’ll compare and contrast the two performance of our two approaches.
But! Let’s warm up with another debugging challenge!
Declare a public class Modifier
providing one static method adder
.
adder
takes a single int
parameter and returns a method that implements the Modify functional interface:
The returned "function" should implement modify
so that it adds the value passed to adder
.
So, for example:
The correct solution to this problem is a single line lambda expression!
At this point we can initialize our linked lists and get and set items.
But what about add and remove?
It’s not a list yet!
Both add and remove require adjusting the linkage to either insert or delete elements.
This is tricky!
Let’s start with remove.
First, let’s look at what needs to happen using a diagram.
OK, now let’s take a stab at this in code!
Interactive Walkthrough
Click on an icon below to start!
What about add?
We’ll leave that for you to work on…
But, to help you get started, let’s diagram it first:
Let’s examine the performance tradeoffs of our ArrayList
versus our LinkedList
.
Now, you might be wondering why anyone would use a linked list, ever!
However, there are applications that only ever modify the ends of the list!
For example, consider a help queue.
Requests are added at one end and removed from the other.
So we are only ever modifying the front or the end of the list.
Modifying the front of a linked list is O(1)
.
But what about the end?
Could we make that O(1)
too?
Sure!
Let’s see how.
Interactive Walkthrough
Click on an icon below to start!
Homework: SimpleLinkedList add
Created By: learncs.online Staff
/ Version: 2020.10.0
Continuing with the SimpleLinkedList
class below, complete the code for add
.
You'll want review the rest of the code to understand how this list implementation works and how to
walk a linked list and manipulate the references properly.
Please Log In to Complete Homework Problems
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]);
}
size = values.length;
}
public int size() {
return size;
More Practice
Need more practice? Head over to the practice page.