Using ArrayList with Post — Collections and Generics

Student: Ok Professor, I think I’m ready to use an ArrayList in my own programs.

Prof: Sure, let’s go back to an example we have gone over before. We made a Post class.

class Post {
  String user;
  String message;
  int likes;

  Post(String user, String message) {
    this.user = user;
    this.message = message;
    this.likes = 0;
  }

  void like() {
    this.likes = this.likes + 1;
  }
}

Post original = new Post("joe", "CSE-PACE next Tuesday!");
int likes;
void main() {
  original.like();
  likes = original.likes;
}

Prof: Imagine we wanted to support replies on our posts. How would you go about implementing replies to a post using an ArrayList?

Student: I should have every Post contain an ArrayList of replies, and the type should be other posts, so I’ll use an ArrayList<Post>.

Prof: Good idea. You should also include a reference to the Post it’s replying to, since each reply is also a Post.

Student: Ok, I understand.

import java.util.ArrayList;

class Post {
  String user;
  String message;
  int likes;
  ArrayList<Post> replies;
  Post replyTo;

  Post(String user, String message) {
    this.user = user;
    this.message = message;
    this.likes = 0;
    this.replies = new ArrayList<Post>();
    this.replyTo = null;
  }

  void like() {
    this.likes = this.likes + 1;
  }
}

Post original = new Post("joe", "CSE-PACE next Tuesday!");
int count;
void main() {
  count = original.replies.size();
}

Student: Ok now I am going to add a reply() method. It needs to make a new Post() and set replyTo to be the original Post. And then add this new reply to the ArrayList.

Prof: Implement that method. After you run it, let’s take a moment to think through what it actually builds in memory.

import java.util.ArrayList;

class Post {
  String user;
  String message;
  int likes;
  ArrayList<Post> replies;
  Post replyTo;

  Post(String user, String message) {
    this.user = user;
    this.message = message;
    this.likes = 0;
    this.replies = new ArrayList<Post>();
    this.replyTo = null;
  }

  void like() {
    this.likes = this.likes + 1;
  }

  Post reply(String user, String message) {
    Post r = new Post(user, message);
    r.replyTo = this;
    this.replies.add(r);
    return r;
  }
}

Post original = new Post("joe", "CSE-PACE next Tuesday!");
int count;
String backUser;
void main() {
  Post r = original.reply("ada", "I'll be there");
  original.reply("grace", "Is there pizza?");
  count = original.replies.size();
  backUser = r.replyTo.user;
}

Prof: Here’s the picture just after both reply calls, but before we read count and backUser:

Names (the stack)

main()

r = @1003

top level

original = @1001

count = 0

backUser = null

Heap

@1001: Post[user=joe, message=CSE-PACE next Tuesday!, likes=0, replies=@1002, replyTo=null]

@1002: [@1003, @1005]

@1003: Post[user=ada, message=I'll be there, likes=0, replies=@1004, replyTo=@1001]

@1004: []

@1005: Post[user=grace, message=Is there pizza?, likes=0, replies=@1006, replyTo=@1001]

@1006: []

Prof: Each reply did two things at once: it made a new Post and pointed that post’s replyTo back at the one it was replying to. That leaves a link from the original to the reply through the list, and from the reply back to the original through replyTo.

Student: Now for the likes. Since we are using references, whenever we like a Post it shouldn’t matter whether I reach it through the variable r or through original.replies.get(0). They both point at the same object, so liking one should show up on the other.

Prof: Exactly, the posts are mutable. They can be changed without making a copy.

import java.util.ArrayList;

class Post {
  String user;
  String message;
  int likes;
  ArrayList<Post> replies;
  Post replyTo;

  Post(String user, String message) {
    this.user = user;
    this.message = message;
    this.likes = 0;
    this.replies = new ArrayList<Post>();
    this.replyTo = null;
  }

  void like() {
    this.likes = this.likes + 1;
  }

  Post reply(String user, String message) {
    Post r = new Post(user, message);
    r.replyTo = this;
    this.replies.add(r);
    return r;
  }
}

Post original = new Post("joe", "CSE-PACE next Tuesday!");
int viaVariable;
int viaList;
void main() {
  Post r = original.reply("ada", "I'll be there");
  original.replies.get(0).like();
  viaVariable = r.likes;
  viaList = original.replies.get(0).likes;
}

Student: So we’ve been using ArrayList, HashSet, and HashMap. They have a lot of similarities — are they connected in any way?

Prof: They sure are. Each one of these classes implements an interface. ArrayList is one kind of List, and a List is a kind of Collection. HashSet is a Set, which is also a Collection. HashMap is a bit different as a Map holds key/value pairs rather than single elements. Here’s the class hierarchy for that.

interface

Collection

add(E e)

contains(Object o)

remove(Object o)

size()

interface

List

get(int index)

add(int index, E e)

set(int index, E e)

remove(int index)

interface

Set

interface

Map

put(K key, V value)

get(Object key)

containsKey(Object key)

getOrDefault(Object key, V d)

ArrayList

HashSet

HashMap

Prof: Because ArrayList is a List, you will sometimes see the field written as List<Post> replies instead of ArrayList<Post>. We only covered one type of list, but you will learn about others in future classes. The full set of methods each one offers is in the Java documentation.

Practice

After Post r = p.reply("ada", "hi"); runs, which of these is true?

p.replies contains r and r.replyTo is p
p.replies contains a copy of r, and r.replyTo is null
r.replies contains p and p.replyTo is r
p.replies is unchanged until like() is called

Fill in reply so the new post is linked in both directions: it remembers its parent, and the parent remembers it. main should end with 1 printed for the number of replies.

import java.util.ArrayList;

class Post {
String user;
ArrayList<Post> replies = new ArrayList<Post>();
Post replyTo;
Post(String user) { this.user = user; }

Post reply(String user) {
Post r = new Post(user);

return r;
}
}

void main() {
Post p = new Post("joe");
Post r = p.reply("ada");
System.out.println(p.replies.size());
System.out.println(r..user);
}