Data Structures in Java and Introduction to Collection Framework

The Java Collection Framework is a unified architecture for representing and manipulating collections, enabling them to be manipulated independently of the details of their representation.

1. DATA STRUCTURES IN JAVA
Arun Seetharaman
March 10, 1998

2. TOPIC OBJECTIVES
•Understand some useful data structures in the java.util
package
•The Observer-Observable pattern
•Java Collection Framework
•Iterators

3. DATA STRUCTURES
•Well designed java.util package
•A bunch of dynamic data structures
•You do not have to write linked lists and hash tables
•Could be building blocks for more complicated data
structures

4. THE “VECTOR” CLASS
•A very generic structure for storing and retrieving
objects
•A very simple structure to use
•Tries to optimize storage, resulting in some extra
capacity at times
•Removal of elements closes the holes created

5. VECTOR OPERATIONS
public void addElement(Object);
public void clear();
public Object elementAt(int);
public void insertElementAt(
Object, int);
public void removeElementAt(int);
public void setElementAt(
Object, int);
public int size();

6. THE “HASHTABLE” CLASS
•Useful for searchable data structures
•Stores key-value pairs
•Key-based search mechanism
•Better than Vector for large amount of data that need
to be searched
public Object get(Object);
public Object put(Object,Object);
protected void rehash();

7. CALENDARS
•Date: mostly deprecated as of JDK1.1
•Calendar: Convert Date objects to fields
•GregorianCalendar: Important class that cater to the
differences between Julian date and Gregorian date.
Also understands timezones
•TimeZone: represents any timezone with the GMT offset

8. THE BITSET CLASS
•Represents a collection of bits
•Grows dynamically as bits are required
•Bits accessed using 0-based index
•public void and(BitSet);
•public void andNot(BitSet);
•public void or(BitSet);
•public void xor(BitSet);

9. OBSERVER-OBSERVABLE
PATTERN
•Update multiple objects from a common source of
data
•Displaying data in multiple formats like charts,
worksheet is a common example
•More often implemented using the MVC design pattern

10. THE “OBSERVABLE”
CLASS
•Represents the data source
•Can have one or more observers
void addObserver(Observer);
void deletebserver(Observer);
void notifyObservers(Object);
void setChanged();
boolean hasChanged();
void clearChanged();

11. AN OBSERVABLE ENTITY
class MsgObservable extends Observable
implements Runnable {
public void run() {
while(true) {
msg = waitForMsg();
setChanged();
notifyObservers(msg);
}
}
}

12. THE “OBSERVER”
INTERFACE
•Implemented when changes in an “Observable”
object need to be informed
•updateis invoked, when the Observable object calls
the notifyObservers method
class LogServer implements Observer {
public void update(Observable obs,
Object obj) {
logTheMsg(obj);
}
}

13. WHAT IS A COLLECTION
FRAMEWORK?
•Unified Architecture
•Interfaces :implementation-independence
•Implementations :reusable data structures
•Algorithms:reusable functionality
•Best-known examples
•C++ Standard Template Library (STL)
•Smalltalk

14. ARCHITECTURE
OVERVIEW
•Core Collection Interfaces
•General-Purpose Implementations
•Wrapper Implementations
•Abstract Implementations
•Algorithms

15. CORE COLLECTION
INTERFACES

16. COLLECTION INTERFACE
public interface Collection {
int size();
boolean isEmpty();
boolean contains(Object element);
Iterator iterator();
Object[] toArray();
Object[] toArray(Object a[]);
}

17. ITERATOR INTERFACE
•Replacement for Enumeration interface
•Adds remove method
•Improves method names
public interface Iterator {
boolean hasNext();
Object next();
void remove(); // Optional
}

18. COLLECTION EXAMPLE
public static boolean removeNulls(
Collection c) {
boolean modified = false;
for (Iterator i=c.iterator();i.hasNext();){
if (i.next()==null) {
i.remove();
modified = true;
}
}
return modified;
}

19. SET INTERFACE
•Adds no methods to Collection!
•Adds stipulation: no duplicate elements
•Mandates equals and hashCode calculation
public interface Set
extends Collection {
}

20. SET IDIOMS
Set s1, s2;
boolean subset= s1.containsAll(s2);
Set union= new HashSet(s1).addAll(s2);
Set intersection= new
HashSet(s1).retainAll(s2);
Set difference= new
HashSet(s1).removeAll(s2);

21. LIST INTERFACE
•A sequence of objects
public interface List
extends Collection {
Object get(int);
int lastIndexOf(Object);
int lastIndexOf(Object, int);
ListIterator listIterator(int);
…
}

22. LIST EXAMPLE
•Reusable algorithms to swap elements and randomize
public static void swap(List a,
int i, int j) {
Object tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
public static void randomize(List a) {
for (int i=a.size(); i>1; i --)
swap(a, i-1,
(r.nextInt() &~ (1<<31)) % i);
}

23. MAP INTERFACE
•A key-value mapping
public interface Map {
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
Object get(Object key);
public Set keySet();
public Collection values();
public Set entries();
}

24. MAP IDIOMS
Map m;
for (iterator i=m.keySet().iterator();
i.hasNext(); )
System.out.println(i.next());
Map a, b;
boolean isSubMap=
a.entries().containsAll(b.entries());
Set commonKeys= new
HashSet(a.keySet()).retainAll(b.keySet);

25. GENERAL-PURPOSE
IMPLEMENTATIONS

26. COLLECTIONS
•Exclusively static methods
•Contains polymorphic algorithms
•Work on collections
•Implementers can substitute algorithms

27. SYNCHRONIZATION
WRAPPERS
•Anonymous implementations, one per core interface
•Static factories take collection of appropriate type
•Thread-safety assured if all access via wrapper
•Iteration must be synchronized manually

28. SYNCHRONIZATION
WRAPPER EXAMPLE
Set s = Collections.synchronizedSet(
newHashSet());
...s.add("wombat");
// Thread-safe ...
synchronized(s) {
Iterator i = s.iterator(); // In synch block!
while (i.hasNext())
System.out.println(i.next());
}

29. UNMODIFIABLE
WRAPPERS
•Unmodifiable wrappers
•Analogous to synchronization wrappers
•Provide read-only access
•Available for core interfaces

30. CONVENIENCE
WRAPPERS
•List-view of arrays
•Multiple-copy list
•Singletons
•Empty collections

31. SOME NEEDS FOR
CUSTOMIZATION
•Persistence
•Highly concurrent collections
•High-performance, special-purpose
•Space-efficient representations
•Fancy data structures
•Convenience classes

32. REUSABLE ALGORITHMS
•Sorting
•Searching
•Shuffling
•Data Manipulation
•Extreme Values

33. ALGORITHMS:SORTING
•Uses an optimized merge sort
•Doesn’t reorder equal elements
•static void sort(List);
•static void sort(List, Comparator);

34. COMPARABLE AND
COMPARATOR
•Comparable: uses the natural ordering for that object
type
•int compareTo(Object);
•Comparator: can define custom ordering for object
•int compare(Object, Object);
•boolean equals(Object);

35. ALGORITHMS:
SEARCHING
•Works on sorted lists
•Uses the binary search algorithm
•int binarySearch(List, Object);
•int binarySearch(List, Object, Comparator);

36. ALGORITHMS:SHUFFLING
•Force randomness in the Collection
•A random object defines the randomness for the shuffle
operation
•void shuffle(List);
•void shuffle(List, Random);

37. OTHER ALGORITHMS
•Data Manipulation:
•void copy(List, List);
•void fill(List, Object);
•void reverse(List);
•Extreme Values:
•Object max/min(Collection);
•Object max/min(Collection, Comparator);

38. COMPATIBILITY
•Upward Compatibility
•Vector implements List
•Hashtable implements Map
•Arrays.toList(myArray)
•Backward Compatibility
•myCollection.toArray()
•Vector(myCollection)
•Hashtable(myMap)

39. TOPIC SUMMARY
•The java.util package has a good collection of data
structures
•Classes to support the Observer-Observable pattern
•Collection framework for improved data structures
•Many reusable algorithms implemented