Java – Data Structures

​The data structures provided by the Java utility package are very powerful and perform a wide range of functions. These data structures consist of the following interface and classes −

• Enumeration
• BitSet
• Vector
• Stack
• Dictionary
• Hashtable
• Properties

All these classes are now legacy and Java-2 has introduced a new framework called Collections Framework, which is discussed in the next chapter. −

The Enumeration

The Enumeration interface isn’t itself a data structure, but it is very important within the context of other data structures. The Enumeration interface defines a means to retrieve successive elements from a data structure.

For example, Enumeration defines a method called nextElement that is used to get the next element in a data structure that contains multiple elements.

To have more detail about this interface, checkThe Enumeration.

The BitSet

The BitSet class implements a group of bits or flags that can be set and cleared individually.

This class is very useful in cases where you need to keep up with a set of Boolean values; you just assign a bit to each value and set or clear it as appropriate.

For more details about this class, check The BitSet.

The Vector

The Vector class is similar to a traditional Java array, except that it can grow as necessary to accommodate new elements.

Like an array, elements of a Vector object can be accessed via an index into the vector.

The nice thing about using the Vector class is that you don’t have to worry about setting it to a specific size upon creation; it shrinks and grows automatically when necessary.

For more details about this class, check The Vector.

The Stack

The Stack class implements a last-in-first-out (LIFO) stack of elements.

You can think of a stack literally as a vertical stack of objects; when you add a new element, it gets stacked on top of the others.

When you pull an element off the stack, it comes off the top. In other words, the last element you added to the stack is the first one to come back off.

For more details about this class, check The Stack.

The Dictionary

The Dictionary class is an abstract class that defines a data structure for mapping keys to values.

This is useful in cases where you want to be able to access data via a particular key rather than an integer index.

Since the Dictionary class is abstract, it provides only the framework for a key-mapped data structure rather than a specific implementation.

For more details about this class, check The Dictionary.

The Hashtable

The Hashtable class provides a means of organizing data based on some user-defined key structure.

For example, in an address list hash table you could store and sort data based on a key such as ZIP code rather than on a person’s name.

The specific meaning of keys with regard to hash tables is totally dependent on the usage of the hash table and the data it contains.

For more detail about this class, check The Hashtable.

The Properties

Properties is a subclass of Hashtable. It is used to maintain lists of values in which the key is a String and the value is also a String.

The Properties class is used by many other Java classes. For example, it is the type of object returned by System.getProperties( ) when obtaining environmental values.

For more detail about this class, check The Properties.

Java – Collections Framework

Prior to Java 2, Java provided ad hoc classes such as Dictionary, Vector, Stack, and Propertiesto store and manipulate groups of objects. Although these classes were quite useful, they lacked a central, unifying theme. Thus, the way that you used Vector was different from the way that you used Properties.

The collections framework was designed to meet several goals, such as −

• The framework had to be high-performance. The implementations for the fundamental collections (dynamic arrays, linked lists, trees, and hashtables) were to be highly efficient.

• The framework had to allow different types of collections to work in a similar manner and with a high degree of interoperability.

• The framework had to extend and/or adapt a collection easily.

Towards this end, the entire collections framework is designed around a set of standard interfaces. Several standard implementations such as LinkedList, HashSet, and TreeSet, of these interfaces are provided that you may use as-is and you may also implement your own collection, if you choose.

A collections framework is a unified architecture for representing and manipulating collections. All collections frameworks contain the following −

• Interfaces − These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.

• Implementations, i.e., Classes − These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.

• Algorithms − These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface.

In addition to collections, the framework defines several map interfaces and classes. Maps store key/value pairs. Although maps are notcollections in the proper use of the term, but they are fully integrated with collections.

The Collection Interfaces

The collections framework defines several interfaces. This section provides an overview of each interface −

Sr.No.	Interface & Description
1	The Collection Interface This enables you to work with groups of objects; it is at the top of the collections hierarchy.
2	The List Interface This extends Collection and an instance of List stores an ordered collection of elements.
3	The Set This extends Collection to handle sets, which must contain unique elements.
4	The SortedSet This extends Set to handle sorted sets.
5	The Map This maps unique keys to values.
6	The Map.Entry This describes an element (a key/value pair) in a map. This is an inner class of Map.
7	The SortedMap This extends Map so that the keys are maintained in an ascending order.
8	The Enumeration This is legacy interface defines the methods by which you can enumerate (obtain one at a time) the elements in a collection of objects. This legacy interface has been superceded by Iterator.

The Collection Classes

Java provides a set of standard collection classes that implement Collection interfaces. Some of the classes provide full implementations that can be used as-is and others are abstract class, providing skeletal implementations that are used as starting points for creating concrete collections.

The standard collection classes are summarized in the following table −

Sr.No.	Class & Description
1	AbstractCollection Implements most of the Collection interface.
2	AbstractList Extends AbstractCollection and implements most of the List interface.
3	AbstractSequentialList Extends AbstractList for use by a collection that uses sequential rather than random access of its elements.
4	LinkedList Implements a linked list by extending AbstractSequentialList.
5	ArrayList Implements a dynamic array by extending AbstractList.
6	AbstractSet Extends AbstractCollection and implements most of the Set interface.
7	HashSet Extends AbstractSet for use with a hash table.
8	LinkedHashSet Extends HashSet to allow insertion-order iterations.
9	TreeSet Implements a set stored in a tree. Extends AbstractSet.
10	AbstractMap Implements most of the Map interface.
11	HashMap Extends AbstractMap to use a hash table.
12	TreeMap Extends AbstractMap to use a tree.
13	WeakHashMap Extends AbstractMap to use a hash table with weak keys.
14	LinkedHashMap Extends HashMap to allow insertion-order iterations.
15	IdentityHashMap Extends AbstractMap and uses reference equality when comparing documents.

The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and AbstractMap classes provide skeletal implementations of the core collection interfaces, to minimize the effort required to implement them.

The following legacy classes defined by java.util have been discussed in the previous chapter −

Sr.No.	Class & Description
1	Vector This implements a dynamic array. It is similar to ArrayList, but with some differences.
2	Stack Stack is a subclass of Vector that implements a standard last-in, first-out stack.
3	Dictionary Dictionary is an abstract class that represents a key/value storage repository and operates much like Map.
4	Hashtable Hashtable was part of the original java.util and is a concrete implementation of a Dictionary.
5	Properties Properties is a subclass of Hashtable. It is used to maintain lists of values in which the key is a String and the value is also a String.
6	BitSet A BitSet class creates a special type of array that holds bit values. This array can increase in size as needed.

The Collection Algorithms

The collections framework defines several algorithms that can be applied to collections and maps. These algorithms are defined as static methods within the Collections class.

Several of the methods can throw aClassCastException, which occurs when an attempt is made to compare incompatible types, or an UnsupportedOperationException, which occurs when an attempt is made to modify an unmodifiable collection.

Collections define three static variables: EMPTY_SET, EMPTY_LIST, and EMPTY_MAP. All are immutable.

Sr.No.	Algorithm & Description
1	The Collection Algorithms Here is a list of all the algorithm implementation.

How to Use an Iterator ?

Often, you will want to cycle through the elements in a collection. For example, you might want to display each element.

The easiest way to do this is to employ an iterator, which is an object that implements either the Iterator or the ListIterator interface.

Iterator enables you to cycle through a collection, obtaining or removing elements. ListIterator extends Iterator to allow bidirectional traversal of a list and the modification of elements.

Sr.No.	Iterator Method & Description
1	Using Java Iterator Here is a list of all the methods with examples provided by Iterator and ListIterator interfaces.

How to Use a Comparator ?

Both TreeSet and TreeMap store elements in a sorted order. However, it is the comparator that defines precisely what sorted order means.

This interface lets us sort a given collection any number of different ways. Also this interface can be used to sort any instances of any class (even classes we cannot modify).

Sr.No.	Iterator Method & Description
1	Using Java Comparator Here is a list of all the methods with examples provided by Comparator Interface.

Summary

The Java collections framework gives the programmer access to prepackaged data structures as well as to algorithms for manipulating them.

A collection is an object that can hold references to other objects. The collection interfaces declare the operations that can be performed on each type of collection.

The classes and interfaces of the collections framework are in package java.util.

Java – Generics

It would be nice if we could write a single sort method that could sort the elements in an Integer array, a String array, or an array of any type that supports ordering.

Java Generic methods and generic classes enable programmers to specify, with a single method declaration, a set of related methods, or with a single class declaration, a set of related types, respectively.

Generics also provide compile-time type safety that allows programmers to catch invalid types at compile time.

Using Java Generic concept, we might write a generic method for sorting an array of objects, then invoke the generic method with Integer arrays, Double arrays, String arrays and so on, to sort the array elements.

Generic Methods

You can write a single generic method declaration that can be called with arguments of different types. Based on the types of the arguments passed to the generic method, the compiler handles each method call appropriately. Following are the rules to define Generic Methods −

• All generic method declarations have a type parameter section delimited by angle brackets (< and >) that precedes the method’s return type ( < E > in the next example).

• Each type parameter section contains one or more type parameters separated by commas. A type parameter, also known as a type variable, is an identifier that specifies a generic type name.

• The type parameters can be used to declare the return type and act as placeholders for the types of the arguments passed to the generic method, which are known as actual type arguments.

• A generic method’s body is declared like that of any other method. Note that type parameters can represent only reference types, not primitive types (like int, double and char).

Example

Following example illustrates how we can print an array of different type using a single Generic method −

publicclassGenericMethodTest{// generic method printArraypublicstatic< E >void printArray( E[] inputArray ){// Display array elementsfor(E element : inputArray){System.out.printf("%s ", element);}System.out.println();}publicstaticvoid main(String args[]){// Create arrays of Integer, Double and CharacterInteger[] intArray ={1,2,3,4,5};Double[] doubleArray ={1.1,2.2,3.3,4.4};Character[] charArray ={'H','E','L','L','O'};System.out.println("Array integerArray contains:");
      printArray(intArray);// pass an Integer arraySystem.out.println("\nArray doubleArray contains:");
      printArray(doubleArray);// pass a Double arraySystem.out.println("\nArray characterArray contains:");
      printArray(charArray);// pass a Character array}}

This will produce the following result −

Output

Array integerArray contains:
1 2 3 4 5 
Array doubleArray contains:
1.1 2.2 3.3 4.4 
Array characterArray contains:
H E L L O

Bounded Type Parameters

There may be times when you’ll want to restrict the kinds of types that are allowed to be passed to a type parameter. For example, a method that operates on numbers might only want to accept instances of Number or its subclasses. This is what bounded type parameters are for.

To declare a bounded type parameter, list the type parameter’s name, followed by the extends keyword, followed by its upper bound.

Example

Following example illustrates how extends is used in a general sense to mean either “extends” (as in classes) or “implements” (as in interfaces). This example is Generic method to return the largest of three Comparable objects −

publicclassMaximumTest{// determines the largest of three Comparable objectspublicstatic<T extendsComparable<T>> T maximum(T x, T y, T z){
      T max = x;// assume x is initially the largestif(y.compareTo(max)>0){
         max = y;// y is the largest so far}if(z.compareTo(max)>0){
         max = z;// z is the largest now                 }return max;// returns the largest object   }publicstaticvoid main(String args[]){System.out.printf("Max of %d, %d and %d is %d\n\n",3,4,5, maximum(3,4,5));System.out.printf("Max of %.1f,%.1f and %.1f is %.1f\n\n",6.6,8.8,7.7, maximum(6.6,8.8,7.7));System.out.printf("Max of %s, %s and %s is %s\n","pear","apple","orange", maximum("pear","apple","orange"));}}

This will produce the following result −

Output

Max of 3, 4 and 5 is 5
Max of 6.6,8.8 and 7.7 is 8.8
Max of pear, apple and orange is pear

Generic Classes

A generic class declaration looks like a non-generic class declaration, except that the class name is followed by a type parameter section.

As with generic methods, the type parameter section of a generic class can have one or more type parameters separated by commas. These classes are known as parameterized classes or parameterized types because they accept one or more parameters.

Example

Following example illustrates how we can define a generic class −

publicclassBox<T>{private T t;publicvoid add(T t){this.t = t;}public T get(){return t;}publicstaticvoid main(String[] args){Box<Integer> integerBox =newBox<Integer>();Box<String> stringBox =newBox<String>();
      integerBox.add(newInteger(10));
      stringBox.add(newString("Hello World"));System.out.printf("Integer Value :%d\n\n", integerBox.get());System.out.printf("String Value :%s\n", stringBox.get());}}

This will produce the following result −

Output

Integer Value :10
String Value :Hello World