Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Collections in Java: Arrays

    Uploaded by

    Om Thacker
    java collections

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Collections in Java: Arrays

    Uploaded by

    Om Thacker
    13 views27 pages
    java collections

    Original Title

    Collections

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    java collections

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    13 views27 pages

    Collections in Java: Arrays

    Uploaded by

    Om Thacker
    java collections

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 27

    Collections in Java

    Arrays
    n

    Has special language support Iterator (i) Collection (i) Set (i),
    u

    Iterators
    n

    Collections (also called containers)


    n n

    HashSet (c), TreeSet (c) ArrayList (c), LinkedList (c) HashMap (c), TreeMap (c)

    List (i),
    u

    Map (i),
    u

    OOP: Collections

    Array
    Most efficient way to hold references to objects.
    data index

    Car Car
    0 1 2

    Car
    3 4 5

    Car
    6 7

    Advantages
    n n n

    An array know the type it holds, i.e., compile-time type checking. An array know its size, i.e., ask for the length. An array can hold primitive types directly. An array can only hold one type of objects (including primitives). Arrays are fixed size.
    2

    Disadvantages
    n n

    OOP: Collections

    Array, Example
    class Car{}; Car[] cars1; Car[] cars2 = new Car[10]; // minimal dummy class // null reference // null references

    for (int i = 0; i < cars2.length; i++) cars2[i] = new Car(); // Aggregated initialization Car[] cars3 = {new Car(), new Car(), new Car(), new Car()}; cars1 = {new Car(), new Car(), new Car()};

    Helper class java.util.Arrays


    n n n n

    Search and sort: binarySearch(), sort() Comparison: equals() (many overloaded) Instantiation: fill() (many overloaded) Conversion: asList()
    3

    OOP: Collections

    Overview of Collection
    A collection is a group of data manipulate as a single object.
    Corresponds to a bag.

    Insulate client programs from the implementation.


    n

    array, linked list, hash table, balanced binary tree

    Like C++'s Standard Template Library (STL) Can grow as necessary. Contain only Objects (reference types). Heterogeneous. Can be made thread safe (concurrent access). Can be made not-modifiable.
    4

    OOP: Collections

    Collection Interfaces
    Collections are primarily defined through a set of interfaces.
    n

    Supported by a set of classes that implement the interfaces

    [Source: java.sun.com]

    Interfaces are used of flexibility reasons


    n n

    Programs that uses an interface is not tightened to a specific implementation of a collection. It is easy to change or replace the underlying collection class with another (more efficient) class that implements the same interface.
    5

    OOP: Collections

    Collection Interfaces and Classes

    OOP: Collections

    [Source: bruceeckel.com]

    The Iterator Interface


    The idea : Select each element in a collection
    n

    Hide the underlying collection

    Collection isEmpty() add() remove() ...

    list

    Iterator hasNext() next() remove()

    Iterators are fail-fast


    n

    Exception thrown if collection is modified externally, i.e., not via the iterator (multi-threading).

    OOP: Collections

    The Iterator Interface, cont.


    // the interface definition Interface Iterator { boolean hasNext(); Object next(); // note "one-way" traffic void remove(); }

    // an example public static void main (String[] args){ ArrayList cars = new ArrayList(); for (int i = 0; i < 12; i++) cars.add (new Car()); Iterator it = cats.iterator(); while (it.hasNext()) System.out.println ((Car)it.next()); }

    OOP: Collections

    The Collection Interface


    public interface Collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator(); // Bulk Operations boolean containsAll(Collection c); boolean addAll(Collection c); // boolean removeAll(Collection c); // boolean retainAll(Collection c); // void clear(); // // Array Operations Object[] toArray(); Object[] toArray(Object a[]); }
    OOP: Collections 9

    Optional Optional Optional Optional

    The Set Interface


    Corresponds to the mathematical definition of a set (no
    duplicates are allowed).

    Compared to the Collection interface


    n n n n

    Interface is identical. Every constructor must create a collection without duplicates. The operation add cannot add an element already in the set. The method call set1.equals(set2) works at follows
    u

    set1 set2, and set2 set1

    OOP: Collections

    10

    Set Idioms
    set1 set2
    n

    set1.addAll(set2) set1.retainAll(set2) set1.removeAll(set2)

    set1 set2
    n

    set1 set2
    n

    OOP: Collections

    11

    HashSet and TreeSet Classes


    HashSet and TreeSet implement the interface Set. HashSet
    n n n

    Implemented using a hash table. No ordering of elements. add, remove, and contains methods constant time complexity O(c).

    TreeSet
    n n n

    Implemented using a tree structure. Guarantees ordering of elements. add, remove, and contains methods logarithmic time complexity O(log (n)), where n is the number of elements in the set.
    12

    OOP: Collections

    HashSet, Example
    // [Source: java.sun.com] import java.util.*; public class FindDups { public static void main(String args[]){ Set s = new HashSet(); for (int i = 0; i < args.length; i++){ if (!s.add(args[i])) System.out.println("Duplicate detected: " + args[i]); } System.out.println(s.size() + " distinct words detected: " + s); } }

    OOP: Collections

    13

    The List Interface


    The List interface corresponds to an order group of elements.
    Duplicates are allowed.

    Extensions compared to the Collection interface


    n

    Access to elements via indexes, like arrays


    u

    add (int, Object), get(int), remove(int), set(int, Object) (note set = replace bad name for the method) indexOf(Object), lastIndexOf(Object)

    Search for elements


    u

    n n

    Specialized Iterator, call ListIterator Extraction of sublist


    u

    subList(int fromIndex, int toIndex)

    OOP: Collections

    14

    The List Interface, cont.


    Further requirements compared to the Collection Interface

    add(Object)adds at the end of the list. remove(Object)removes at the start of the list. list1.equals(list2)the ordering of the elements is
    taken into consideration. Extra requirements to the method hashCode.
    n

    list1.equals(list2) implies that list1.hashCode()==list2.hashCode()

    OOP: Collections

    15

    The List Interface, cont.


    public interface List extends Collection { // Positional Access Object get(int index); Object set(int index, Object element); // Optional void add(int index, Object element); // Optional Object remove(int index); // Optional abstract boolean addAll(int index, Collection c); // Optional // Search int indexOf(Object o); int lastIndexOf(Object o); // Iteration ListIterator listIterator(); ListIterator listIterator(int index); // Range-view List subList(int from, int to);

    }
    OOP: Collections 16

    ArrayList and LinkedList Classes


    The classes ArrayList and LinkedList implement the
    List interface.

    ArrayList is an array based implementation where elements


    can be accessed directly via the get and set methods.
    n

    Default choice for simple sequence.

    LinkedList is based on a double linked list


    n n

    Gives better performance on add and remove compared to ArrayList. Gives poorer performance on get and set methods compared to ArrayList.

    OOP: Collections

    17

    ArrayList, Example
    // [Source: java.sun.com] import java.util.*; public class Shuffle { public static void main(String args[]) { List l = new ArrayList(); for (int i = 0; i < args.length; i++) l.add(args[i]); Collections.shuffle(l, new Random()); System.out.println(l); } }

    OOP: Collections

    18

    LinkedList, Example
    import java.util.*; public class MyStack { private LinkedList list = new LinkedList(); public void push(Object o){ list.addFirst(o); } public Object top(){ return list.getFirst(); } public Object pop(){ return list.removeFirst(); } public static void main(String args[]) { Car myCar; MyStack s = new MyStack(); s.push (new Car()); myCar = (Car)s.pop(); } }
    OOP: Collections 19

    The ListIterator Interface


    public interface ListIterator extends Iterator { boolean hasNext(); Object next(); boolean hasPrevious(); Object previous(); int nextIndex(); int previousIndex(); void remove(); void set(Object o); void add(Object o); } // Optional // Optional // Optional

    OOP: Collections

    20

    The Map Interface


    A Map is an object that maps keys to values. Also called an
    associative array or a dictionary .

    Methods for adding and deleting


    n n

    put(Object key, Object value) remove (Object key) get (Object key)

    Methods for extraction objects


    n

    Methods to retrieve the keys, the values, and (key, value) pairs
    n n n

    keySet() // returns a Set values() // returns a Collection, entrySet() // returns a set


    21

    OOP: Collections

    The MAP Interface, cont.


    public interface Map { // Basic Operations Object put(Object key, Object value); Object get(Object key); Object remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk Operations void putAll(Map t); void clear(); // Collection Views public Set keySet(); public Collection values(); public Set entrySet(); // Interface for entrySet elements public interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); } } OOP: Collections

    22

    HashMap and TreeMap Classes


    The HashMap and HashTree classes implement the Map
    interface.

    HashMap
    n n

    The implementation is based on a hash table. No ordering on (key, value) pairs.

    TreeMap
    n n

    The implementation is based on red-black tree structure. (key, value) pairs are ordered on the key.

    OOP: Collections

    23

    HashMap, Example
    import java.util.*; public class Freq { private static final Integer ONE = new Integer(1); public static void main(String args[]) { Map m = new HashMap(); // Initialize frequency table from command line for (int i=0; i < args.length; i++) { Integer freq = (Integer) m.get(args[i]); m.put(args[i], (freq==null ? ONE : new Integer(freq.intValue() + 1))); } System.out.println(m.size()+ " distinct words detected:"); System.out.println(m); } }

    OOP: Collections

    24

    Static Methods on Collections


    Collection
    n n n

    Search and sort: binarySearch(), sort() Reorganization: reverse(), shuffle() Wrappings: unModifiableCollection, synchonizedCollection

    OOP: Collections

    25

    Collection Advantages and Disadvantages


    Advantages Disadvantages

    Can hold different types of


    objects. Resizable

    Must cast to correct type Cannot do compile-time type


    checking.

    OOP: Collections

    26

    Summary
    Array
    n n

    Holds objects of known type. Fixed size.

    Collections
    n n n n

    Generalization of the array concept. Set of interfaces defined in Java for storing object. Multiple types of objects. Resizable.

    Queue, Stack, Deque classes absent


    n

    Use LinkedList.
    27

    OOP: Collections

    You might also like