Transcript Collections in Java

Lists in Java
Part of the Collections Framework
29-Mar-16
Kinds of Collections

Collection—a group of objects, called elements



Map—a collection that maps keys to values


Set—An unordered collection with no duplicates
 SortedSet—An ordered collection with no duplicates
List—an ordered collection, duplicates are allowed
SortedMap—a collection ordered by the keys
Note that there are two distinct hierarchies
Using Collections


import java.util.*
or import java.util.Collection;
There is a sister class, java.util.Collections;
that provides a number of algorithms for use with
collections: sort, binarySearch, copy,
shuffle, reverse, max, min, etc.
Collections Example
import java.util.*; // importing Arrays, List, and Collections
public class TestCollections {
public static void main(String args[]) {
String[] array = {"Phil", "Mary", "Betty", "bob"};
List<String> myList = Arrays.asList(array);
Collections.sort(myList);
System.out.println("Sorted: " + myList);
int where = Collections.binarySearch(myList, "bob");
System.out.println("bob is at " + where);
Collections.shuffle(myList);
System.out.println("Shuffled: " + myList);
}
}
Sorted: [Betty, Mary, Phil, bob]
bob is at 3
Shuffled: [Betty, bob, Phil, Mary]
Collections are interfaces





Collection is actually an interface
Each kind of Collection has one or more
implementations
You can create new kinds of Collections
When you implement an interface, you promise to
supply the required methods
Some Collection methods are optional

How can an interface declare an optional method?
Creating a Collection

All Collection implementations should have two
constructors:




A no-argument constructor to create an empty collection
A constructor with another Collection as argument
All the Sun-supplied implementations obey this
rule, but—
—if you implement your own Collection type, this
rule cannot be enforced, because an Interface
cannot specify constructors
Collection<E>: Basic operations
int size( );
boolean isEmpty( );
boolean contains(Object element);
boolean add(E element);
// Optional
boolean remove(Object element); // Optional
Iterator<E> iterator( );
Collection: Iterator
public interface Iterator<E> {
boolean hasNext( );
// true if there is another element
E next( );
// returns the next element (advances the iterator)
void remove( ); // Optional
// removes the element returned by next
}
Using an Iterator




static void printAll (Collection coll) {
Iterator iter = coll.iterator( );
while (iter.hasNext( )) {
System.out.println(iter.next( ) );
}
}
hasNext() just checks if there are any more elements
next() returns the next element and advances in the
collection
Note that this code is polymorphic—it will work for
any collection
Object[] toArray()


Defined in java.util.Collection interface, so it applies to all
classes that implement Collection
Object[ ] toArray( )




Creates a new array of Objects
Defined in java.util.Collection interface, so it applies to all classes
that implement Collection
Example:
Object[ ] newArray = myCollection.toArray( );
Problem: Returns an array of Objects, so we have to cast every
time we want to use something from the array
<T> T[] toArray(T[] a)



Also defined in java.util.Collection interface, so it applies to all classes
that implement Collection
More complex, but definitely worth knowing
This version of toArray:



Is a message to some collection of type T objects
Takes as parameter an array of some type T
Puts the objects from the collection into the array



If the array is longer than needed, a null is put in after the data
If the array is too short, a new array (of the correct type) is created and returned
Examples:
ArrayList<String> list = new ArrayList<String>();
// Put some Strings into list here
String[ ] a = new String[20];
list.toArray(a);
String[] b = list.toArray(new String[0]);
Set operations
A
B
Set union: A  B
A
B
Set intersection: A  B
A
B
Set difference: A – B
Collection: Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear( );

The last four operations are optional, in order to allow for
immutable collections


That is, they might throw an UnsupportedOperationException
addAll, removeAll, retainAll return true if the object receiving
the message was modified
Set operations
A
B
Set union: A  B
setC = setA.addAll(setB);
A
B
Set intersection: A  B
setC = setA.retainAll(setB);
A
B
Set difference: A – B
setC = setA.removeAll(setB);
Mixing Collection types

Note that most methods, such as
boolean containsAll(Collection<?> c);

are defined for any type of Collection, and take any
type of Collection as an argument
This makes it very easy to work with different types of
Collections
singleton

static <T> Set<T>Collections.singleton(T e)
returns an immutable set containing only the element e


This is handy when you have a single element but you would
like to use a Set operation
c.removeAll(Collections.singleton(e)); will
remove all occurrences of e from the Collection c
The List interface


The order of elements in a List is important, and
there may be duplicate elements
Operations are exactly those for Collection
int size( );
boolean isEmpty( );
boolean contains(Object e);
boolean add(E e);
boolean remove(Object e);
Iterator iterator( );
Object[ ] toArray( );
<T> T[ ] toArray(T a[ ]);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear( );
List implementations


List is an interface; you can’t say new List ( )
There are two implementations:



LinkedList gives faster insertions and deletions
ArrayList gives faster random access
It’s poor style to expose the implementation
unnecessarily, so:

Good: List list = new LinkedList ( );
Not as good: LinkedList list = new LinkedList ( );
Inherited List methods



list.remove(e) removes the first e
add and addAll add to the end of the list
To append one list to another:
list1.addAll(list2);

To append two lists into a new list:
List list3 = new ArrayList(list1);
list3.addAll(list2);

Again, it's good style to hide the implementation
List: Positional access
E get(int index); // Required -- the rest are optional
E set(int index, E element);
void add(int index, E element);
E remove(int index);
boolean addAll(int index, Collection<? extends E> c);

These operations are more efficient with the
ArrayList implementation
List: Searching
int indexOf(Object o);
int lastIndexOf(Object o);

equals and hashCode work even if
implementations are different
Interface ListIterator

Iterators specific to Lists:
ListIterator listIterator( );
ListIterator listIterator(int index);


starts at the position indicated (0 is first element)
Methods that ListIterator inherits from Iterator:
boolean hasNext( );
E next( );
void remove( );

Additional methods:
boolean hasPrevious()
E previous()
List: Iterating backwards
boolean hasPrevious( );
E previous( );
int nextIndex( );
int previousIndex( );


Think of the iterator as “between” elements
Hence, next followed by previous gives you the
same element each time
ListIterator: More operations
void add(E o);


void set(E o);


Inserts an object at the cursor position
// Optional
Replaces the current element
void remove(int index); // Optional

Removes the last element that was returned by next() or
previous()
List: Range-view

List<E> subList(int from, int to) allows you
to manipulate part of a list



Notice the unusual capitalization
A subList is a “view” into the actual list; manipulating
it is manipulating the original list.
A subList may be used just like any other list

However, it is dangerous to modify the original list and
expect the subList to remain consistent
The End
References:
http://java.sun.com/docs/books/tutorial/collections
/interfaces/collection.html
http://java.sun.com/docs/books/tutorial/collections
/interfaces/list.html