Loopy Problem - III

Provide a declaration for i that turns this loop into an infinite loop:

while (i != i + 0) {

}

The inescapable conclusion is that the type of i must be non-numeric, and therein lies the solution. The only non-numeric type for which the + operator is defined is String. The + operator is overloaded: For the String type, it performs not addition but string concatenation. If one operand in the concatenation is of some type other than String, that operand is converted to a string prior to concatenation

Loopy Problem - II

The following program counts the number of iterations of a loop and prints the count when the loop terminates. What does it print?

public class InTheLoop {

public static final int END = Integer.MAX_VALUE;

public static final int START = END - 100;

public static void main(String[] args) {

int count = 0;

for (int i = START; i <= END; i++)

count++;

System.out.println(count);

}

}

If you don't look at the program very carefully, you might think that it prints 100; after all, END is 100 more than START. If you look a bit more carefully, you will see that the program doesn't use the typical loop idiom. Most loops continue as long as the loop index is less than the end value, but this one continues as long as the index is less than or equal to the end value. So it prints 101, right? Well, no. If you ran the program, you found that it prints nothing at all. Worse, it keeps running until you kill it. It never gets a chance to print count, because it's stuck in an infinite loop.

The problem is that the loop continues as long as the loop index (i) is less than or equal to Integer.MAX_VALUE, but all int variables are always less than or equal to Integer.MAX_VALUE. It is, after all, defined to be the highest int value in existence. When i gets to Integer.MAX_VALUE and is incremented, it silently wraps around to Integer.MIN_VALUE.

If you need a loop that iterates near the boundaries of the int values, you are better off using a long variable as the loop index. Simply changing the type of the loop index from int to long solves the problem, causing the program to print 101 as expected:

for (long i = START; i <= END; i++)

More generally, the lesson here is that ints are not integers. Whenever you use an integral type, be aware of the boundary conditions. What happens if the value underflows or overflows? Often it is best to use a larger type. (The integral types are byte, char, short, int, and long.)

Loopy Problem - I

This program increments a variable repeatedly and then prints its value. What is it?

public class Increment {

public static void main(String[] args) {

int j = 0;

for (int i = 0; i < 100; i++)

j = j++;

System.out.println(j);

}

}

At first glance, the program might appear to print 100. After all, it does increment j 100 times. Perhaps surprisingly, it does not print 100 but 0. All that incrementing gets us nowhere. Why?

When placed after a variable, the ++ operator functions as the postfix increment operator [JLS 15.14.2]: The value of the expression j++ is the original value of j before it was incremented. Therefore, the preceding assignment first saves the value of j, then sets j to its value plus 1, and, finally, resets j back to its original value. In other words, the assignment is equivalent to this sequence of statements:

int tmp = j;

j = j + 1;

j = tmp;

The program repeats this process 100 times, after which the value of j is exactly what it was before the loop, or 0.

Fixing the program is as simple as removing the extraneous assignment from the loop, leaving:

for (int i = 0; i < 100; i++)

j++;

What is ArrayStoreException

An interesting situation occurs when you assign a subclass one-dimensional array variable's reference to a superclass one-dimensional array variable, because a one-dimensional array subtype is a kind of one-dimensional array supertype. If you then try to assign a superclass object reference to one of the subclass one-dimensional array's elements, anArrayStoreException object is thrown. The following code fragment demonstrates

AlarmClock [] ac = new AlarmClock [1];

Clock [] c = ac;

c [0] = new Clock ();

The compiler compiles the code fragment above because each line is legal. At runtime, however, c [0] = new Clock (); results in an ArrayStoreException. That exception occurs because we might try to access an AlarmClock-specific member via a reference to a Clock object. For example, suppose AlarmClock contains a public void soundAlarm() method, Clock lacks that method, and the code fragment above executes without throwing anArrayStoreException object. An attempt to execute ac [0].soundAlarm (); crashes the JVM because we attempt to execute that method in the context of a Clock object (which doesn't incorporate a soundAlarm() method).

ArrayList vs LinkedList

Source

The first thing to do while differentiating the two is to look at what interfaces these two implement. This might hint us at their purpose, as Sun usually bound purposes into interfaces.


// lang java
public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

public class LinkedList
extends AbstractSequentialList
implements List, Queue, Cloneable, Serializable
We can ignore Cloneable and Serializable as all of the JCF implement those. It’s also quite obvious that both of them implement the List interface, as they need to provide list functionability (backwards iteration, sub listing, etc).

Now for the differences: ArrayList is implementing RandomAccess while LinkedList implementing Queue. You could already tell something about the usage of the two classes.

ArrayList

Now for some implementation notes. The ArrayList is actually encapsulating an actualy Array, an Object[]. When you instanciate ArrayList, an array is created, and when you add values into it, the array changes its size accordingly. This gives you strengths and weaknesses:

Fast Random Access
You can perform random access without fearing for performence. Calling get(int) will just access the underlying array.

Adding values might be slow When you don’t know the amount of values the array will contain when you create it, a lot of shifting is going to be done in the memory space when the ArrayList manipulates its internal array.
Slow manipulation When you’ll want to add a value randomly inside the array, between two already existing values, the array will have to start moving all the values one spot to the right in order to let that happen.
LinkedList

The LinkedList is implemented using nodes linked to each other. Each node contains a previous node link, next node link, and value, which contains the actual data. When new data is inserted, a node is inserted and the links of the surrounding nodes are updated accordingly. When one is removed, the same happens – The surrounding nodes are changing their links and the deleted node is garbage collected. This, as well, gives strengths and weaknesses:

Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantanious. Change two links, and you have a new value anywhere you want it.
No random access Even though the get(int) is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.
Some Conclusions

ArrayList is very useful when a well defined set of data is needed in a List interface as opposed to an array. It can be dynamically changed, but try not to do so frequently throughout the life of the application. LinkedList is there for you to do just that: Manipulating it is very easy, and as long as its used for iteration purposes only and not for random accessing, it’s the best solution. Further, if you need random accessing from time to time, I suggest toArray for that specific moment.

Another point I didn’t raise here is the Queue issue. LinkedList implements extended abilities to the normal List interface which allows it to add and remove elements from its beginning and end. This makes the LinkedList perfect for Queue and Stack purposes – Although in Java 5 they already added a Stack class.