Generic Stack (Array and Linked List) Implementation

I am working on brushing up my data-structures knowledge, and was hoping to have my code/thoughts reviewed.

Thoughts on Generic Array Stack:

• Insertion/Pop are amortized to \$\mathcal{O}(1)\$. This is because the stack resizing itself should be a rare enough event that it won't increase the overall time.

• Peek is \$\mathcal{O}(1)\$ since we are directly accessing the value.

• The max size the array can be is Integer.MAX_VALUE - (A number depending on VM). I chose 8 since that seemed to be the safest option.

• I'm not aware of any good way to clone/copy generic items. This means that items pushed onto the stack can have their values changed at any time. Example: Create a new class and push it onto the stack. Modify the original class, and retrieve the item from the stack. It will then have the modified value.

Thoughts on Generic Linked List Stack:

• Insertion/Pop/Peek is \$\mathcal{O}(1)\$.

• There is a small complexity cost with creating all the nodes.

• The size of Linked List can exceed Integer.MAX_VALUE.

• Sequential data access suffers since each node can be located in different parts of the memory.

• Suffers the same issue with generic copying. The data can be changed at any time in the stack.

Interface:

```
package dataStructures;

import java.util.NoSuchElementException;

public interface StackInterface {
/**
* Pushes an element onto the stack and returns this class to allow method chaining.
*
* @param element
* - A generic element to push onto the stack
*/
StackInterface push(T element);

/**
* Removes and returns the last element that was added to the stack.
*
* @return The last element of the stack.
* @throws NoSuchElementException
* is thrown when there are no elements to pop off the stack
*/
T pop() throws NoSuchElementException;

/**
* Returns the last element that was added to the stack.
*
* @return The last element of the stack.
*

Looks good to me, only a few things to note:

public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

You only check if the size exceeds the MAX_ARRAY_SIZE on construction. What happens in private void resizeCapacity(int size) when the new size exceeds the MAX_ARRAY_SIZE or even overflows?

public static final int INITIAL_ARRAY_SIZE = 16;

It's not the initial size, it's the default initial size.

About the tests: You don't test the GenericLinkedStack, do you?


Thoughts on Generic Array Stack:

• Insertion/Pop are amortized to \$\mathcal{O}(1)\$. This is because the stack resizing itself should be a rare enough event that it won't

increase the overall time.


Insertion is \$\mathcal{O}(n)\$ in the worst-case scenario (when it needs to grow) and pop is something like \$\mathcal{O}(n/4)\$ in the worst-case scenarion when shrinking.

Sorry for the short answer, I might add a bit more if something comes to my mind later on, but for the moment I don't see much to comment on.

StackExchange Code Review Q#139737, answer score: 2