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