Transcript CS102 – OOP - Bilkent University

Collections Framework
A very brief look at Java’s
Collection Framework
David Davenport
May 2010
Core Collection Interfaces

Set: A collection that cannot contain duplicate elements.

List: An ordered collection (sometimes called a sequence).
Lists can contain duplicate elements. The user of a List
generally has precise control over where in the List each
element is inserted, and can access elements by their
integer index (position).

Queue: A collection used to hold multiple elements prior
to processing.

Map: An object that maps keys to values. Maps cannot
contain duplicate keys: Each key can map to at most one
value.
The Hierarchy
SortedSet
TreeSet
AbstractSet
Set
AbstractCollection
Collection
List
AbstractList
AbstractSequentialList
Queue
AbstractQueue
LinkedHashSet
Vector
Stack
ArrayList
LinkedList
PriorityQueue
TreeMap
SortedMap
Map
HashSet
AbstractMap
HashMap
LinkedHashMap
Examples…
for ( Object o : collection)
System.out.println( o);
Iterator i = collection.iterator();
while ( i.hasNext() )
System.out.println( i.next() );
import java.util.*;
public class FindDups {
public static void main( String args[]) {
Set<String> s = new HashSet<String>();
for ( String a : args)
if ( !s.add( a) )
System.out.println( "Duplicate: " + a);
System.out.println( s.size() + " distinct words: “ + s );
}
}
Note use of Set for
variable s allows
change to TreeSet, for
example
Examples…
import java.util.*;
public class Freq {
public static void main( String args[] ) {
Map<String, Integer>
m=
new HashMap<String, Integer>();
}
}
// Initialize frequency table from command line
for ( String a : args) {
Integer freq = m.get(a);
m.put( a, (freq == null ? 1 : freq + 1) );
}
System.out.println( m.size() + " distinct words:“ );
System.out.println(m);
Run with…
java Freq if it is to be it is up to me to delegate
output:
8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}
Try changing the
implementation to
TreeMap or
LinkedHashMap
Collections class…
public static <E> void swap( List<E> a, int i, int j) {
E tmp = a.get(i);
a.set( i, a.get(j) );
public static void shuffle( List<?> list, Random rnd) {
a.set( j, tmp);
for( int i = list.size(); i > 1; i--)
}
swap( list, i - 1, rnd.nextInt(i) );
}
import java.util.*;
public class Shuffle {
public static void main( String args[]) {
List<String> list = new ArrayList<String>();
for( String a : args)
list.add( a);
Collections.shuffle( list, new Random());
System.out.println( list);
}
Can also…
}
sort, reverse, fill, copy, swap, addAll, retainAll, …
and binarySearch on sorted list..
int pos = Collections.binarySearch( list, key);
if (pos < 0)
l.add(-pos-1);
From & To Arrays…
// *********************************************************************
// Create List from an Array
// - asList uses original array, or use new to construct new copy.
// *********************************************************************
String[] animals = { "dog", "cat", "mouse", "mouse", "elephant", "horse", "camel"};
// List<String> list = Arrays.asList( "dog", "cat", "mouse", "elephant", "horse", "camel");
// List<String> list = Arrays.asList( animals);
// List<String> list = new ArrayList<String>( Arrays.asList( animals) );
List<String> list = new LinkedList<String>( Arrays.asList( animals) );
System.out.println( list);
// *********************************************************************
// Convert List back to Array
// *********************************************************************
// Object[] zoo = list.toArray();
String[] zoo = list.toArray( new String[0] );
for ( String creature : zoo)
System.out.println( creature);
Polymorphic Algorithms…
// *********************************************************************
// Use some of the polymorphic List algorithms
// *********************************************************************
// Collections.sort( list, Collections.reverseOrder() );
Collections.sort( list );
System.out.println( list);
String key = "giraffe";
int pos = Collections.binarySearch( list, key);
if ( pos < 0)
{
System.out.println( "\"" + key + "\" not found.. adding");
list.add(-pos-1, key);
}
else
System.out.println( "\"" + key + "\" found at " + pos);
Collections.reverse( list);
Collections.shuffle( list);
Sets…
//
//
//
//
*********************************************************************
Sets cannot have duplicate elements
- HashSet (unordered), LinkedHashSet (order added), TreeSet (ordered)
*********************************************************************
// Set<String> s = new HashSet<String>();
// Set<String> s = new LinkedHashSet<String>();
Set<String> s = new TreeSet<String>();
for (String a : animals)
if ( !s.add( a) )
System.out.println( "Duplicate detected: " + a);
System.out.println( s.size() + " distinct words: " + s);
Arrays class…
// *********************************************************************
// The Arrays class provides some useful methods too...
// *********************************************************************
String[] animals = { "dog", "cat", "mouse", "mouse", "elephant", "horse", "camel"};
System.out.println( animals);
System.out.println( Arrays.toString(animals));
// doesn't work!
// does work!
Arrays.sort( animals);
System.out.println( Arrays.toString(animals));
// after sorting, can search...
System.out.println( "\"elephant\" is at " + Arrays.binarySearch( animals, "elephant") );