Title: intro-collections
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Intro to Collections

At some point, you will find that you want more support than simple Arrays can provide. In Computer Science, you can spend a whole semester studying datastructures and all of the various ways that data can be stored. Depending on what your primary operations are, you might choose a datastructure that is the most efficient for the normal operations that you encounter. Every datastructure has its own advantages and disadvantages.

First of all let's look at the characteristics of simple arrays.

1. Arrays are efficient.
2. You can store Classes, or primitives(int, long, double, etc.) in arrays.
3. You have to know how many elements that are required up front. Otherwise, you end up writing code to create a larger array and copy the previous array into the new bigger array.
4. Recent versions of Java have added an Arrays class in java.util that provides some support software.
5. Minimal software for working with Arrays. Difficult to insert into the middle of the array, etc. Using the Collection classes provides a large amount of supporting software and makes life easier than using simple arrays.

Why Use the Collections Framework?

1. Reduces programming effort -methods such as sorting algorithms are already written.
2. Increases program speed and quality.
3. By providing standard interfaces, its easier to integrate modules together.
4. Standard interfaces make it easier to learn how to use the classes available.

We will be working with a simplified version of 3 classes to demo Collections

ArrayList, LinkedList, and HashMap

We will focus on a few methods related to the 3 classes we have chosen.

ArrayList subset of methods

Proto-Type | Description
Object get(int index) | Returns the element at the specified position in this list.
int size() | Returns the number of elements in this collection.
boolean add(Object o) | Ensures that this collection contains the specified element (optional operation).
boolean remove(Object o) | Removes a single instance of the specified element from this collection, if it is present (optional operation).
Object remove(int index) | Removes the element at the specified position in this list (optional operation).
Object set(int index, Object element) | Replaces the element at the specified position in this list with the specified element (optional operation).
void add(int index, Object element) | Inserts the specified element at the specified position in this list (optional operation).

LinkedList subset of methods -everything in ArrayList + the following:

Proto-Type | Description
void addFirst(Object o) | Inserts the given element at the beginning of this list.
void addLast(Object o) | Appends the given element to the end of this list.
Object getFirst() | Returns the first element in this list.
Object getLast() | Returns the last element in this list.
Object removeFirst() | Removes and returns the first element from this list.
Object removeLast() | Removes and returns the last element from this list.

HashMap subset of methods

Proto-Type | Description
Object get(Object key) | Returns the value to which this map maps the specified key.
Object put(Object key, Object value) | Associates the specified value with the specified key in this map (optional operation).
Object remove(Object key) | Removes the mapping for this key from this map if present (optional operation).
int size() | Returns the number of key-value mappings in this map.

We will cover this material by doing a lot of in-class exercises

Exercise

Word Gather

Read in text from a file and store each of the words encountered into an ArrayList. You can use the StringTokenizer to split out the words from the text lines read from the file. Make the program interactive such that it has commands like:

- read filename
- change index newValue
- add index newValue
- remove value
- remove index

Change the ArrayList to a LinkedList

Make changes so the LinkedList stays in alphabetical order.

Create a routine that takes a LinkedList in alphabetical order and provides a BinarySearch algorithm

Random 2 Letter Sequences

Suppose you want to see how good the Java Random number generator is. You want to call it 1,000,000 times to generate 2 letter (lower case)sequences. For example, "ij", "za" "xh", etc. You would like to dump out the number of occurrences of each of the 2 letter strings. Try using a LinkedList, ArrayList and a HashMap class as your data structure. With the ArrayList, and the LinkedList try using simple "for" loop logic and also try Iterator logic for searching the data structure.

Time each of the possible solutions. The following is a piece of code that demonstrates how to do timing:


class Test
{

  public static void main(String[] args)
  {
    int max = Integer.parseInt(args[0]);
    long time = System.currentTimeMillis();
   // Do something   to waste time
    for (int i=0; i < max; i++)
    {
        Math.sqrt(212345.0);
    }
    System.out.println("Delta Time = "+(System.currentTimeMillis() - time));
  }
}



In a previous class we came up with the following solutions:
Sequence Solutions

Cross Reference Program

Create a program that reads in a file and prints out the same file with line numbers in front. At the end of the file printout, a cross reference listing is generated. In otherwords, the words found are listed and next to each word is a list of the line numbers where the word was found. A HashMap works well with the words being the key. The actual object stored can be an ArrayList of line numbers.

If you use a TreeMap to collect your entries, your list is automatically sorted. However, Capitalized entries are separate from non-capitalized entries. Suppose that you want the words to be listed in a non-case sensitive order.

MyArrayList

Try to create your own ArrayList using simple arrays

MyLinkedList

Try to create your own LinkedList using simple arrays

MyHashMap

Try to create your own HashMap using simple arrays

Try out your HashMap on the published Sequence Solution above.

A Solution created in a previous class meeting is as follows:
MyMap.java

Write a Pizza Server using a LinkedList

Add commands like:

- customer name : pizza info
- bakeNext
- listQueSize
- cutin index customer name : pizza info

Derive a Stack datastructure from LinkedList or ArrayList

Your Stack should have methods:

- push(int value);
- int pop() throws some exception
- int size()

Using your Stack datastructure (you can also use the Stack collection class found in Java.util), create a Reverse Polish calculator that can handle + * / and unary -

Numbers pushed on the stack will always be positive. If we need a negative number will will also push the unary - operator.

Let the operators be represented as negative numbers.

In reverse polish we would have the following expressions

7 + 8 is generated with:
push(7) push(8) push(+)

9 - 8 is generated with
push(9) push(8) push(-) push(+)

5*(2+3) - 9 is generated with
push(2) push(3) push(+) push(5) push(*)push(9) push(-) push(+)

Read in your Stack either from the command line or from a loop that reads in inputs from MyInput. For example, the following can be evaluated to a single number:

5 6 8.5 + *

The following evaluates to 2 numbers (42 and 5)

5 6 7.0 +

Last Updated: November 3, 2004 11:13 AM