There are many methods in the java.util.ArrayList class in Java. But, two of the overloaded methods set and add at index, are quite interesting. I am writing this post just to tell you a small gotcha of the methods.

ArrayList Class

There a two add methods

1. add(E e)

    This basically adds the element to the ArrayList. Since the ArrayList is dynamic, it automatically increases the size of the ArrayList by 1, and adds the new element to the index.

2. add(int index, E e)

    This is a little confusing because it shifts all the elements after the element has been added to the specified index. Let's say, you have an ArrayList with elements [1, 2, 3, 4] and the size is 4. If you try to add a new element 10 to index 2 where we have element 3 already, it won't replace element 3 with 10, but rather it will add 10 at index 2, and shifts all the remaining elements from 3 onwards to the right of the ArrayList. So, the resulting Arraylist looks something like this:

[1, 2, 10, 3, 4] and the size becomes 5

3. set(int index, E e)

    As the name suggests, the set replaces the existing element in the index with the element that you want to add. So, for the ArrayList [1, 2, 3, 4] with size 4 after set(2, 10) becomes

[1, 2, 10, 4] and the size remains 4

References:

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

Operations

The operation we require are:

1. push() - pushes an item onto the stack

2. pop() - removes an item from the stack

3. isEmpty() - checks if the stack is empty or not.

Implementation using Linked List

The stack's implementation using Linked List is quite straight forward. We need to maintain a pointer to the first element of the linked list and we shall insert/remove the elements from the first element. We shall have an inner class Node that this model class/entity for an actual node/item. 

private class Node  { 

      String item; 

      Node next; 

}     

The item is the actual data which is a String in this example. You can also have any other type of data that you want. The next variable is used to maintain the link to the next Node of the item. In the case of the last element, the next will always be null.

Push

Pushing a new element/item will always be from the beginning of the list. For this, we need to save the first element temporarily into oldFirst. Since we are adding a new Node, we need to create a new node and assign it to the first element. The item to be inserted will also go in the item variable of the first. Finally, the previous first element that we save in oldFirst will be pointed by first.  

public void push(String item) { 

      Node oldfirst = first; 

      first = new Node(); 

      first.item = item; 

      first.next = oldfirst; 

}

Pop

Poping or removing an element/item from the stack is also from the beginning of the list. First, we save the item to be removed which will be returned at the last. The first node now points to the node which was its next node. The element/item is then returned.

public String pop() { 

       String item = first.item; 

       first = first.next; 

       return item; 

}

 

Implementation using Array

The arrays implementation uses an array S to store N items. We push items to the array at S[N] position and pop an item from S[N-1] position. We can handle the underflow of an array by throwing an exception when a pop operation is done on an empty array and overflow by resizing the array when we have crossed the size of the array. We can also add null items so that on the pop operation we can free the space.

Strategies to Grow and Shrink the Array

We can always ask the client who will be using the Stack API to provide the size which is not a good idea because a client should not be caring about all these. We can increase or decrease the size of the array on push and pop, but this will also be very expensive. Think of a scenario where we are doing push-pop-push-pop-push. Here the strategy of increase or decrease the size by 1 will be very expensive. Hence we need to ensure that the array resizing happens as infrequent as possible.

     When the array becomes full, we can create an array double the size of the array and copy all the items to it. Similarly, we can also halve the size of the array when it is quarter full. The question obviously will be why not halve the size of an array when it is half full, why quarter full? Consider the same scenario above of push-pop-push-pop-push ... when the array is full and each operation takes time proportional to N which can be too expensive. 

Resizing

We can create an array of size 1.

 public Stack() { 

      s = new String[1]; 

} 

For, resizing the array we shall have a method which does what we have discussed above:

private void resize(int capacity) { 

       String[] copy = new String[capacity]; 

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

             copy[i] = s[i]; 

       s = copy; 

}

  Push

Pop

Tradeoffs between both the approaches