Let's review arrays through the actions you can perform on an array and the runtime/algorithm analysis of these operations.
What are some actions you can do with an array?
Declare
Store
Retrieve
That's basically it. From your perspective, these operations are constant, i.e. the time it takes to declare, store, and retrieve values from an array is constant no matter the size.
Let's Get Some Practice w/ Analysis (5 minutes)
What's the runtime for the second line? All arrays are subject to change.
What are some actions you expect to be able to do with a list? Spoiler documentation for lists.
With lists, there are multiple implementations. They have their tradeoffs and the particular implementation you want may depend on what you want to do/prioritize, e.g. I want to be able to store stuff quickly.
The implementations of a List determine the runtime for the operations. We'll focus on the ArrayList implementation.
Practice with ArrayList (10 minutes)
You'll probably want the documentation in front of you. You'll be manipulating a list of Song objects, a class I'll code for you.
Add three of your favorite songs, no judgment.
Print out true/false based on whether your list contains new Song("Enchanted", "Taylor Swift"). You need to @Override the public boolean equals(Object o) function for it to work properly.
Create two playlists and combined them.
Song List Starter Code
import java.util.ArrayList;
publicclassSong{
public String title;
public String artist;
Song(String setTitle, String setArtist) {
this.title = setTitle;
this.artist = setArtist;
}
}
ArrayList<Song> playlist = new ArrayList<>();
"Gross, Greek letters...": Lambda Exressions
Lambda expressions allow you to write functions like variables.
interfaceModify{
intmodify(int value);
}
Modify first = (value) -> value + 1;
Pretty neat! Other programming languages allow you to do this more elegantly, but regardless it's a cool tool.
The syntax is pretty weird though, lambda expressions use arrow notation to define the parameters and the body of the function.
Example of Anonymous Class to Lambda Expression
// A functional interface.interfaceSayHello{
voidsayHello();
}
// An anonymous class.
SayHello jackie = new SayHello() {
@OverridepublicvoidsayHello(){
System.out.println("Hey Jackie!");
}
};
jackie.sayHello();
// A lambda expression, no parameters here.
SayHello akhila = () -> System.out.println("Hey Akhila!");
akhila.sayHello();
Customized Playlist Filters (20 minutes)
Here, we will use lambda expressions to make filters for playlists on the fly.
We'll define a function called public ArrayList<Song> filter(ArrayList<Song> original, Filter f). Don't change the original list, make a new list with the songs we didn't filter out.
Write a function that prints out the songs in the ArrayList. Override toString() in the Song class.
Implement the Filter functional interface to filter out, say Taylor Swift songs :(
Filter Playlist Starter Code
import java.util.ArrayList;
publicclassSong{
public String title;
public String artist;
Song(String setTitle, String setArtist) {
this.title = setTitle;
this.artist = setArtist;
}
}
interfaceFilter{
booleaninclude(Song s);
}
public ArrayList<Song> filter(ArrayList<Song> original, Filter f){
// Your code here.
}
publicvoidprintSongs(ArrayList<Song> pl){
// Your code here.
}
We covered a lot. Particularly, we did some practice on runtime analysis, lists (specfically the ArrayList implementation), and lambda expressions through the playlist filter.
Let us know if you have any questions!
Fill out the feedback form if you have anything to say! Have a good, safe weekend! Get vaccinated if you can.
Solution Section
Runtime Analysis Solutions
Constant time, O(1). If that notation doesn't make sense, doesn't matter. Retrieve a value with an index is constant for arrays.
Linear time, O(n). Loops through the list to find five.
Linear time, O(n). Tried to trick you. Should be linear cause who knows where 1 is for a random array.
Polynomial time, specifically O(n2). You can tell because there are two for loops going through the size of the array.
interfaceFilter{
booleaninclude(Song s);
}
Filter taylor = (s) -> !s.artist.equals("Taylor Swift");
Print the songs in the playlist.
publicvoidprintSongs(ArrayList<Song> pl){
for (int i = 0; i < pl.size(); i++) {
System.out.println((i + 1) + ": " + pl.get(i));
}
}
Song Filtering Solution Part 3
Filter the playlist without changing the original.
public ArrayList<Song> filter(ArrayList<Song> original, Filter f){
ArrayList<Song> filtered = new ArrayList<>();
for (int i = 0; i < original.size(); i++) {
if (f.include(original.get(i))) {
filtered.add(original.get(i));
}
}
return filtered;
}