Lecture 25 - CS159 Collections + Maps
Prof. Alvin Chao
Due this week:
POGIL
Model 1 - ArrayList
An “ArrayList” is a list that uses an array to store elements. The following code is a simplified
version of java.util.ArrayList.
1 public class MyArrayList {
2
3 private char[] data = new char[10];
4 private int size;
5
6 public void add(char item) {
7 if (size == data.length) {
8 grow();
9 } else {
10 shift();
11 }
12 data[0] = item;
13 size++;
14 }
15
16 private void grow() {
17 // make the new data array 50% larger
18 char[] old = data;
19 int newLen = (int) (old.length * 1.5);
20 data = new char[newLen];
21 // copy and shift from old to new array
22 for (int i = size; i > 0; i--) {
23 data[i] = old[i - 1];
24 }
25 }
26
27 private void shift() {
28 for (int i = size; i > 0; i--) {
29 data[i] = data[i - 1];
30 }
31 }
32
33 public static void main(String[] args) {
34 MyArrayList list = new MyArrayList();
35 list.add('A');
36 list.add('B');
37 list.add('C');
38 }
39
40 }
What are: list.size and list.data.length
list.add('A');
�
Model 2 Linked List
A “LinkedList” is a list that uses references to link elements. The following code is a simplified
version of java.util.LinkedList.
1 public class MyLinkedList {
2
3 private Node head; // see inner class below
4 private int size;
5
6 public void add(char item) {
7 Node oldHead = head;
8 head = new Node(item, oldHead);
9 size++;
10 }
11
12 private static class Node {
13 public char item;
14 public Node next;
15
16 public Node(char item, Node next) {
17 this.item = item;
18 this.next = next;
19 }
20 }
21
22 public static void main(String[] args) {
23 MyLinkedList list = new MyLinkedList();
24 list.add('A');
25 list.add('B');
26 list.add('C');
27 }
28
29 }
Model 3 Doubly Linked List
Java’s implementation of LinkedList stores two references in each node: one for the previous,
and one for the next. In addition, both the head and the tail of the list are stored.
1 public class MyDoublyList {
2
3 private Node head; // the first node
4 private Node tail; // the last node
5 private int size;
6
7 public void add(char item) {
8 Node oldHead = head;
9 head = new Node(null, item, oldHead);
10 if (size == 0) {
11 tail = head;
12 } else {
13 oldHead.prev = head;
14 }
15 size++;
16 }
17
18 private static class Node {
19 public Node prev;
20 public char item;
21 public Node next;
22
23 public Node(Node prev, char item, Node next) {
24 this.prev = prev;
25 this.item = item;
26 this.next = next;
27 }
28 }
29
30 public static void main(String[] args) {
31 MyDoublyList list = new MyDoublyList();
32 list.add('A');
33 list.add('B');
34 list.add('C');
35 }
36
37 }
At the end of main(), what is the value of . . . ?
a) list.head.item
b) list.tail.item
c) list.head.prev
d) list.tail.next
e) list.head.next.item
f) list.tail.prev.prev.ite
Explain 1(19)
Explain why java.util.ArrayList is a poor choice of List in the program below:
1 public static void main(String[] args) {
2 List<String> list = new ArrayList<>();
3 System.out.println("Start");
4 addAndRemove(list);
5 System.out.println("Done!");
6 }
7
8 public static void addAndRemove(List<String> list) {
9 System.out.println("Adding...");
10 for (int i = 0; i < 1000000; i++) {
11 list.add(0, "A"); // insert at index 0
12 }
13 System.out.println("Removing...");
14 for (int i = 0; i < 1000000; i++) {
15 list.remove(0); // remove at index 0
16 }
17 }
Explain 2(20)
Explain why java.util.LinkedList is a poor choice of List in the program below.
1 public static void main(String[] args) {
2 List<String> list = new LinkedList<>();
3 System.out.println("Start");
4 addAndGet(list);
5 System.out.println("Done!");
6 }
7
8 public static void addAndGet(List<String> list) {
9 System.out.println("Adding...");
10 for (int i = 0; i < 1000000; i++) {
11list.add("A"); // append at the end
12 }
13 System.out.println("Getting...");
14 for (int i = 0; i < 1000000; i++) {
15 list.get(list.size() / 2); // get the middle
16 }
17 }
PI Question
https://runestone.academy/ Select Peer Instruction Student and select Apr 21
Or https://canvas.jmu.edu/courses/2071161/assignments/19940303
Exam 3 Question review
public void save(String filename) throws IOException{
First
// PrintWriter w = new PrintWriter(filename);
// w.println(toString());
// w.close();
Second
// FileWriter file = new FileWriter(filename);
// file.write(toString());
// file.close();
Third
BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
writer.write(toString());
writer.close();