Contents |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Data structures are used to store and retrieve large, unpredictable amounts of data. One can prioritize ease of storage or speed of retrieval. Furthermore, the various solutions differ in their storage requirements. Therefore, it is important to consider the following:
So far, we've only learned about arrays. Arrays allow you to store a predefined number of data points. If this number is exceeded, the entire array must be rewritten. Arrays cannot be enlarged later. Accessing the array requires searching through its entire contents. Therefore, storage is fast, access is slow, and there is no flexibility whatsoever. The storage requirement depends on the fixed upper limit.
Threads will be discussed in a later chapter.
An array can also hold arbitrary data. This is achieved by ensuring that the objects stored in the array are either instances of classes or arrays themselves, and that the array is declared as an array of type Object . All classes in Java are derived from Object .
Furthermore, for the built-in data types, such as `int` and `double` , there are wrapper classes that can hold such data, like `Integer` and `Double` . These wrapper classes also offer useful additional functions. However, you can no longer perform calculations directly with the data wrapped in this way. For that, you have to convert it back into its elementary formats. From Java 1.5 onwards, Java does this automatically.
public class Test
{
public static void main (String args[])
{
Object A[] = new Object[6];
// Enter various things:
A[0] = Integer.valueOf(4); // int
A[1] = Double.valueOf(4.5); // double
A[2] = new Test(); // Instance of Test
int K[] = new int[2];
K[0] = 1;
K[1] = 2;
A[3] = K; // an array of int
A[4] = A; // A itself
A[5] = "Test"; // a string
// Spend them again:
System.out.println(((Integer) A[0]).intValue() + 2);
System.out.println((Double) A[1]);
System.out.println((Test) A[2]);
System.out.println(((int[]) A[3])[1]);
System.out.println(((Object[]) A[4]).length);
System.out.println((String) A[5]);
}
/**
* This allows you to print an instance of Test using System.out.println().
*/
public String toString()
{
return "Instance of Test";
}
}
In this example, an array of 6 objects is declared, and we store various items in this array and then output it. Note that the object must be converted to the appropriate type each time if you want to ensure that the compiler recognizes it as more than just an Object .
We want to perform calculations with the value of the integer . Therefore, we use the `intValue()` method of `Integer` to retrieve its value. The value of a `Double` can be directly output because `Double` has a `toString()` method . We have also provided for this in our `Test` class by including a `toString` method there.
A[3] contains (points to) a complete array. The type conversion looks a bit strange, but it works. Afterwards, you can index the array as usual. Note the parentheses! The type conversion always applies to the entire expression it precedes.
A[4] points directly to A itself. This is perfectly possible. After converting to Object[], the length of this array can be determined.
The output of this program is now
6 4.5 instance of test 2 6 test
Incidentally, if you make a mistake when converting the object by converting to the wrong data type, you will get an IllegalTypeCastException .
The Vector class functions like an array that grows as needed. The class is declared in java.util and must first be imported.
import java.util.*;
After that, a vector can be declared as follows.
Vector v = new Vector();
The constructor also accepts a minimum size, which ensures that the vector doesn't need to be extended again immediately. What can be stored on the vector? Naturally, all objects, which are all of type Object , and also arrays. The `addElement()` method , used for storing elements, therefore also accepts an Object as a parameter.
Vectors are typically used to store homogeneous data. However, this is not necessarily the case, as the following example shows, which stores data of different types on a single vector.
import java.util.*;
public class Test
{
static public void main (String args[])
{
Vector v = new Vector();
// Store string:
v.addElement("Test");
// Store integers:
v.addElement(Integer.valueOf(2));
// Store double array
v.addElement(new double[100]);
// Read:
System.out.println((String) v.elementAt(0));
// prints: Test
System.out.println((Integer) v.elementAt(1));
// prints: 2
System.out.println(((double[]) v.elementAt(2)).length);
// prints: 100
}
}
This type of object vector is unsafe, however, because it constantly requires correct conversion to the appropriate data type and generates warnings. We will learn below how to specify the data type that is actually stored in the vector.
There are several other classes that can contain data. We will demonstrate the Java implementation of List as an example. The LinkedList class we use here is a special implementation of the general List class . Collections can be found in the java.util package .
import java.util.*;
public class Test
{
static public void main (String args[])
{
// List structure:
LinkedList L = new LinkedList();
for (int i = 1; i <= 10; i++)
L.add(new Integer(i));
// First pass of the list:
System.out.println("First pass:");
Iterator I = L.iterator();
while (I.hasNext())
{
int i = ((Integer) I.next()).intValue();
System.out.println(i);
if (i == 5)
I.remove(); // Remove all 5s
}
// Second pass of the list:
System.out.println("Second pass:");
I = L.iterator();
while (I.hasNext())
{
int i = ((Integer) I.next()).intValue();
System.out.println(i);
}
}
}
The code above builds a list of the numbers 1 to 10, outputs the list again, removing the 5, and outputs the list a second time, this time of course without the 5.
For output, we use an iterator , an interface that can be obtained with the `iterator()` function . It functions similarly to an enumeration and has only three methods: `hasNext()` , ` next()` , and `remove()` . The meaning of the first two methods should be clear. `remove()` is a safe way to remove the currently retrieved element from the collection.
We will modernize this example shortly.
The disadvantage of this class Vector , and also of the class just presented, LinkedListis that the compiler cannot ensure that only data of that type Integer
is actually stored in the list.
This changes, however, with the introduction of generic classes. Such classes are templates for other classes that depend on a specific data type. Only when the concrete instance of the class is created is it determined which data type the class should work with.
As an example, we will use the class LinkedList, which is such a generic class, for the data type Integer. The data type is appended to the class name in square brackets.
import java.util.*;
public class Test
{
static public void main (String args[])
{
// List structure:
LinkedList<Integer> L = new LinkedList<Integer>();
for (int i = 1; i <= 10; i++)
L.add(Integer.valueOf(i));
// First pass of the list:
System.out.println("First pass:");
for (Integer I : L)
System.out.println(I.intValue());
L.remove(Integer.valueOf(5));
// Second pass of the list:
System.out.println("Second pass:");
for (Integer I : L)
System.out.println(I.intValue());
}
}
That looks significantly sleeker and safer.
add()It now only works with objects of type
Integer.Integer.remove()apply this to the list. For comparison, we equals()use this method. All objects have this method, and Integerthe values are compared.Incidentally, iterators can also be used as generic classes. In our example, it looks like this.
Iterator<Integer> I=L.iterator();
The iterator then automatically returns objects of type Integer, and a type conversion is no longer necessary. This gives the compiler control over potential misuse of the list.
It is also possible to use an automatic type conversion from integer to int .
for (int i : L) System.out.println(i);
Since automatic conversion is an unclear concept, I personally advise against it. One could try including the code for removing the 5s in the loop.
for (int i : L)
{
System.out.println(i);
if (i==5) L.remove(i); // Remove all 5s
}
However, this doesn't work because `remove()` is not allowed within the loop for a list. Furthermore, the iterator itself is not accessible to use its `remove` method.
We've learned how to use generic data types. But how do you write your own generic data types?
To understand this, we create a class called Memory that can only store one object.
class Tier
{
String name ()
{
return "Tier";
}
}
class Monkey extends Animal
{
String name ()
{
return "Affe";
}
}
class dog extends animal
{
String name ()
{
return "dog";
}
}
class Memory<Class extends Animal>
{
Class K;
void put (Class k)
{
K = k;
}
class get()
{
return K;
}
}
public class Test
{
static public void main (String args[])
{
Memory<Monkey> monkey = new Memory<Monkey>();
affe.put(new Affe());
System.out.println(monkey.get().name());
}
}
The name `Class` within the `Memory` class represents any class. However, it is specified that this class must be a child of the ` Animal` class in the specific application. Therefore, if an object of the class `Memory<Monkey>` is created in the main program , the `Memory` class is used, where ` Class` is replaced by `Monkey` . In principle, a class of the form `Memory<Monkey>` is simply used.
class storage
{
Monkey K;
void put (Affe k)
{
K = k;
}
Monkey get ()
{
return K;
}
}
generated. This is actually quite easy to understand.
General classes like LinkedList do not use `extends` . The classes look something like this.
public interface List <class>
{
void add (Class x);
Iterator<Class> iterator();
}
public interface Iterator <class>
{
class next();
boolean hasNext();
}
They are implemented here as an interface , which is what they are in reality. In this case, the specified class can be any child of Object .
What can you do when passing lists of unknown types to a function, such as a list of monkeys or, alternatively, a list of dogs? In this case, you use wildcards . The following example should clarify the construction.
public class Test
{
static public void print (List<? extends Tier> k)
{
for (Tier e : k)
{
System.out.println(e.name());
}
}
static public void main (String args[])
{
List<Monkey> l = new LinkedList<Monkey>();
l.add(new Monkey());
l.add(new Monkey());
print(l);
}
}
The generic version of Vector is called ArrayList . This class works essentially the same way, but it is type-safe. This means that the compiler already knows the type of the data it contains. We will construct an example of this in the exercises.
Hashtables are an example of an advanced and useful concept. They are used to store data using a key, which can then be used to retrieve it later. The key can be any object that has a ` hashCode()` method. Most often, however, a simple string is used.
Hashtables store objects in an array under an index derived from the hash code of the key . Naturally, any collisions must be resolved, for which various strategies exist. While the internal workings of Java's hashtables can be studied in the Java source code, this is essentially unknown to the user.
Hashtables store data quickly and retrieve it very quickly. In this respect, they are far superior to arrays. They are also very flexible in terms of size, but become increasingly inefficient as they fill up due to the increasing number of collisions.
The following example illustrates storing and retrieving objects in a hashtable. We use the type-safe method, where the data types for the key and value must be specified. Generic classes can also depend on two data types, in which case both must be specified.
import java.util.*;
public class Test
{
public static void main (String args[])
{
Hashtable<String, String> H = new Hashtable<String, String>();
H.put("eins", "one");
H.put("two", "two");
H.put("three", "three");
System.out.println(H.get("two")); // prints: two
System.out.println(H.get("four")); // prints: null
}
}
Therefore, if a key is not found, get() returns the value null .
Hashtables are therefore suitable for dictionaries or property lists. They are very efficient for both accessing and storing data.
Since Java already includes a very large number of data structures, it's usually unnecessary to reinvent the wheel. However, anyone who wants to program more complex structures themselves needs to understand how to organize data in memory.
For study purposes, we only provide the listing of sorted binary trees here. A tree consists of nodes, each with two children, which are themselves trees (or null ). The node contains a string . All nodes in the left child tree contain an alphabetically smaller string, and all nodes in the right child tree contain an alphabetically larger string.
We create such a tree and output the contents in a sorted order.
class StringNode
{
private String S;
protected StringNode Left, Right;
public StringNode(String s)
{
Left = Right = null;
S = s;
}
public void insert (String s) // Insert s correctly.
{
if (s.compareTo(S) > 0) // then right
{
if (Right == null)
Right = new StringNode(s);
else
Right.insert(s);
} else // otherwise left
{
if (Left == null)
Left = new StringNode(s);
else
Left.insert(s);
}
}
public String getString()
{
return S;
}
public StringNode getLeft()
{
return Left;
}
public StringNode getRight()
{
return Right;
}
}
public class Test
{
public static void main (String args[])
{
StringNode tree = null;
for (int i = 0; i < 20; i++) // store 20 random strings
{
String s = "Random number " + Math.random();
if (tree == null)
tree = new StringNode(s);
else
tree.insert(s);
}
print(tree); // Print again in sorted order
}
public static void print (StringNode tree)
// Recursive print function
{
if (tree == null)
return;
print(tree.getLeft());
System.out.println(tree.getString());
print(tree.getRight());
}
}
Some remarks
TreeSetthat does exactly what our trees can do, and more.
In Java, if you wanted to write functions that could accept a variable number of arguments, you previously had to use an array to hold those arguments. From Java 1.5 onwards, this is no longer necessary. We can now write a function that adds any number of numbers.
public class Test
{
static public int add (int...I)
{
int sum = 0;
for (int i : I)
sum += i;
return sum;
}
static public void main (String args[])
{
System.out.println(add(4, 5, 3, 5));
}
}
In principle, the variable argument list is an array and therefore a collection. This means that you can actually access I[0] etc. within the function. We have used the new for loop here.
The variable argument list is indicated by the three dots " ... ". It can only be the last argument of the function.
There's a useful function we haven't discussed yet that also works with a variable argument list. It's possible to embed formatted variables in text using the `MessageFormat.format()` function (in the `java.text` package ). To do this, you first pass a format string and then the variables in a variable argument list.
The format string contains elements of the form {variable number, format type, format style}, where the last two elements can be omitted. The format type can be number , date , time , or choice . The format style depends on the type. For numbers, specifying the digits in the form #.#### is particularly useful. For integer numbers , simply use integer . For more complex formatting options, refer to the documentation.
import java.text.MessageFormat;
import java.util.Date;
public class Test
{
static public void main (String args[])
{
System.out.println(
MessageFormat.format(
"Today is {0,date}. Pi to 10 decimal places is {1,number,#.##########}."
new Date(), Math.PI));
}
}
The following program rewrites the previously described merge sort for arbitrary Comparable . Interestingly, it uses the generic data type `Type` by specifying in the header that this data type extends a Comparable —specifically, one that can compare with `Type` . The keyword here is `extends`.
class MergeSorter<Type extends Comparable<Type>>
{
// needed as working space
Type[] work;
public void sort (Type[] array)
{
if (array.length < 2)
return;
// easiest way to create a work area is cloning
work = array.clone();
// call recursive sort
sort(array, 0, array.length - 1);
}
void sort (Type[] array, int start, int end)
{
// System.out.println(start + "-" + end);
// half point, can be equal to start or end.
int half = (start + end) / 2;
if (half - start > 0) // need to sort first half
sort(array, start, half);
if (end - (half + 1) > 0) // need to sort second half
sort(array, half + 1, end);
// merge sorted parts
merge(array, start, half, half + 1, end);
}
void merge (Type[] array, int start1, int end1, int start2, int end2)
{
// aim index to copy into work
int aim = start1;
// remember start index, because we are changing start1
int start = start1;
// Loop breaks if one merge part is exceeded
while (true)
{
if (array[start1].compareTo(array[start2]) < 0)
{
work[aim++] = array[start1++];
if (start1 > end1) // first part is exceeded
{
while (start2 <= end2)
work[aim++] = array[start2++];
break;
}
}
else
{
work[aim++] = array[start2++];
if (start2 > end2) // second part is exceeded
{
while (start1 <= end1)
work[aim++] = array[start1++];
break;
}
}
}
System.arraycopy(work, start, array, start, aim - start);
}
}
public class Test
{
public static void main (String args[]) throws Exception
{
int N = 10000000;
String[] array = new String[N];
for (int i = 0; i < N; i++)
array[i] = "String " + Math.random();
MergeSorter<String> sorter = new MergeSorter<String>();
long time = System.currentTimeMillis();
sorter.sort(array);
// Arrays.sort(array);
System.out.println((System.currentTimeMillis() - time) + " msec");
for (int i = 0; i < N - 1; i++)
if (array[i].compareTo(array[i + 1]) > 0)
throw new Exception("Error in Sort");
}
}
One problem with generic classes in Java is that arrays of generic types cannot be created easily. The following method will not work because Java implements generic classes in a special way.
work = new Type[array.length];
One simple solution is to create the required arrays in the calling program and pass them to the constructor or a function call. However, in our case, we can simply clone the argument, since `work` should have the same length as the array we are sorting.
A more complex solution uses reflection . For this, the class whose array we want to create must be known. This is the case here, since we are passing an array of this class (String). Because we are converting the result to Type[] without checking , a warning is generated, which we suppress. The call looks simply like this.
@SuppressWarnings("unchecked")
public void sort (Type[] array)
{
if (array.length < 2)
return;
// reflection way to generate an array of a generic class
work = (Type[]) java.lang.reflect.Array.newInstance(array[0].getClass(),
array.length);
// call recursive sort
sort(array, 0, array.length - 1);
}
ArrayList
and write an example where you
ArrayListstore 1000 random numbers in a `R` block and then forcalculate the mean using a `for` loop. Remove Iteratorall values less than 0.5 using a `R` block and output how many values remain.LinkedListwith 1000 random numbers, one empty one ArrayList, and add all elements of the LinkedList
one ArrayListto addAll()the other.TreeSetand rewrite our tree example using this class.