Arrays vs LinkedList When Implementing Stacks

[Lil_Aziz1]

I've been reading on Stacks and Queues and I have a question on Stacks that Google answers inconclusively. When implementing a Stack, should one use an array or LinkedList? Some pros and cons that I've researched:

Pros: Arrays
1. O(1) constant time when accessing top element of a stack.

Cons: Arrays
1. Capacity

Pros: LinkedList
1. O(1) constant time when accessing top element of a stack.

Cons: LinkedList
1. Memory for references.

I cannot tell which one is more advantageous for a Stack. I know that Collections Framework uses an array, but if I were to implement my own Stack class, which concept should I use? An array or a LinkedList? I've made one using LinkedList, but if array is the way to go, I'm willing to put time into making it into an array based class (which really should take minutes). Thanks in advance!

Stack (non-generic at the moment):

package stacksAndQueues;
import java.util.EmptyStackException;
import linkedLists.ListNode;

public class Stack {
	
	private ListNode topElement;
	
	public Stack() {
		topElement = null;
	}
	
	public boolean isEmpty() {
		return topElement == null;
	}
	
	public Object peek() {
		if (isEmpty())
			throw new EmptyStackException();
		return topElement.getValue();
	}
	/**
	 * The top element is removed.
	 * @return The top element.
	 */
	public Object pop() {
		if (isEmpty())
			throw new EmptyStackException();
		Object firstElement = topElement.getValue();
		topElement = topElement.getNext();
		return firstElement;
	}
	/**
	 * @param item is added to the top of the stack.
	 */
	public void push(Object item) {
		topElement = new ListNode(item, topElement);
	}
	/**
	 * @param item The item that's being searched for.
	 * @return the distance from the top of the stack 
	 * 		of the occurrence nearest the top of the stack; 
	 * 		the topmost item on the stack is considered to 
	 * 		be at distance 1
	 */
	public int search(Object item) {
		int distance = 0;
		ListNode current;
		for (current = topElement; current != null; current = current.getNext()) {
			distance++;
			if (current.getValue().equals(item))
				break;
		}
		if (current == null)
			return -1;
		return distance;
	}

	public String toString() {
		if (isEmpty())
			return "Empty";
		else {
			String s = "";
			for (ListNode current = topElement; current != null; current = current.getNext())
				s+= current.getValue() + " ";
			return s;
		}
	}
}

linkedLists.ListNode

package linkedLists;

public class ListNode {
	private Object value;
	private ListNode next;
	
	public ListNode(Object value, ListNode next) {
		this.value = value;
		this.next = next;
	}
	
	public Object getValue() {
		return value;
	}
	
	public ListNode getNext() {
		return next;
	}
	
	public void setValue(Object value) {
		this.value = value;
	}
	
	public void setNext(ListNode next) {
		this.next = next;
	}
}

[masijade]

Uhm, why not use the Stack Class?

[Lil_Aziz1]

Educational purposes I guess.

[Singing Boyo]

Its one of unanswerable questions. There's an ArrayList and a LinkedList because they are good for different things. In the same way, an array-based stay may be better or worse than a LinkedList based stack depending on circumstances. Personally, I'd go with the linked-list, as if the stack ever got larger than the array you'd either have a massive reallocation or a crash on your hands...

[paul pasciak]

I would most likely use a linked list.
Its primary advantage is that you can quickly
add a new element and have the stack grow
as your need for that resource expands.

The disadvantage of an array in this aspect
is that you have to spend a lot of time
recreating a larger array if your current
array runs out of space.

Congratulations on a worthy question.
A small population seem to show no interest
or see no value in understanding the basics
of Computer Science.

[masijade]

If you purposely construct the constructor in such a way that a size limit for the stack must be provided, then an array brings a definate performance advantage (if that is a consideration).

[Lil_Aziz1]

paul pasciak, you coulld always rep me. lol jk

Performance advantage is what I'm shooting for. Also, wouldn't knowing the size of a stack be somewhat difficult in practical applications of a Stack?
One more thing, what are the pros of extending the Vector class to a Stack (like the package java.util)? Does it not make Stack inconsistent with its definition because of add(int index, Object o), Object get(int index), and Object remove(int index) defined in the Vector class? (neglecting generics)

[masijade]

ArrayList would be better, unless the synchronisation of the Vector is needed. Besides, just because what you have "under" the stack has "additional" methods, doesn't mean you need to use them. Again, however, if you are going to use a Collections Class, then just use Stack.