Collections - Arrays
Array
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
Array is basically an object. It does not belong to the collections framework in Java.
An array is a container object that holds a fixed number of values of a single type. The length of an array is established when the array is created. After creation, its length is fixed.
Arrays are linear data structures providing functionality to add elements in a continuous manner in memory address space.
Each element’s position is uniquely designated by an integer. The elements are accessed by it’s numerical index.
Declaring arrays
byte[] anArrayOfBytes;
short[] anArrayOfShorts;
long[] anArrayOfLongs;
float[] anArrayOfFloats;
double[] anArrayOfDoubles;
boolean[] anArrayOfBooleans;
char[] anArrayOfChars;
String[] anArrayOfStrings;
Creating, Initializing, and Accessing an Array
int[] anArray = new int[10];
anArray[0] = 100;
anArray[1] = 200;
anArray[2] = 300;
or
int[] anArray = {
100, 200, 300,
400, 500, 600,
700, 800, 900, 1000
}
Multi dimensional arrays
public class TwoDimArrayDemo {
public static void main(String[] args) {
String[][] names = {
{"Mr. ", "Mrs. ", "Ms. "},
{"Smith", "Jones"}
};
System.out.println(names.length);
// 2
for (int i = 0; i < names.length; i++) {
System.out.println(names[i][0] + names[i][1]);
}
// Mr. Mrs.
// SmithJones
System.out.println(names[0][0] + names[1][0]);
// Mr. Smith
System.out.println(names[0][1] + names[1][0]);
// Mrs. Smith
System.out.println(names[0][2] + names[1][1]);
// Ms. Jones
}
}
In the array, memory allocation depends whether the array is of primitive type or object type. In the case of primitive types, actual values are contiguous locations, but in the case of objects, allocation is similar to ArrayList.
Obtain Array from ArrayList
Array can be obtained from an ArrayList using toArray() method on ArrayList.
List arrayList = new ArrayList();
arrayList.add("abc");
Object a[] = arrayList.toArray();
How does array resizing work?
Array variables (references) are reusable; to change the length of an array, we can create a new array of the desired length and assign it to the original array variable.
int arrayOfInt[] = new int[7];
String arrayOfString[] = new String[4];
In the preceding declarations, arrayOfInt is an array of seven int values. Because int is a primitive type, there is no need to allocate any additional space after the new call. The array already is assigned enough contiguous memory to hold seven ints.
The arrayOfString allocation call is a little different. The new operator assigns enough contiguous memory for the handles to four Strings; it does not allocate the memory for the String objects themselves. The String memory must be created separately, as shown in this code:
int arrayOfInt[] = new int[7];
String arrayOfString[] = new String[4];
for( int i = 0; i < 7; i++ )
{
arrayOfInt[i] = i;
}
arrayOfString[0] = new String("Hello");
arrayOfString[1] = new String("World");
arrayOfString[2] = new String("It's");
arrayOfString[3] = "Me";
The final statement is an implicit call to the following:
arrayOfString[3] = new String("Me");
TODO For details about memory allocation and management, see Vectors/Notes.md
Array resizing:
Choosing an array to represent the stack contents implies that clients must estimate the maximum size of the stack ahead of time. In Java, we cannot change the size of an array once created, so the stack always uses space proportional to that maximum. A client that chooses a large capacity risks wasting a large amount of memory at times when the collection is empty or nearly empty. For example, a transaction system might involve billions of items and thousands of collections of them. Such a client would have to allow for the possibility that each of those collections could hold all of those items, even though a typical constraint in such systems is that each item can appear in only one collection. Moreover, every client risks overflow if the collection grows larger than the array. For this reason, push() needs code to test for a full stack, and we should have an isFull() method in the API to allow clients to test for that condition. We omit that code, because our desire is to relieve the client from having to deal with the concept of a full stack, as articulated in our original Stack API. Instead, we modify the array implementation to dynamically adjust the size of the array a[] so that it is both sufficiently large to hold all of the items and not so large as to waste an excessive amount of space. Achieving these goals turns out to be remarkably easy. First, we implement a method that moves a stack into an array of a different size:
see resize() in ArrayResizing.java
Now, in push() , we check whether the array is too small. In particular, we check whether there is room for the new item in the array by checking whether the stack size N is equal to the array size a.length. If there is no room, we double the size of the array. Then we simply insert the new item with the code a[N++] = item , as before:
see push() in ArrayResizing.java
Similarly, in pop() , we begin by deleting the item, then we halve the array size if it is too large. If you think a bit about the situation, you will see that the appropriate test is whether the stack size is less than one-fourth the array size. After the array is halved, it will be about half full and can accommodate a substantial number of push() and pop() operations before having to change the size of the array again.
see pop() in ArrayResizing.java
With this implementation, the stack never overflows and never becomes less than one-quarter full (unless the stack is empty, when the array size is 1). We will address the performance analysis of this approach in more detail later.
REMEMBER : Loitering: Java’s garbage collection policy is to reclaim the memory associated with any objects that can no longer be accessed. In our pop() implementations, the reference to the popped item remains in the array. The item is effectively an orphan—it will be never be accessed again— but the Java garbage collector has no way to know this until it is overwritten. Even when the client is done with the item, the reference in the array may keep it alive. This condition (holding a reference to an item that is no longer needed) is known as loitering. In this case, loitering is easy to avoid, by setting the array entry corresponding to the popped item to null , thus overwriting the unused reference and making it possible for the system to reclaim the memory associated with the popped item when the client is finished with it.
Generic Array Creation is disallowed in Java
When implementing FixedCapacityStack, we do not know the actual type of Item, but a client can use our stack for any type of data by providing a concrete type when the stack is created. Concrete types must be reference types, but clients can depend on autoboxing to convert primitive types to their corresponding wrapper types. Java uses the type parameter Item to check for type mismatch errors - even though no concrete type is yet known, variables of type Item must be assigned values of type Item, and so forth. But there is one significant hitch in this story: We would like to implement the constructor in FixedCapacityStack with the code
a = new Item[cap];
which calls for creation of a generic array. For historical and technical reasons beyond our scope, generic array creation is disallowed in Java. Instead, we need to use a cast:
a = (Item[]) new Object[cap];
This code produces the desired effect (though the Java compiler gives a warning, which we can safely ignore), and we use this idiom throughout the book (the Java system li- brary implementations of similar abstract data types use the same idiom).
Q. Why does Java disallow generic arrays? A. Experts still debate this point. You might need to become one to understand it! For starters, learn about covariant arrays and type erasure.
// TODO find out more about this.