CPAN322 Java Application Programming
Lecture #1: Data Structure
A data structure is a special format of organizing and storing data . Java provides standard API for handling complex data structures such as List, sets, hashes and maps. The Java Collection framework forms the basis for working with different types of data structures. The java package java.util offers many interfaces and classes for managing data structure with better performance in adding, removing , searching and managing elements of such structures.
Arrays and Array Lists:
An array is a fixed-length sequence of values of the same data types. Arrays can be one dimensional or multidimensional and can hold data of object type or primitive type. In the following statement , we are declaring a one dimensional array of 3 Strings:
String names[]=new String [3];
The position of an element in the array is identified by an integer number called index. The index of an array starts from 0 and end by length, where length is an instance variable of the array object.
To reference an array element, we specify the array name and the element’s position. We can initialize an array by allocating it and then filling each entry. For example:
names[0]="John";
names[1]="Rob";
names[2]="Linda";
As an alternative, we can also declare and initialize the array in one statement as follows:
String names[]={“John”,”Rob”,”Linda”};
The following example shows how to traverse through an array:
for(int i=0;i<names.length,i++)
{
System.out.println(names[i]);
}
An array variable stores a reference to the array. To copy the elements of an array , use clone method. For example:
String users=(String)names.clone();
Where the clone method returns an Object. Therefore we need to cast it to the proper type.
Copying the array variable yields in another reference to the same array. The following statement will make another reference to names array called users.
String users[]=names;
To copy some elements from one array to another, we can use the static method System.arraycopy. For example:
int amount[]={10,20,30,40,50,60,70,80,90,100};
int discount[]=new int[5];
System.arraycopy(amount,5,discount,0,5);
for (int i=0;i<discount.length;i++)
{
System.out.println(discount[i]);
}
The above example will copy the last 5 elements from amount array to discount array.
Class Arrays provides static methods for manipulating arrays such as sort, binarySearch, equals, and fill. The method asList returns a fixed-size list backed by the specified array.
Two-dimensional arrays are used to represent tables of values consisting of data arranged in rows and columns. When we construct a two dimensional array, we need to determine how many rows and columns are needed. For example:
int marks[][]=new int[3][5];
Here we are declaring an array of 3 rows and 5 columns. We have to use two indexes to reference an element of a two dimensional array. The first index identifies the element’s row and the second identifies the element’s column. For example:
marks[0][0]=90;
Two dimensional arrays can be declared and initialized in one statement as follows:
int marks[][]={{60,60,70,80,85},{78,67,88,82,75},{81,89,92,87,86}};
The following example shows how to traverse through all the elements of marks array:
for (int i=0;i<marks.length;i++)
{
for(int j=0;j<marks[i]..length;j++)
System.out.println(marks[i][j]);
}
Java allows declaring two-dimensional arrays with variable length of rows. For example:
String projects[][[]=new String [2][[];
Then we can allocate each row separately. Or we can declare and initialize the array in one statement as follows:
String projects[][[]={{“Java”,”C”,”VB”},{“C”,”PER”}};
And we can traverse through projects array as we did with marks array.
An array list is a data structure that manages a sequence of objects. The position of an object in the array list is identified by an integer number called index. The index of an array list starts from 0 and end by size()-1 where size() method returns the number of objects in the array list. Accessing an object out of the array list boundaries generates bound error exception.
Primitive data types are not objects, therefore we cannot store them directly into an array list. Instead we have to use wrapper classes (Like Integer, Double, Float and Boolean).
To declare an empty array list, we use:
ArrayList arlitems=new ArrayList();
Some of the methods of ArrayList class are:
· add
To add items to arlitems, we use add method, for example assume that we have the following class :
class Person
{
private String name;
public Person(String name)
{
this.name=name;
}
public String getName()
{
return name;
}
public void setName(String name)
{
this.name=name;
}
}
Objects of class Person can be added to our array list using add method as follows:
arlitems.add(new Person(“john”));
add method can be also used to insert an object at a certain position. For example:
arlitems.add(0,new Person(“Smith”));
· set
Used to overwrite existing values, for example:
arlitems.set(0,new Person(“Rob”));
· get
Used to access an object by its index. The return value of this method is an Object. Therefore we need to cast the Object back to the proper class:
Personobj=(Person)arlitems.get(0);
Returns the first Person object in the array list arlitems.
· remove
Used to remove an object from the array indicated by its index. For example to remove the second object from arlitems:
arlitems.remove(1);
To traverse through all the elements in arlitems, we can use for statement as follows:
for(int i=0;i<arlitems.size()-1,i++)
{
Person p=(Person) arlItems.get(i);
System.out.println(p.getName());
}
To check whether an element exists in an array list, check all the elements. For example, the following method will determine is a person is found in arlitems:
public Boolean findElement(Person p)
{
for(int I=0;I<arlitems.size()-1,i++)
{
Person per=(Person) arlItems.get(i);
if per.equals(p)
return true;
}
return false;
}
The class Collections provides static methods for manipulating collections that implements List interface. Some of these methods operates on lists such as: sort, shuffle, reverse, binarySearch, fill, and copy.
The static methods max and min of Collections class operates on Collections.
Sets and Maps:
A set is an unordered collection of distinct elements. Duplicated elements in a set are not allowed. Adding a duplicated element is ignored silently To implement a set , Java provides two classes: HashSet and TreeSet. Both classes realize Set interface. Set interface is derived from the Collection interface, the root interface in the collection hierarchy. Collection interface has methods for adding, removing, comparing, retaining elements in the collection. It also has methods for determining the size and the hashCode for a collection. There are also methods for converting a collection into an array. Elements in the Collection are accessed using an the Iterator interface.
HashSet class implements a set based on a hash table. A hash table can be implemented as an array of buckets, sequences of links that holds elements with the same hash code. A hash function computes an integer value called the hash code for an object. The hash code is used to locate a specific element. A collision occurs when two distinct objects have the same hash code. A good hash function minimizes collisions.
You should define hashCode method for your own classes by combining the hash code for the instance variables. Your hashCode method should be also compatible with equals methods. Two equal objects must yield the same hash code.
Set scores=new HashSet();
scores.add("Score 1");
scores.add("Score 2");
Also we can use the following syntax to declare and initialize a HashSet:
String arr[]={"Score 1","Score 2"};
Set scores=new HashSet(Arrays.asList(arr));
To remove an element from the HashSet, we use remove method:
Scores.remove(“Score 1”);
To test whether an element is contained in a set , we use contains method:
If(scores.contains())
{
// do something
}
To list all the elements in a set, we use the Iterator interface. This interface defines the methods :next, hasNext and move. The following example shows how to list all the elements in scores:
Iterator it=scores.iterator();
while(it.hasNext())
System.out.println((String)it.next());
The elements are not stored in the order they are inserted, but in the order HashSet keeps them for quick elements locating.
Some of the methods used with a HashSet are:
· add
Adds the specified element to the set if it is not already present.
· clear
Removes all of the elements from the set.
· contains
Returns true if the set contains the specified element.
· isEmpty
Returns true if the set contains no elements.
· iterator
Returns an iterator over the elements in the set.
· remove
Removes the specified element from the set if it is present.
· size
Returns the number of elements in the set.
TreeSet is a sorted collection of data. It stores its elements in a tree and is constructed in the same way as HashSet.
Some of the methods used with a HashTree are:
· add
Adds the specified element to the set if it is not already present.
· clear
Removes all of the elements from the set.
· comparator
Returns the comparator used to order the sorted set, or null if this tree set uses its elements natural ordering.
· contains
Returns true if the set contains the specified element.
· first
Returns the first (lowest) element currently in the sorted set.
· headSet
Returns a view of the portion of the set.
· last
Returns the last (highest) element currently in the sorted set.
· iterator
Returns an iterator over the elements in the set.
· remove
Removes the specified element from this set if it is present.
· size
Returns the number of elements in this set.
A Map is a data type that keeps association between keys and values and cannot contain duplicate keys. To implement a Map, Java provides two classes: HashMap and TreeMap. Both classes realize Map interface. HashMap stores its elements in a Hashtable.
Map login=new HashMap();
To add an association, we use put method:
login.put(“user1”,”password1”);
To return a value that is associated with a key, we use get method:
System.out.println(login.get(“user1”);
If the key passes was not found, get method would return null.
To traverse through all the keys and values in a map, iterate through the key set and find the keys and their values as shown below:
Set ks=login.keySet();
it=ks.iterator();
while(it.hasNext())
{
Object key=it.next();
Object value=login.get(key);
System.out.println("Key is :"+key + " and value is "+ value );
}
TreeMap is a sorted collection of data. It stores its elements in a tree and is constructed in the same way as MapSet.
To sort the elements of a tree in a particular order, you can implements the Comparator interface. This interface has two methods: compare and equals.
Some of the methods used with HashMap and TreeMap are:
· values
Returns a collection view of the values contained in the map.
· size
Returns the number of key-value mappings in the map.
· remove
Removes the mapping for this key from the map if present.
· put
Associates the specified value with the specified key in the map.
· keySet
Returns a set view of the keys contained in the map.
· get
Returns the value to which the specified key is mapped in the identity hash map, or null if the map contains no mapping for this key..
· entrySet
Returns a collection view of the mappings contained in the map.
· containsValue
Returns true if the map maps one or more keys to the specified value.
· clear
Removes all mappings from the map.
· containsKey
Returns true if the map contains a mapping for the specified key.
Vectors and Stacks:
Vector class enables us to create an array-like data structure that can grow and shrink dynamically. The capacity of a vector can be incremented manually by the programmer or automatically by the system. If not specified, the system will double the size of a vector to increment it’s capacity. To iterate through a vector , we use the Enumeration interface. The Enumeration interface work like Iterator interface. The only difference is that the Iterator can remove elements. Enumeration cannot.
Vectors are designed to store references to objects. To store data of primitive types, use wrapper classes like Integer, Float, Double. For example:
Vector v1=new Vector();
v1.addElement(new Integer(10));
v1.addElement(new Double(1.660));
v1.addElement(new Character('a'));
v1.addElement(new Boolean (true));
We could also use the following syntax to declare and initialize the vector:
Object ob[]= {new Integer(10),new Double(1.660),new Character('a'),new Boolean (true)};
Vector v=new Vector(Arrays.asList(ob));
Some of the methods used with Vectors are:
· add
Insert an element to a specific position in the vector. For example:
v1.add(1,new Integer(50));
Another version of add method will append an element to the end of the vector.
· get
Returns the element at a specific position in the vector.
· size
Used to find the number of components (elements) in the vector.
· capacity
Returns the current capacity of this vector
· trimToSize
Trims the capacity of this vector to be the vector's current size
· toArray
Returns an array containing all of the elements in this Vector in the correct order.
· set
Replaces an element at a specific position in the vector.
· removeElement
Removes the first occurrence of an element from the vector.
· clear
Removes all the elements form the vector.
· isEmpty
Tests if this vector has no components.
· contains
Tests if the specified object is a component in this vector.
· elements
Returns an enumeration of the components in the vector.
Stack class extends Vector class to implement a data structure. It is used to store objects. To store data of primitive types, use wrapper classes like Integer, Float and Double. For example:
Stack s1=new Stack();
s1.addElement(new Integer(10));
s1.addElement(new Double(1.660));
s1.addElement(new Character('a'));
Some of the methods used with Stacks are:
· empty
Tests if this stack is empty.
· pop
Removes the object at the top of this stack. The return value of this function is the object been removed. If none was found, the return value is null.
· peek
Looks at the object at the top of this stack without removing it from the stack
· push
Pushes an object onto the top of this stack
· search
Pushes an item onto the top of this stack