Building Java Programs

Chapter 16
Linked Lists

Copyright (c) Pearson 2013.

All rights reserved.
 A swap method?
• Does the following swap method work? Why or why not?
public static void main(String[] args) {
int a = 7;
int b = 35;
// swap a with b
swap(a, b);
System.out.println(a + " " + b);
}

public static void swap(int a, int b) {

int temp = a;
a = b;
b = temp;
}
2
 Value semantics
• value semantics: Behavior where values are copied when
assigned to each other or passed as parameters.
– When one primitive is assigned to another, its value is copied.
– Modifying the value of one variable does not affect others.

int x = 5;
int y = x; // x = 5, y = 5
y = 17; // x = 5, y = 17
x = 8; // x = 8, y = 17

3
 Reference semantics
• reference semantics: Behavior where variables actually store
the address of an object in memory.
– When one reference variable is assigned to another, the object is
not copied; both variables refer to the same object.

int[] a1 = {4, 5, 2, 12, 14, 14, 9};

int[] a2 = a1; // refers to same array as a1
a2[0] = 7;
System.out.println(a1[0]); // 7

a1 index 0 1 2 3 4 5 6
value 7
4 5 2 12 14 14 9
a2
4
 References and objects
• In Java, objects and arrays use reference semantics. Why?
– efficiency. Copying large objects slows down a program.
– sharing. It's useful to share an object's data among methods.

DrawingPanel panel1 = new DrawingPanel(80, 50);

DrawingPanel panel2 = panel1; // same window
panel2.setBackground(Color.CYAN);

panel1

panel2

5
 References as fields
• Objects can store references to other objects as fields.
Example: Homework 3 (HTML Validator)
– HtmlValidator stores a reference to a Queue
– the Queue stores many references to HtmlTag objects
– each HtmlTag object stores a reference to its element String

HtmlValidator private Queue<HtmlTag> tags;

...

Queue front ... ... ... back

HtmlTag
HtmlTag
private String element;
... private String element;
...

String h t m l
String b o d y 6
 Null references
• null : A value that does not refer to any object.

– The elements of an array of objects are initialized to null.

String[] words = new String[5];

index 0 1 2 3 4
words value null null null null null

– not the same as the empty string "" or the string "null"
– Why does Java have null ? What is it used for?

7
 Null references
– Unset reference fields of an object are initialized to null.
public class Student {
String name;
int id;
}

Student timmy = new Student();

name null

timmy id 0

8
 Things you can do w/ null
• store null in a variable or an array element
String s = null;
words[2] = null;

• print a null reference

System.out.println(timmy.name); // null

• ask whether a variable or array element is null

if (timmy.name == null) { ... // true

• pass null as a parameter to a method

– some methods don't like null parameters and throw exceptions

• return null from a method (often to indicate failure)

return null;
9
 Dereferencing
• dereference: To access data or methods of an object.
– Done with the dot notation, such as s.length()
– When you use a . after an object variable, Java goes to the
memory for that object and looks up the field/method requested.

Student timmy = new Student();

timmy.name = "Timmah";
String s = timmy.name.toUpperCase();

Student String

name null 'T' 'i' 'm' 'm' 'a' 'h'

timmy
public int indexOf(String s) {...}
id 0 public int length() {...}
public String toUpperCase() {...}
10
 Null pointer exception
• It is illegal to dereference null (it causes an exception).
– null does not refer to any object, so it has no methods or data.

Student timmy = new Student();

String s = timmy.name.toUpperCase(); // ERROR

name null
timmy
id 0

Output:
Exception in thread "main"
java.lang.NullPointerException
at Example.main(Example.java:8)
11
 References to same type
• What would happen if we had a class that declared one of its
own type as a field?

public class Strange {

private String name;
private Strange other;
}

– Will this compile?

• If so, what is the behavior of the other field? What can it do?
• If not, why not? What is the error and the reasoning behind it?

12
 Linked data structures
• All of the collections we will use and implement in this course
use one of the following two underlying data structures:
– an array of all elements
• ArrayList, Stack, HashSet, HashMap

42 -3 17 9

– a set of linked objects, each storing one element,

and one or more reference(s) to other element(s)
• LinkedList, TreeSet, TreeMap

front 42 -3 17 9 null

13
 A list node class
public class ListNode {
int data;
ListNode next;
}

• Each list node object stores:

– one piece of integer data
– a reference to another list node

• ListNodes can be "linked" into chains to store a list of values:

data next data next data next data next

42 -3 17 9 null

14
 List node client example
public class ConstructList1 {
public static void main(String[] args) {
ListNode list = new ListNode();
list.data = 42;
list.next = new ListNode();
list.next.data = -3;
list.next.next = new ListNode();
list.next.next.data = 17;
list.next.next.next = null;
System.out.println(list.data + " " + list.next.data
+ " " + list.next.next.data);
// 42 -3 17
}
}

data next data next data next

list 42 -3 17 null

15
 List node w/ constructor
public class ListNode {
int data;
ListNode next;

public ListNode(int data) {

this.data = data;
this.next = null;
}

public ListNode(int data, ListNode next) {

this.data = data;
this.next = next;
}
}

– Exercise: Modify the previous client to use these constructors.

16
 Linked node problem 1
• What set of statements turns this picture:
data next data next
list
10 20

• Into this?
data next data next data next
list
10 20 30

17
 Linked node problem 2
• What set of statements turns this picture:
data next data next
list
10 20

• Into this?
data next data next data next
list
30 10 20

18
 Linked node problem 3
• What set of statements turns this picture:
data next data next
list1
10 20

data next data next

list2
30 40

• Into this?
data next data next data next
list1
10 30 20

data next
list2
40
19
 Linked node problem 4
• What set of statements turns this picture:
data next data next
list
10 ... 990

• Into this?
data next data next data next
list
10 ... 990 1000

20
 References vs. objects
variable = value;

a variable (left side of = ) is an arrow (the base of an arrow)

a value (right side of = ) is an object (a box; what an arrow points at)

2
• For the list at right:
data next data next
a
– a.next = value; 10 20
1
means to adjust where 1 points

– variable = a.next;
means to make variable point at 2

21
 Reassigning references
• when you say:
– a.next = b.next;

• you are saying:

– "Make the variable a.next refer to the same value as b.next."
– Or, "Make a.next point to the same place that b.next points."

data next data next

a
10 20

data next data next

b
30 40

22
 Linked node question
• Suppose we have a long chain of list nodes:

data next data next data next

list
10 20 ... 990

– We don't know exactly how long the chain is.

• How would we print the data values in all the nodes?

23
 Algorithm pseudocode
• Start at the front of the list.
• While (there are more nodes to print):
– Print the current node's data.
– Go to the next node.

• How do we walk through the nodes of the list?

list = list.next; // is this a good idea?

data next data next data next

list
10 20 ... 990

24
 Traversing a list?
• One (bad) way to print every value in the list:
while (list != null) {
System.out.println(list.data);
list = list.next; // move to next node
}

– What's wrong with this approach?

• (It loses the linked list as it prints it!)

data next data next data next

list
10 20 ... 990

25
 A current reference
• Don't change list. Make another variable, and change that.
– A ListNode variable is NOT a ListNode object

ListNode current = list;

data next data next data next

list
10 20 ... 990

current

• What happens to the picture above when we write:

current = current.next;
26
 Traversing a list correctly
• The correct way to print every value in the list:
ListNode current = list;
while (current != null) {
System.out.println(current.data);
current = current.next; // move to next node
}

– Changing current does not damage the list.

data next data next data next

list
10 20 ... 990

27
 Linked list vs. array
• Algorithm to print list values: • Similar to array code:

ListNode front = ...; int[] a = ...;

ListNode current = front; int i = 0;

while (current != null) { while (i < a.length) {
System.out.println(current.data); System.out.println(a[i]);
current = current.next; i++;
} }

28
 A LinkedIntList class
• Let's write a collection class named LinkedIntList.
– Has the same methods as ArrayIntList:
• add, add, get, indexOf, remove, size, toString

– The list is internally implemented as a chain of linked nodes

• The LinkedIntList keeps a reference to its front as a field
• null is the end of the list; a null front signifies an empty list

LinkedIntList
ListNode ListNode ListNode
front
add(value)
data next data next data next
add(index, value) 42 -3 17
indexOf(value)
remove(index) element 0 element 1 element 2
size()
toString()
29
 LinkedIntList class v1
public class LinkedIntList {
private ListNode front;
LinkedIntList
public LinkedIntList() {
front = null; front =
}

methods go here

30
 Implementing add
// Adds the given value to the end of the list.
public void add(int value) {
...
}

– How do we add a new node to the end of a list?

– Does it matter what the list's contents are before the add?

data next data next data next

front = 42 -3 17
element 0 element 1 element 2

31
 Adding to an empty list
• Before adding 20: After:

data next
front = front = 20
element 0

– We must create a new node and attach it to the list.

32
 The add method, 1st try
// Adds the given value to the end of the list.
public void add(int value) {
if (front == null) {
// adding to an empty list
front = new ListNode(value);
} else {
// adding to the end of an existing list

...

}
}

33
 Adding to non-empty list
• Before adding value 20 to end of list:

data next data next

front = 42 -3
element 0 element 1

• After:
data next data next data next
front = 42 -3 20
element 0 element 1 element 2

34
 Don't fall off the edge!
• To add/remove from a list, you must modify the next
reference of the node before the place you want to change.

data next data next

front = 42 -3
element 0 element 1

– Where should current be pointing, to add 20 at the end?

– What loop test will stop us at this place in the list?

35
 The add method
// Adds the given value to the end of the list.
public void add(int value) {
if (front == null) {
// adding to an empty list
front = new ListNode(value);
} else {
// adding to the end of an existing list
ListNode current = front;
while (current.next != null) {
current = current.next;
}
current.next = new ListNode(value);
}
}

36
 Implementing get
// Returns value in list at given index.
public int get(int index) {
...
}

– Exercise: Implement the get method.

data next data next data next

front = 42 -3 17
element 0 element 1 element 2

37
 The get method
// Returns value in list at given index.
// Precondition: 0 <= index < size()
public int get(int index) {
ListNode current = front;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}

38
 Implementing add (2)
// Inserts the given value at the given index.
public void add(int index, int value) {
...
}

– Exercise: Implement the two-parameter add method.

data next data next data next

front = 42 -3 17
element 0 element 1 element 2

39
 The add method (2)
// Inserts the given value at the given index.
// Precondition: 0 <= index <= size()
public void add(int index, int value) {
if (index == 0) {
// adding to an empty list
front = new ListNode(value, front);
} else {
// inserting into an existing list
ListNode current = front;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = new ListNode(value,
current.next);
}
}

40
 Conceptual questions
• What is the difference between a LinkedIntList and a
ListNode?

• What is the difference between an empty list and a null list?

– How do you create each one?

• Why are the fields of ListNode public? Is this bad style?

• What effect does this code have on a LinkedIntList?

ListNode current = front;
current = null;

41
 Conceptual answers
• A list consists of 0 to many node objects.
– Each node holds a single data element value.

• null list: LinkedIntList list = null;

empty list: LinkedIntList list = new LinkedIntList();

• It's okay that the node fields are public, because client code
never directly interacts with ListNode objects.

• The code doesn't change the list.

You can change a list only in one of the following two ways:
– Modify its front field value.
– Modify the next reference of a node in the list.
42
 Implementing remove
// Removes and returns the list's first value.
public int remove() {
...
}

– How do we remove the front node from a list?

– Does it matter what the list's contents are before the remove?

43
 Removing front element
• Before removing front element:

data next data next

front = 42 20
element 0 element 1

• After first removal: After second removal:

data next
front = 20 front =
element 0

44
 remove solution
// Removes and returns the first value.
// Throws a NoSuchElementException on empty list.
public int remove() {
if (front == null) {
throw new NoSuchElementException();
} else {
int result = front.data;
front = front.next;
return result;
}
}

45
 Implementing remove (2)
// Removes value at given index from list.
// Precondition: 0 <= index < size
public void remove(int index) {
...
}

– How do we remove any node in general from a list?

– Does it matter what the list's contents are before the remove?

46
 Removing from a list
• Before removing element at index 1:

data next data next data next

front = 42 -3 20
element 0 element 1 element 2

• After:
data next data next
front = 42 20
element 0 element 1

47
 Removing from the front
• Before removing element at index 0:

data next data next data next

front = 42 -3 20
element 0 element 1 element 2

• After:
data next data next
front = -3 20
element 0 element 1

48
 Removing the only element
• Before: After:

data next
front = 20 front =
element 0

– We must change the front field to store null instead of a node.

– Do we need a special case to handle this?

49
 remove (2) solution
// Removes value at given index from list.
// Precondition: 0 <= index < size()
public void remove(int index) {
if (index == 0) {
// special case: removing first element
front = front.next;
} else {
// removing from elsewhere in the list
ListNode current = front;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
}
}
50
 Exercise
• Write a method addSorted that accepts an integer value as a
parameter and adds that value to a sorted list in sorted order.
– Before addSorted(17) :
data next data next data next
front =
-4 8 22
element 0 element 1 element 2

– After addSorted(17) :
data next data next data next data next
front =
-4 8 17 22
element 0 element 1 element 2 element 3
51
 The common case
• Adding to the middle of a list:
addSorted(17)

data next data next data next

front =
-4 8 22
element 0 element 1 element 2

– Which references must be changed?

– What sort of loop do we need?
– When should the loop stop?

52
 First attempt
• An incorrect loop:
ListNode current = front;
while (current.data < value) {
current = current.next;
} current

data next data next data next

front =
-4 8 22
element 0 element 1 element 2

• What is wrong with this code?

– The loop stops too late to affect the list in the right way.
53
 Key idea: peeking ahead
• Corrected version of the loop:
ListNode current = front;
while (current.next.data < value) {
current = current.next;
} current

data next data next data next

front =
-4 8 22
element 0 element 1 element 2

– This time the loop stops in the right place.

54
 Another case to handle
• Adding to the end of a list:
addSorted(42)

data next data next data next

front =
-4 8 22
element 0 element 1 element 2

Exception in thread "main": java.lang.NullPointerException

– Why does our code crash?

– What can we change to fix this case?

55
 Multiple loop tests
• A correction to our loop:
ListNode current = front;
while (current.next != null &&
current.next.data < value) {
current = current.next; current
}

data next data next data next

front =
-4 8 22
element 0 element 1 element 2

– We must check for a next of null before we check its .data.

56
 Third case to handle
• Adding to the front of a list:
addSorted(-10)

data next data next data next

front =
-4 8 22
element 0 element 1 element 2

– What will our code do in this case?

– What can we change to fix it?

57
 Handling the front
• Another correction to our code:
if (value <= front.data) {
// insert at front of list
front = new ListNode(value, front);
} else {
// insert in middle of list
ListNode current = front;
while (current.next != null &&
current.next.data < value) {
current = current.next;
}
}

– Does our code now handle every possible case?

58
 Fourth case to handle
• Adding to (the front of) an empty list:
addSorted(42)

front =

– What will our code do in this case?

– What can we change to fix it?

59
 Final version of code
// Adds given value to list in sorted order.
// Precondition: Existing elements are sorted
public void addSorted(int value) {
if (front == null || value <= front.data) {
// insert at front of list
front = new ListNode(value, front);
} else {
// insert in middle of list
ListNode current = front;
while (current.next != null &&
current.next.data < value) {
current = current.next;
}
}
}
60
 Other list features
• Add the following methods to the LinkedIntList:
– size
– isEmpty
– clear
– toString
– indexOf
– contains

• Add a size field to the list to return its size more efficiently.

• Add preconditions and exception tests to appropriate methods.

61
 Implementing an interface
public class name implements interface {
...
}

• A class can declare that it "implements" an interface.

– The class promises to contain each method in that interface.
(Otherwise it will fail to compile.)

– Example:
public class Bicycle implements Vehicle {
...
}

62
 Interface requirements
public class Banana implements Shape {
// haha, no methods! pwned
}

• If we write a class that claims to be a Shape but doesn't

implement area and perimeter methods, it will not compile.

Banana.java:1: Banana is not abstract and does

not override abstract method area() in Shape
public class Banana implements Shape {
^

63
 Interfaces + polymorphism
• Interfaces benefit the client code author the most.
– they allow polymorphism
(the same code can work with different types of objects)

public static void printInfo(Shape s) {

System.out.println("The shape: " + s);
System.out.println("area : " + s.area());
System.out.println("perim: " + s.perimeter());
System.out.println();
}
...
Circle circ = new Circle(12.0);
Triangle tri = new Triangle(5, 12, 13);
printInfo(circ);
printInfo(tri);
64
 Linked vs. array lists
• We have implemented two collection classes:
– ArrayIntList
index 0 1 2 3
value 42 -3 17 9

– LinkedIntList
data next data next data next data next
front 42 -3 17 9

– They have similar behavior, implemented in different ways.

We should be able to treat them the same way in client code.
65
 An IntList interface
// Represents a list of integers.
public interface IntList {
public void add(int value);
public void add(int index, int value);
public int get(int index);
public int indexOf(int value);
public boolean isEmpty();
public void remove(int index);
public void set(int index, int value);
public int size();
}

public class ArrayIntList implements IntList { ...

public class LinkedIntList implements IntList { ...
66
 Redundant client code
public class ListClient {
public static void main(String[] args) {
ArrayIntList list1 = new ArrayIntList();
list1.add(18);
list1.add(27);
list1.add(93);
System.out.println(list1);
list1.remove(1);
System.out.println(list1);
LinkedIntList list2 = new LinkedIntList();
list2.add(18);
list2.add(27);
list2.add(93);
System.out.println(list2);
list2.remove(1);
System.out.println(list2);
}
}
67
 Client code w/ interface
public class ListClient {
public static void main(String[] args) {
IntList list1 = new ArrayIntList();
process(list1);
IntList list2 = new LinkedIntList();
process(list2);
}
public static void process(IntList list) {
list.add(18);
list.add(27);
list.add(93);
System.out.println(list);
list.remove(1);
System.out.println(list);
}
}
68
 ADTs as interfaces (11.1)
• abstract data type (ADT): A specification of a collection of
data and the operations that can be performed on it.
– Describes what a collection does, not how it does it.

• Java's collection framework uses interfaces to describe ADTs:

– Collection, Deque, List, Map, Queue, Set

• An ADT can be implemented in multiple ways by classes:

– ArrayList and LinkedList implement List
– HashSet and TreeSet implement Set
– LinkedList , ArrayDeque, etc. implement Queue
• They messed up on Stack; there's no Stack interface, just a class.
69
 Using ADT interfaces
When using Java's built-in collection classes:

• It is considered good practice to always declare collection

variables using the corresponding ADT interface type:
List<String> list = new ArrayList<String>();

• Methods that accept a collection as a parameter should also

declare the parameter using the ADT interface type:
public void stutter(List<String> list) {
...
}

70
 Why use ADTs?
• Why would we want more than one kind of list, queue, etc.?

• Answer: Each implementation is more efficient at certain tasks.

– ArrayList is faster for adding/removing at the end;
LinkedList is faster for adding/removing at the front/middle.

– HashSet can search a huge data set for a value in short time;
TreeSet is slower but keeps the set of data in a sorted order.

– You choose the optimal implementation for your task, and if the
rest of your code is written to use the ADT interfaces, it will work.

71
 Our list classes
• We implemented the following two list classes:
– ArrayIntList
index 0 1 2
value 42 -3 17

– LinkedIntList data next data next data next

front 42 -3 17

– Problems:
• We should be able to treat them the same way in client code.
• Some of their methods are implemented the same way (redundancy).
• Linked list carries around a clunky extra node class.
• They can store only int elements, not any type of value.
• It is inefficient to get or remove each element of a linked list.
72
 Recall: ADT interfaces (11.1)

• abstract data type (ADT): A specification of a collection of data

and the operations that can be performed on it.
– Describes what a collection does, not how it does it.

• Java's collection framework describes ADTs with interfaces:

– Collection, Deque, List, Map, Queue, Set, SortedMap

• An ADT can be implemented in multiple ways by classes:

– ArrayList and LinkedList implement List
– HashSet and TreeSet implement Set
– LinkedList , ArrayDeque, etc. implement Queue

• Exercise: Create an ADT interface for the two list classes.

73
 An IntList interface (16.4)

// Represents a list of integers.

public interface IntList {
public void add(int value);
public void add(int index, int value);
public int get(int index);
public int indexOf(int value);
public boolean isEmpty();
public void remove(int index);
public void set(int index, int value);
public int size();
}

public class ArrayIntList implements IntList { ...

public class LinkedIntList implements IntList { ...
74
 Our list classes
• We have implemented the following two list collection classes:
– ArrayIntList
index 0 1 2
value 42 -3 17

– LinkedIntList data next data next data next

front 42 -3 17

– Problems:
• We should be able to treat them the same way in client code.
• Some methods are implemented the same way (redundancy).
• Linked list carries around a clunky extra node class.
• They can store only int elements, not any type of value.
• It is inefficient to get or remove each element of a linked list.
75
 Common code
• Notice that some of the methods are implemented the same
way in both the array and linked list classes.
– add(value)
– contains
– isEmpty

• Should we change our interface to a class? Why / why not?

– How can we capture this common behavior?

76
 Abstract classes (9.6)

• abstract class: A hybrid between an interface and a class.

– defines a superclass type that can contain method declarations
(like an interface) and/or method bodies (like a class)
– like interfaces, abstract classes that cannot be instantiated
(cannot use new to create any objects of their type)

• What goes in an abstract class?

– implementation of common state and behavior that will be
inherited by subclasses (parent class role)
– declare generic behaviors that subclasses must implement
(interface role)

77
 Abstract class syntax
// declaring an abstract class
public abstract class name {
...

// declaring an abstract method

// (any subclass must implement it)
public abstract type name(parameters);

• A class can be abstract even if it has no abstract methods

• You can create variables (but not objects) of the abstract type

• Exercise: Introduce an abstract class into the list hierarchy.

78
 Abstract and interfaces
• Normal classes that claim to implement an interface must
implement all methods of that interface:
public class Empty implements IntList {} // error

• Abstract classes can claim to implement an interface without

writing its methods; subclasses must implement the methods.
public abstract class Empty implements IntList {} // ok

public class Child extends Empty {} // error

79
 An abstract list class
// Superclass with common code for a list of integers.
public abstract class AbstractIntList implements IntList {
public void add(int value) {
add(size(), value);
}

public boolean contains(int value) {

return indexOf(value) >= 0;
}

public boolean isEmpty() {

return size() == 0;
}
}

public class ArrayIntList extends AbstractIntList { ...

public class LinkedIntList extends AbstractIntList { ...

80
 Abstract class vs. interface
• Why do both interfaces and abstract classes exist in Java?
– An abstract class can do everything an interface can do and more.
– So why would someone ever use an interface?

• Answer: Java has single inheritance.

– can extend only one superclass
– can implement many interfaces
– Having interfaces allows a class to be part of a hierarchy
(polymorphism) without using up its inheritance relationship.

81
 Our list classes
• We have implemented the following two list collection classes:
– ArrayIntList
index 0 1 2
value 42 -3 17

– LinkedIntList data next data next data next

front 42 -3 17

– Problems:
• We should be able to treat them the same way in client code.
• Some of their methods are implemented the same way (redundancy).
• Linked list carries around a clunky extra node class.
• They can store only int elements, not any type of value.
• It is inefficient to get or remove each element of a linked list.
82
 Inner classes
• inner class: A class defined inside of another class.
– can be created as static or non-static
– we will focus on standard non-static ("nested") inner classes

• usefulness:
– inner classes are hidden from other classes (encapsulated)
– inner objects can access/modify the fields of the outer object

83
 Inner class syntax
// outer (enclosing) class
public class name {
...

// inner (nested) class

private class name {
...
}
}

– Only this file can see the inner class or make objects of it.
– Each inner object is associated with the outer object that created it, so
it can access/modify that outer object's methods/fields.
• If necessary, can refer to outer object as OuterClassName.this

– Exercise: Convert the linked node into an inner class.

84
 Our list classes
• We have implemented the following two list collection classes:
– ArrayIntList
index 0 1 2
value 42 -3 17

– LinkedIntList data next data next data next

front 42 -3 17

– Problems:
• We should be able to treat them the same way in client code.
• Some of their methods are implemented the same way (redundancy).
• Linked list carries around a clunky extra node class.
• They can store only int elements, not any type of value.
• It is inefficient to get or remove each element of a linked list.
85
 Type Parameters (Generics)
ArrayList<Type> name = new ArrayList<Type>();

• Recall: When constructing a java.util.ArrayList, you

specify the type of elements it will contain between < and >.
– We say that the ArrayList class accepts a type parameter,
or that it is a generic class.

ArrayList<String> names = new ArrayList<String>();

names.add("Marty Stepp");
names.add("Stuart Reges");

86
 Implementing generics
// a parameterized (generic) class
public class name<Type> {
...
}

– By putting the Type in < >, you are demanding that any client that
constructs your object must supply a type parameter.
• You can require multiple type parameters separated by commas.

– The rest of your class's code can refer to that type by name.

• Exercise: Convert our list classes to use generics.

87
 Generics and arrays (15.4)

public class Foo<T> {

private T myField; // ok

public void method1(T param) {

myField = new T(); // error
T[] a = new T[10]; // error

myField = param; // ok
T[] a2 = (T[]) (new Object[10]); // ok
}
}

– You cannot create objects or arrays of a parameterized type.

– You can create variables of that type, accept them as parameters,
return them, or create arrays by casting from Object[] .
88
 Generics and inner classes
public class Foo<T> {
private class Inner<T> {} // incorrect

private class Inner {} // correct

}

– If an outer class declares a type parameter, inner classes can also

use that type parameter.
– Inner class should NOT redeclare the type parameter. (If you do,
it will create a second type parameter with the same name.)

89
 Our list classes
• We have implemented the following two list collection classes:
– ArrayIntList
index 0 1 2
value 42 -3 17

– LinkedIntList data next data next data next

front 42 -3 17

– Problems:
• We should be able to treat them the same way in client code.
• Some of their methods are implemented the same way (redundancy).
• Linked list carries around a clunky extra node class.
• They can store only int elements, not any type of value.
• It is inefficient to get or remove each element of a linked list.
90
 Linked list iterator
• The following code is particularly slow on linked lists:
List<Integer> list = new LinkedList<Integer>();
...
for (int i = 0; i < list.size(); i++) {
int value = list.get(i);
if (value % 2 == 1) {
list.remove(i);
}
}

– Why?
– What can we do to improve the runtime?

91
 Recall: Iterators (11.1)

• iterator: An object that allows a client to traverse the

elements of a collection, regardless of its implementation.
– Remembers a position within a collection, and allows you to:
• get the element at that position
• advance to the next position
• (possibly) remove or change the element at that position

– Benefit: A common way to examine any collection's elements.

index 0 1 2 data next data next data next
value 42 -3 17 front 42 -3 17

current element: -3 current element: -3

iterator iterator
current index: 1 current index: 1
92
 Iterator methods
hasNext() returns true if there are more elements to examine
next() returns the next element from the collection (throws a
NoSuchElementException if there are none left to examine)
remove() removes from the collection the last value returned by next()
(throws IllegalStateException if you have not called
next() yet)

– every provided collection has an iterator method

Set<String> set = new HashSet<String>();
...
Iterator<String> itr = set.iterator();
...

• Exercise: Write iterators for our array list and linked list.
– You don't need to support the remove operation.
93
 Array list iterator
public class ArrayList<E> extends AbstractIntList<E> {
...
// not perfect; doesn't forbid multiple removes in a row
private class ArrayIterator implements Iterator<E> {
private int index; // current position in list
public ArrayIterator() {
index = 0;
}
public boolean hasNext() {
return index < size();
}
public E next() {
index++;
return get(index - 1);
}
public void remove() {
ArrayList.this.remove(index - 1);
index--;
}
}
}
94
 Linked list iterator
public class LinkedList<E> extends AbstractIntList<E> {
...
// not perfect; doesn't support remove
private class LinkedIterator implements Iterator<E> {
private ListNode current; // current position in list
public LinkedIterator() {
current = front;
}
public boolean hasNext() {
return current != null;
}
public E next() {
E result = current.data;
current = current.next;
return result;
}
public void remove() { // not implemented for now
throw new UnsupportedOperationException();
}
}
}
95
 for-each loop and Iterable
• Java's collections can be iterated using a "for-each" loop:
List<String> list = new LinkedList<String>();
...
for (String s : list) {
System.out.println(s);
}
– Our collections do not work in this way.

• To fix this, your list must implement the Iterable interface.

public interface Iterable<E> {
public Iterator<E> iterator();
}

96
Final List interface (15.3, 16.5)

// Represents a list of values.

public interface List<E> extends Iterable<E> {
public void add(E value);
public void add(int index, E value);
public E get(int index);
public int indexOf(E value);
public boolean isEmpty();
public Iterator<E> iterator();
public void remove(int index);
public void set(int index, E value);
public int size();
}

97