4.10 Week 10 -- I/O 4 Operator Precedence and Associativity4.8 Week 8 - JButtons, JFrames, ... 4.9 Week 9 - Collections

4.9 Week 9 - Collections

4.9.1 Reading and Web Sites

  1. Read van der Linden Chapter 15, Collections (pages 452-487)
  2. Go through the Java Collections Tutorial

4.9.2 Notes

  1. Why Collections
    1. A set of data structures for holding and accessing objects
    2. Already implemented, re-usable
    3. Fast execution
    4. Efficient memory usage
    5. Need to choose the "right one"
    6. Provides iterators and other access methods.
    7. This may be one of the best ways for a programmer dealing with complex structures to get the code right quickly.
    8. It will also let others familiar with collections understand the code.
  2. Collection types
    1. sets only one of each entry
    2. list ordered list
    3. ArrayList fast random access, more overhead than LinkedList.
    4. LinkedHashList Most overhead but accesses fast randomly even with large and growing data structures.
    5. TreeSet A sorted set. compairTo order.
    6. map are associative arrays or Perl hashes. A sparse array with out the requirements of a positive integer index.
    7. IdentityHashMap use with extreme caution - or avoid all together. Uses (k1==k2) Instead of (k1==null ? k2==null : k1.equals(k2))
    8. HashMap Fastest, cheapest, no order.
    9. LinkedHashMap Insertion order.
    10. TreeMap Sorted.
  3. Examples
    1. ArrayList1 
      /* Louis Taber  PCC  3/5/2003  */

import java.util.*;

class ArrayList1
{
public static void main( String [] args)
  {
  String sentence = "Greed is never good";

  List list = new ArrayList();

  for( int i=0; i<sentence.length(); i++)
    {
    Character ch = new  Character( sentence.charAt(i) ) ;
    System.out.print(ch); 
    list.add(ch);
    }
  System.out.println("");

  traverse(list);
  traverse_r( (ArrayList)list);
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    Character ch = (Character)iter.next();
    System.out.print(ch);
    }
  System.out.println("");
  }


static void traverse_r( ArrayList lst )
  {
  ListIterator iter = lst.listIterator( lst.size() );

 
  while( iter.hasPrevious())
    {
    Character ch = (Character)iter.previous();
    System.out.print(ch);
    }
  System.out.println("");
  }

}

      Greed is never good
Greed is never good
doog reven si deerG
    2. LinkedHashMap1 
      /* Louis Taber  PCC  3/12/2003  */
/* Linked Hash Map demo program */
/* Guarantees traversal in insertion order */

import java.util.*;

class LinkedHashMap1
{
public static void main( String [] args)
  {
  System.out.println("Linked Hash Map demo program");
  Character r_value;
  String sentence = "Greed is never good";

  LinkedHashMap list = new LinkedHashMap();

  System.out.println( sentence + "/n" );

  for( int i=0; i<sentence.length(); i++)
    {
    String key = "" + (i%10);
    Character value = new  Character( sentence.charAt(i) ) ;
    if( (r_value = (Character)list.put( key, value)) == null )
      {
      System.out.println("Added:    " + 
                 value + " With key " + key );
      }
    else
      {
      System.out.println("Replaced: " + 
                 r_value + " with " + value);
      }
    }
  System.out.println("");

  traverse(list.keySet());
  traverse(list.values());
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    System.out.print( iter.next() + " " );
    }
  System.out.println("");
  }

}

      Linked Hash Map demo program
Greed is never good/n
Added:    G With key 0
Added:    r With key 1
Added:    e With key 2
Added:    e With key 3
Added:    d With key 4
Added:      With key 5
Added:    i With key 6
Added:    s With key 7
Added:      With key 8
Added:    n With key 9
Replaced: G with e
Replaced: r with v
Replaced: e with e
Replaced: e with r
Replaced: d with  
Replaced:   with g
Replaced: i with o
Replaced: s with o
Replaced:   with d

0 1 2 3 4 5 6 7 8 9 
e v e r   g o o d n
    3. HashList1 
      /* Louis Taber  PCC  3/12/2003  */
/* HashList demo program */

import java.util.*;

class HashList1
{
public static void main( String [] args)
  {
  String sentence = "Greed is never good";

  Set list = new HashSet();

  System.out.println( sentence + "/n" );

  for( int i=0; i<sentence.length(); i++)
    {
    Character ch = new  Character( sentence.charAt(i) ) ;
    if( list.add(ch) )
      {
      System.out.println("Added:  " + ch);
      }
    else
      {
      System.out.println("Failed: " + ch);
      }
    }
  System.out.println("");

  traverse(list);
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    Character ch = (Character)iter.next();
    System.out.print(ch);
    }
  System.out.println("");
  }

}

      Greed is never good/n
Added:  G
Added:  r
Added:  e
Failed: e
Added:  d
Added:   
Added:  i
Added:  s
Failed:  
Added:  n
Failed: e
Added:  v
Failed: e
Failed: r
Failed:  
Added:  g
Added:  o
Failed: o
Failed: d

o dirngsGve
    4. LinkedHashSet1 
      /* Louis Taber  PCC  3/12/2003  */
/* Linked Hash Set demo program */

import java.util.*;

class LinkedHashSet1
{
public static void main( String [] args)
  {
  String sentence = "Greed is never good";

  LinkedHashSet list = new LinkedHashSet();

  System.out.println( sentence + "/n" );

  for( int i=0; i<sentence.length(); i++)
    {
    Character ch = new  Character( sentence.charAt(i) ) ;
    if( list.add(ch) )
      {
      System.out.println("Added:  " + ch);
      }
    else
      {
      System.out.println("Failed: " + ch);
      }
    }
  System.out.println("");

  traverse(list);
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    Character ch = (Character)iter.next();
    System.out.print(ch);
    }
  System.out.println("");
  }

}

      Greed is never good/n
Added:  G
Added:  r
Added:  e
Failed: e
Added:  d
Added:   
Added:  i
Added:  s
Failed:  
Added:  n
Failed: e
Added:  v
Failed: e
Failed: r
Failed:  
Added:  g
Added:  o
Failed: o
Failed: d

Gred isnvgo
    5. TreeMap1 
      /* Louis Taber  PCC  3/12/2003  */
/* Tree Map demo program */

import java.util.*;

class TreeMap1
{
public static void main( String [] args)
  {
  Character r_value;
  String sentence = "Greed is never good";

  SortedMap list = new TreeMap();

  System.out.println( sentence + "/n" );

  for( int i=0; i<sentence.length(); i++)
    {
    String key = "" + (i%10);
    Character value = new  Character( sentence.charAt(i) ) ;
    if( (r_value = (Character)list.put( key, value)) == null )
      {
      System.out.println("Added:    " + value + " With key " + key );
      }
    else
      {
      System.out.println("Replaced: " + r_value + " with " + value);
      }
    }
  System.out.println("");

  traverse(list.keySet());
  traverse(list.values());
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    System.out.print( iter.next() + " " );
    }
  System.out.println("");
  }

}

      Greed is never good/n
Added:    G With key 0
Added:    r With key 1
Added:    e With key 2
Added:    e With key 3
Added:    d With key 4
Added:      With key 5
Added:    i With key 6
Added:    s With key 7
Added:      With key 8
Added:    n With key 9
Replaced: G with e
Replaced: r with v
Replaced: e with e
Replaced: e with r
Replaced: d with  
Replaced:   with g
Replaced: i with o
Replaced: s with o
Replaced:   with d

0 1 2 3 4 5 6 7 8 9 
e v e r   g o o d n
    6. HashMap1 
      /* Louis Taber  PCC  3/12/2003  */
/* Hash Map demo program */

import java.util.*;

class HashMap1
{
public static void main( String [] args)
  {
  Character r_value;
  String sentence = "Greed is never good";

  HashMap list = new HashMap();

  System.out.println( sentence + "/n" );

  for( int i=0; i<sentence.length(); i++)
    {
    String key = "" + (i%10);
    Character value = new  Character( sentence.charAt(i) ) ;
    if( (r_value = (Character)list.put( key, value)) == null )
      {
      System.out.println("Added:    " + value + " With key " + key );
      }
    else
      {
      System.out.println("Replaced: " + r_value + " with " + value);
      }
    }
  System.out.println("");

  traverse(list.keySet());
  traverse(list.values());
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    System.out.print( iter.next() + " " );
    }
  System.out.println("");
  }

}

      Greed is never good/n
Added:    G With key 0
Added:    r With key 1
Added:    e With key 2
Added:    e With key 3
Added:    d With key 4
Added:      With key 5
Added:    i With key 6
Added:    s With key 7
Added:      With key 8
Added:    n With key 9
Replaced: G with e
Replaced: r with v
Replaced: e with e
Replaced: e with r
Replaced: d with  
Replaced:   with g
Replaced: i with o
Replaced: s with o
Replaced:   with d

3 5 7 2 0 9 4 8 6 1 
r g o e e n   d o v
    7. LinkedList2 
      /* Louis Taber  PCC  3/5/2003  */

import java.util.*;

class LinkedList2
{
public static void main( String [] args)
  {
  String sentence = "Greed is never good";

  List list = new LinkedList();

  for( int i=0; i<sentence.length(); i++)
    {
    Character ch = new  Character( sentence.charAt(i) ) ;
    System.out.print(ch); 
    list.add(ch);
    }
  System.out.println("");

  traverse(list);
  traverse_r( (LinkedList)list);
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    Character ch = (Character)iter.next();
    System.out.print(ch);
    }
  System.out.println("");
  }


static void traverse_r( LinkedList lst )
  {
  ListIterator iter = lst.listIterator( lst.size() );

 
  while( iter.hasPrevious())
    {
    Character ch = (Character)iter.previous();
    System.out.print(ch);
    }
  System.out.println("");
  }

}

      Greed is never good
Greed is never good
doog reven si deerG
    8. TreeSet1 
      /* Louis Taber  PCC  3/12/2003  */
/* Tree Set demo program */

import java.util.*;

class TreeSet1
{
public static void main( String [] args)
  {
  String sentence = "Greed is never good";

  SortedSet list = new TreeSet();

  System.out.println( sentence + "/n" );

  for( int i=0; i<sentence.length(); i++)
    {
    Character ch = new  Character( sentence.charAt(i) ) ;
    if( list.add(ch) )
      {
      System.out.println("Added:  " + ch);
      }
    else
      {
      System.out.println("Failed: " + ch);
      }
    }
  System.out.println("");

  traverse(list);
  System.exit(0);

  }

/* From Java Precisely, Peter Sestoft */

static void traverse( Collection coll )
  {
  Iterator iter = coll.iterator();
  while( iter.hasNext())
    {
    Character ch = (Character)iter.next();
    System.out.print(ch);
    }
  System.out.println("");
  }

}

      Greed is never good/n
Added:  G
Added:  r
Added:  e
Failed: e
Added:  d
Added:   
Added:  i
Added:  s
Failed:  
Added:  n
Failed: e
Added:  v
Failed: e
Failed: r
Failed:  
Added:  g
Added:  o
Failed: o
Failed: d

 Gdeginorsv

4.9.3 Lab Assignment -- Collections, Linked List

Rewrite the "Arrays and Objects" lab using the Java LinkedList class.

  1. Place each word in a String
  2. Place each word into a linked list.
  3. Traverse the linked list in both directions, printing out each word.

4.9.4 Lab Assignment -- Collections, Maps

Write a "phone book" program.

  1. Place at least 8 names and number pairs into a HashMap This can be hard coded.
  2. Look up 4 of the numbers based in the name. This can also be hard coded.
  3. Extra credit 1: Input the name and number pairs from a file.
  4. Extra credit 2: Input the name to look up from the keyboard.
  5. Extra credit 3: Extend the program to deal with multiple data fields: Address, City, Zip, Cell Phone, ...

Please turn in a listing and an example program run.

Instructor: ltaber@pima.edu ** My new Home at GeoApps in Tucson ** The Pima College Site

4.10 Week 10 -- I/O 4 Operator Precedence and Associativity4.8 Week 8 - JButtons, JFrames, ... 4.9 Week 9 - Collections