Results 1 to 8 of 8
  1. #1
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default Arrays vs LinkedList When Implementing Stacks

    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):
    Java Code:
    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
    Java Code:
    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;
    	}
    }
    Last edited by Lil_Aziz1; 06-23-2010 at 05:41 AM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  2. #2
    masijade is offline Senior Member
    Join Date
    Jun 2008
    Posts
    2,571
    Rep Power
    9

    Default

    Uhm, why not use the Stack Class?

  3. #3
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Educational purposes I guess.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  4. #4
    Singing Boyo is offline Senior Member
    Join Date
    Mar 2009
    Posts
    552
    Rep Power
    6

    Default

    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...
    If the above doesn't make sense to you, ignore it, but remember it - might be useful!
    And if you just randomly taught yourself to program, well... you're just like me!

  5. #5
    paul pasciak is offline Senior Member
    Join Date
    Jul 2008
    Posts
    125
    Rep Power
    0

    Default Linked List vs Array for stack

    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.

  6. #6
    masijade is offline Senior Member
    Join Date
    Jun 2008
    Posts
    2,571
    Rep Power
    9

    Default

    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).

  7. #7
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    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)
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  8. #8
    masijade is offline Senior Member
    Join Date
    Jun 2008
    Posts
    2,571
    Rep Power
    9

    Default

    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.

Similar Threads

  1. types of stacks
    By vendetta in forum New To Java
    Replies: 3
    Last Post: 02-06-2010, 03:58 AM
  2. Help with stacks
    By Srcee in forum New To Java
    Replies: 5
    Last Post: 11-01-2009, 11:23 AM
  3. 2 stacks, the second keeps mirroring the second??
    By jigglywiggly in forum New To Java
    Replies: 7
    Last Post: 10-11-2009, 07:31 AM
  4. Stacks
    By Zosden in forum Advanced Java
    Replies: 15
    Last Post: 05-05-2008, 08:16 AM
  5. Using Stacks
    By ravian in forum New To Java
    Replies: 7
    Last Post: 11-28-2007, 09:53 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •