Array Data StructureIntroductionAn array is an aggregate data structure that is designed to store a group of objects of the same or different types. Arrays can hold primitives as well as references. The array is the most efficient data structure for storing and accessing a sequence of objects. Show
Here is the list of most important array features you must know (i.e. be able to program)
You already know that the Java language has only two data types, primitives and references. Which one is an array? Is it primitive? An array is not a primitive data type - it has a field (and only one), called length. Formally speaking, an array is a reference type, though you cannot find such a class in the Java APIs. Therefore, you deal with arrays as you deal with references. One of the major diffeences between refeences and primituives is that you cannot copy arrays by assigning one to another: int[] a = {9, 5, 4}; int[] b = a; The assignment operator creates an alias to the object, like in the picture below Since these two references a and b refer to the same object, comparing them with the double equal sign "==" will always return true. In the next code example, int [] a = {1,2,3}; int [] b = {1,2,3};a and b refer to two different objects (though with identical contents). Comparing them with the double equal sign will return false. How would you compare two objects with identical contents? In short, using the equals method. For array comparison, the Java APIs provides the Arrays class. The Arrays classThe java.util.Arrays class is a convenience class for various array manipulations, like comparison, searching, printing, sorting and others.
Basically, this class is a set of static methods that are all useful for working with arrays. The code below demonstrates a proper invocation of int[] a = {1,2,3}; int[] b = {1,2,3}; if( Arrays.equals(a, b) ) System.out.println("arrays with identical contents"); Another commonly used method is int[] a = {1,2,3}; System.out.println(Arrays.toString(a)); Here is the example of sorting int[] a = {2,1,3}; Arrays.sort(a); System.out.println(Arrays.toString(a)); Once an array is sorted we use the binary search algorithm for efficient searching int[] a = {2,1,3}; Arrays.sort(a); System.out.println(Arrays.binarySearch(a,2)); In addition to that, the class has other utility methods for supporting operations over multidimensional arrays. Copying arraysThere are four ways to copy arrays
The first way is very well known to you int[] a = {1, 2, 3}; int[] b = new int[a.length]; for(int i = 0; i ‹ a.length; i++) b[i] = a[i]; The next choice is to use int[] a = {1, 2, 3}; int[] b = Arrays.copyOf(a, a.length); The second parameter specifies the length of the new array, which could either less or equal or bigger than the original length. The most efficient copying data between arrays is provided by public static void arraycopy(Object source, int srcIndex, Object destination, int destIndex, int length) The method copies int[] a = {1, 2, 3}; int[] b = new int[a.length]; System.arraycopy(a, 0, b, 0, 3) And the last copying choice is the use of cloning. Cloning involves creating a new array of the same
size and type and copying all the old elements into the new array. The int[] a = {1, 2, 3}; int[] b = (int[]) a.clone(); Note, that casting Examine the code in ArrayCopyPrimitives.java for further details. Insertion and DeletionArrays in Java have no methods
and only one immutable field public char[] delete(char[] data, int pos) { if(pos >= 0 && pos < data.length) { char[] tmp = new char[data.length-1]; System.arraycopy(data, 0, tmp, 0, pos); System.arraycopy(data, pos+1, tmp, pos, data.length-pos-1); return tmp; } else return data; } The first arraycopy copies the elements from index 0 to index pos-1, the second arraycopy copies the elements from index pos+1 to data.length. Examine the code in ArrayDemo.java for further details. The ArrayList classSince the array size is fixed, an array can only hold a certain number of items. In many practical cases, it would be really helpful if we could increase (or descrease) the size of an array on demand. The java.util.ArrayList class supports an idea of a dynamic array - an array that grows and shrinks on demand to accomodate the number of elements in the array. Below is a list of commonly used methods
The following code example will give you a heads up into how some of them are used. /* ADD */ ArrayList<Integer> num = new ArrayList<Integer>(); for(int i = 0; i < 10; i++) num.add(i); System.out.println(num); /* REMOVE even integers */ for(int i = 0; i < num.size(); i++) if(num.get(i)%2 == 0) num.remove(i); System.out.println(num); Resizing policyThe ArrayList implements the doubling-up policy when an array does not have enough capacity for insertion: public void add(int index, Object x)
{
if(index >= 0)
{
ensureCapacity(size + 1);
System.arraycopy(items, index, items, index + 1, size - index);
items[index] = x;
size++;
}
}
private void ensureCapacity( int newCapacity )
{
if( newCapacity >= size )
{
Object[] tmp = new Object[2 * items.length];
System.arraycopy(items, 0, tmp, 0, size);
items = tmp;
}
}
However, the deletion resizing policy in Java is not that efficient. The ArrayList resizes an internal array each time the method remove() is called. Examine the code in ArrayListDemo.java for time comparison between add() and remove() implementations.. Binary SearchAlgorithm (1946): - locate the element x in a sorted array by first comparing x with the middle element and then (if they are not equal) dividing the array into two subarrays; if x is less than the middle element you repeat the whole procedure in the left subarray, otherwise - in the right subarray. The procedure repeats until x is found or subarray is a zero dimension. We assume that the array is sorted in ascending order. Design (Pseudocode) if (size ≤ 0) return -1; else { middle = // find the midpoint; if( x == a[middle] ) // x is a target return x else if (x < a[middle]) search in the area before the midpoint; else search in the area after the midpoint; } Example.Given an array {-23, -2, 5, 8, 23, 44, 78, 99, 101}
Find if 8 belongs to the array. The algorithm is implemented by maintaining three indexes: right = array.length-1; // 8 left = 0; // 0 mid = (right+left)/2; // 4Compare 8 with the middle element at index 4, which is 23. Since 8 < 23, we set right = mid-1; // 3 // 0 left is unchanged mid = (right+left)/2; // 1and start a new iteration. Compare 8 with the middle element, which is -2. Since 8 > -2, we set // 3 right is unchanged left = mid+1; // 2 mid = (right+left)/2; // 2and start a new iteration. Compare 8 with the middle element, which is 5. Since 8 > 5, we set // 3 right is unchanged left = mid+1; // 3 mid = (right+left)/2; // 3and start a new iteration. Compare 8 with the middle element. Bingo! Copying arrays of objectsThis topic is more complex for understanding.. Let us start with a simple loop structure Object[] obj1 = {new Integer(10), new StringBuffer("foobar"), new Double(12.95)}; Object[] obj2 = new Object[obj1.length]; for(int i = 0; i ‹ obj1.length; i++) obj2[i] = obj1[i]; At the first glance we might think that all data is copied. In reality, the internal data is shared between two arrays. The figure below illustrates the inner structure The assignment operator obj1[0] = new Integer(5); and As you see, obj1[0] and obj2[0] now refer to different objects. However, obj1[1] and obj2[1] refer to the same object (which is "foobars"). Since both arrays shares the data, you must be quite careful when you modify your data, because it might lead to unexpected effects. The same behavior will take place again, if we use Multi-dimensional arraysIn many practical application there is a need to use two- or multi-dimensional arrays. A two-dimensional array can be thought of as a table of rows and columns. This creates a table of 2 rows and 4 columns: int[][] ar1 = new int[2][4]; You can create and initialize an array by using nested curcly braces. For example, this creates a table of 3 rows and 2 columns: int[][] ar2 = {{1,2},{3,4},{5,6}}; Generally speaking, a two-dimensional array is not exactly a table - each row in such array can have a different length. Consider this code fragment Object[][] obj = {{new Integer(1),new Integer(2)}, {new Integer(10), "bozo", new Double(1.95)}}; The accompanying picture sheds a bit of light on internal representation From the picture you clearly see that a two-dimensional array in Java is an array of arrays. The array obj has two elements Cloning 2D arraysThe procedure is even more confusing and less expected. Consider the following code segment Object[][] obj = {{new Integer(1),new Integer(2)}, {new Integer(10), "bozo", new Double(1.95)}}; Object[][] twin = (Object[][]) obj.clone(); The procedure of clonig 2d arrays is virtually the same as cloning an array of references. Unfortunately, built-in clone() method does not actualy clone each row, but rather creates references to them Here is a graphical interpretation of the above code Let us change the value of obj[1][1] = "xyz"; This assignment effects the value of Such a copy is called a "shallow" copy. The default behavior of clone() is to return a shallow copy of the object. If we want a "deep" copy instead, we must provide our own implementation by overriding Object's clone() method. The idea of a "deep" copy is simple - it makes a distinct copy of each of the object's fields, recursing through the entire object. A deep copy is thus a completely separate object from the original; changes to it don't affect the original, and vise versa. In relevance to the above code, here is a deep clone graphically Further, making a complete deep copy is not always needed. Consider an array of immutable objects. As we know, immutable objects cannot be modified, allowing clients to share the same instance without interfering with each other. In this case there is no need to clone them, which leads to the following picture Always in this course we will create data structures of immutable objets, therefore implementing the clone method will require copying a structure (a shape) and sharing its internal data. We will discuss these issues later on in the course. Which statement sorts the data array in ascending order?We can sort arrays in ascending order using the sort() method which can be accessed from the Arrays class. The sort() method takes in the array to be sorted as a parameter. To sort an array in descending order, we used the reverseOrder() method provided by the Collections class.
Which one of the following statements is true about passing arrays to a method group of answer choices?Which one of the following statements is true about passing arrays to a method? By default, arrays are passed by reference to a method.
Which of the following method calls will return the number of elements in the ArrayList list?The size() method of java. util. ArrayList class is used to get the number of elements in this list. Returns Value: This method returns the number of elements in this list.
Which code correctly swaps elements in a non empty data array for valid positions J and K?Which code correctly swaps elements in a non-empty data array for valid positions j and k? int t = data[j]; data[j] = data[k];
|