Data Structures, Algorithms, & Applications in Java
Chapter 5, Exercise 19
The method dataStructures.ArrayLinearListWithLeftShift.leftShift
is given below.
/** shift elements left by amountOfShift
* @throws IllegalArgumentException when amountOfShift < 0 */
public void leftShift(int amountOfShift)
{
// empty list is easily shifted by any amount
if (size == 0)
return;
// validate shift amount
if (amountOfShift < 0)
throw new IllegalArgumentException("shift amount must be >= 0,"
+ " you have specified " + amountOfShift);
int newSize = 0;
if (amountOfShift < size)
{// at least one element remains
newSize = size - amountOfShift;
System.arraycopy(element, amountOfShift, element, 0, newSize);
}
// set size and replace vacated slots with null
while (size != newSize)
element[--size] = null; // enable garbage collection
}
The complexity is O(size), because the
arrayCopy and the while loop each take
this much time.