Data Structures in Java

This tutorial will cover the fundamentals of implements the standard varieties of data structures in Java. We’ll give you a basic introduction to the usual suspects-arrays, vectors, hash tables, and stacks-and how to use them in your Java programs.

Array

An Array is a (fixed length) data structures used to store multiple data elements of the same type. The memory allocated to an array is consecutive. All the elements of an array are under one variable name. Its position accesses every data element of an array, and an integer value indicates that position that starts from 0 (zero) called index. The array size is fixed and cannot change at runtime of the program.

Java supports two types of arrays:

• One Dimensional Array
• Multiple Dimensional Array

In Java, arrays can be of either type, primitive data types or references types. In primitive data type array, all elements are of a definite primitive data type. In references type array, all elements are of definite reference type.

Vector

Arrays have a fixed length. They are not suitable for a group of things that grow and shrink over an application’s lifetime. In such situations, Java provides the Vector class, which is available in the standard Java.util package.

A Vector is similar to an array in that it holds multiple objects and can retrieve the stored objects by using an index value. However, the primary difference between an array and a Vector is that it can grow automatically when its initial capacity exceeded. A Vector also provides methods for adding and removing elements that you would normally have to do manually in an array. To sum up, the Vector class represents an ordered collection of objects referenced using indexes and can grow and shrink in size.

At any time, a Vector contains a number of elements that is less than or equal to its capacity. The capacity represents the size of the Vector in memory. After the capacity reached, the Vector must grow before a new element can be added. Its attribute capacity increment represents the amount by which the Vector should grow. If the capacity increment is 0, the array doubles in capacity each time it needs to grow.

The standard Vector class, Java.util.Vector is a parameterized class, i.e. when you create an object of that class, you must supply the underlying type.

BitSets

The Java BitSet class, like arrays and vectors, also allows you to store, manipulate, and retrieve sequential data. This class is different, however, in that it stores sequences of bits. BitSets are useful for storing a collection of Boolean style flags (True or False). Although you can accomplish nearly the same thing with an array or Vector of Boolean types or objects, the BitSet class is more efficient for this job. It collects the bits into bytes for compact storage.

Hash Tables

A hash table is a storage mechanism that creates a key-and-value pair for each element. For example, suppose you are keeping records of employees within a company. You need to develop a mechanism for retrieving these records based on employees’ social security numbers. An array really won’t work well for this because the nine-digit identification number is too large. (Vectors and arrays work best for an ordered list of sequential values.) In this situation, hash tables are the answer.

Hash tables enable quick location and retrieval of data by using a key. This key is associated with data contained within an object. The key and value can be from any object type, but the key object must implement the hashCode() and equals() methods. Once these methods have implemented, the hash table computes a small integer from the key; this is the hash code and the location where the key/value pair exists. Unlike arrays and vectors, the order of values in a hash table is not important-the hash code ID is all that matters. What is important is that the keys are unique: Only one value can be stored for each key. If you add a value to a key that is already holding another value, then the added value will replace the preexisting value.

As with other data structures, the hash table’s performance is affected by the ratio between the number of elements and the structure’s capacity. This ratio is called the load factor and represented as a percentage. Hash tables need to allocate more storage space than is needed because they generate the special hash code from the identifying key. As the load factor increases, so does the likelihood that two or more generated hash codes will
have the same value; this is called a collision. The extra space used to ensure that all key/value pairs remain unique. Ideally, the load factor is not higher than 50%; that is, the capacity should double the number of elements in the hash table. If the load factor goes over 75%, the hash table will automatically double the capacity to ensure adequate performance.

Stacks

A stack is a mechanism for building what’s called a “last in, first out” structure, Think of this as a virtual Pez candy dispenser; each piece of candy is a data element. (For those who are a little more ferocious, another analogy for a stack is a clip for a handgun.) The last element added is also the first one to come out. A stack can use as an easy instrument for reversing the order of a sequence of data.