Transcript collections

Collections Framework

“A collections framework is a unified
architecture for representing and
manipulating collections.”
• Data Structures ---Interfaces &
Implementations
• Algorithms ----through
java.util.Collections
First Data Structures….
“Collections”

A collection groups multiple elements
into a single unit.
• Vector
• Hashtable
• array
Hierarchy of Interfaces

Collection (java.util.Collection)
• Set

SortedSet
• List
• Queue

Map
• SortedMap
Collection



“A collection represents a group of
objects known as its elements.”
Some implementations allow
duplicates, some don’t.
Some implementations automatically
sort the elements, some don’t.
Types of Collections

Set
• Cannot contain duplicates.

SortedSet
• Is a set.
• Maintains elements in sorted order.

List
• An ordered collection.

Queue
• A collection with additional insertion, extraction, and
inspection operations.
• Usually FIFO.
Collections that aren’t
Collections

Map
• Maps keys to values.
• Cannot contain duplicate keys.

SortedMap
• Maintains key/value pairs in key order.
Set Implementations

HashSet
• No order guarantee., like “hash table”.

TreeSet
• Value ordered.

LinkedHashSet
• Ordered oldest to newest, in terms of
insertion.
no duplicate elements are allowed in a
Set
List Implementations

ArrayList
• Most common.

LinkedList
• Use if insertions are often done at the head.
Positional access:
add elements at specific positions
add and addAll without a position add to the end of the List
set and remove return the element overwritten or removed
Search: return the position of elements
Extended Iteration: extended Iterator interface
Range-view:
return a sublist
if the sublist is modified, the original List is as well
Map Implementations

Hashtable
• No order guarantee
• Constant time get , put
• no nulls

HashMap
• Like Hashtable but allows nulls

TreeMap
• Key order iteration.

LinkedHashMap
Features of Maps

Copying via constructor:
//m is another Map
Map<K, V> copy = new HashMap<K, V>(m);

Check if 2 maps have same entries,
if (m1.entrySet().containsAll(m2.entrySet())) {
...
}

Check if two maps have the same
keys:
if (m1.keySet().equals(m2.keySet())) {
...
}
Queue Implementations

LinkedList
• Allows for a FIFO queue.

PriorityQueue
• Iteration based on a value specified at
element insertion.
• Has the property that only the highestpriority element can be accessed at any
time.
About Sorted Collection Classes
For o1.compareTo(o2):
• returns negative if o1 < o2
• returns 0 if o1 == o2
• returns positive if o2 > o2
Sort by?
Object
Natural Ordering
Byte, Integer, Long, Short, Float, Double, BigInteger, BigDecimal
Signed Numerical
Character
Unsigned Numerical
Boolean
Boolean.FALSE < Boolean.TRUE
File
System Dependent
Alphabetical by Path
String
Alphabetical
Date
Chronological
CollationKey
Locale-Specific Alphabetical
SortedSet

Differences from Set:
• Iterator traverses the SortedSet in order
• toArray returns an in order array of the
elements
• toString returns a String of the contents in
order
Implementations: ConcurrentSkipListSet,
TreeSet
SortedMap

Differences from Map:
• Iterator traverses the collection views of a
SortedMap in order
• toArray returns an in order array of the keys,
values or entries
• toString returns a String of the contents in
order
Implementations: ConcurrentSkipListMap,
Now a few common data
structures….
LinkedList





Constant insertion and removal at
first/last
Constant insertion and removal at
an Iterator
Lookup is slow (linear time)
Traversal is fast (constant time to
find the next element)
Ordered by insertion
Trees



Logarithmic insertion and lookup
Sorted order
Classes: TreeSet, TreeMap
Review of some implemented
common data structures
Interfaces
Implementations
Hash Table
Set
Resizable
Array
HashSet
List
Tree
Hash Table
Linked List + Linked
List
LinkedHash
Set
TreeSet
ArrayList
LinkedList
Queue
Map
HashMap
TreeMap
LinkedHash
Map
Traversing through
Collections….
Iterate through Collections

for-each
•
If modification of the Collection won’t be
done, use the for-each.
for (Object o : collection){
System.out.println(o);
}

Iterator
•
If modifications are to be done, or the foreach doesn’t excite you, use the Iterator.
Iterator



“Enables you to traverse through a
collection and to remove elements from
the collection selectively, if desired.”
Use the iterator() method on the
Collection to get the Collection’s Iterator.
Methods:
• boolean hasNext()
• Object next()
• void remove()

Example
Vector vec = new Vector;
// Populate it... Then later, iterate over its elements…..
Iterator it = vec.iterator ();
while (it.hasNext ()) {
Object o = it.next (); //or whatever the class type is
}
Another example – no casting
ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist ………not showing this
//now cycle through and visit each element in ArrayList
for (Iterator<String> it = alist.iterator(); it.hasNext(); )
{ String s = it.next(); //no casting done here
System.out.println(s); }
Example again – with for
ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist ………
for (String s : alist)
{ System.out.println(s); }
Example again –older style with
casting
ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist ………
for (Iterator it = alist.iterator(); it.hasNext(); )
{ String s = (String)it.next(); // Downcasting is required pre Java 5.
System.out.println(s); }
ListIterator




Besides the basic Iterator class,
ListIterator is implemented by the
classes that implement the List
interface (ArrayList, LinkedList, and
Vector)
Some methods:
int nextIndex() Returns the index of the element that would be
returned by a subsequent call to next().
int previousIndex() Returns the index of the element that would
be returned by a subsequent call to previous().
Converting Collection to Arrays

Some Collections allow you to
convert to an Array
//c is a Collection of Objects
Object[] a = c.toArray();
//c is a collection of Strings
//we pass an empty string so the compiler knows
the correct result type
String[] a = c.toArray(new String[0]);
Now for ALGORITHMS
java.util.Collections --
HOW to get some predefined useful
ALGORITHMS ---static method
ALGORITHMS
java.util.Collections methods

The collections class has the following methods
(static)..see API for complete list:
• sort(List <?> list) - sort the list
• binarySearch(List<? > list, T key) –binary
search for key
• reverse(List<?> list) - reverse the list
• fill(List <? super T> list, E value) overwrite every value in list with value
• copy(List <? super T> src, List<? extends T>
dest) - copy all the elements from src into
dest
• swap(List<?> list, int i, int j) - swap the
elements at the ith and jth position in list
• addAll(Collection<? super T> c, T...
MORE ALGORITHMS
java.util.Collections methods
•frequency(Collection<?> c, Object o) - how many
times does o appear in c
•disjoint(Collection<?> c1, Collection<?> c2) returns true if c1 and c2 share no elements
•min(Collection<? extends T> coll) – returns min
(see API for overloaded min)
•max(Collection<? extends T> coll) – returns max
(see API for voverloaded max)
Algorithms—example Sort
import java.util.*;
public class Sort {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
//sort using the elements comparator
Collections.sort(list);
System.out.println(list);
//sort using your own comparator
Collections.sort(list, new MyComparator());
System.out.println(list);
}
}
Algorithms- binarysearch
example
int pos = Collections.binarySearch(list,
key);
//if key isn’t in the list, add it in sorted
order
if (pos < 0) list.add(-pos-1), key);
look up API to see why I add at -pos-1
position..hint if key is not found then
binarySearch returns=(-(insertion point) - 1)
 Suppose pos= -4
that means
insertion_point=3