[paser]

Im doing a software project, and I would like to use a stack. Ive written two version of a Stack class, one that uses an expanding array and a linked list implementation. My question is, is a linked list the better implementation of a Stack in java? Since im only poping and pushing I have no need for the random access capabilities of an array. I know a linked list uses more memory per reference so im not sure. I will use this stack to hold a large number of alphanumeric values parsed in from a text file. Which makes me think that an array might be better, but im not sure. Also is there a difference in the amount of memory allocated between:

TestObject[] test = new TestObject[10];

and

TestObject[] test = new TestObject[10];

for (int i = 0; i < 10; i++)
	 test[i] = new TestObject();

basically when you create an Array, does it allocate enough memory to hold just the references or both the references and the objects?

[EdwinNameless]

In Java, memory is (usually) not something you really need to worry about, unless you're working on portable devices where memory is paramount, so I'd be tempted to say convenience is pretty much the driver, hence I'd go for a list (probably not linkedlist, but at least array list). If memory is paramount, then yeah go for an array.

Regarding the other question about memory allocated, when you call:

TestObject[] test = new TestObject[10];

you allocate space for the test reference with 10 references to TestObject, all null. But you don't allocate memory for the objects that are going into it until you call the constructor for this object, like in the second example you gave.

Hope this answers your question.

[g00se]

A LinkedList would be better, since it's optimised for pointer-like operations and push and pop are the easiest of those. As you say, you don't need random access, so that would rule out not only arrays, but ArrayList too, since that's backed by an array and in most cases is more expensive to maintain

[paser]

thanks guys, both of you were helpful

[pbl]

paser, on 14 Dec, 2009 - 01:56 PM, said:

basically when you create an Array, does it allocate enough memory to hold just the references or both the references and the objects?

just the reference (4 bytes I presume)

[EdwinNameless]

pbl, on 14 Dec, 2009 - 11:41 PM, said:

just the reference (4 bytes I presume)

Interestingly enough, it is more than that, as the following snapshot shows:



Even an array of size 0 takes 16B:



This confirms the findings of this article (which is a bit of a relief ).

This post has been edited by EdwinNameless: 15 December 2009 - 01:28 AM

[EdwinNameless]

g00se, on 14 Dec, 2009 - 09:47 PM, said:

A LinkedList would be better, since it's optimised for pointer-like operations and push and pop are the easiest of those.

Ok, I have had some time to test this assertion, and to my own surprise, it is actually not true... When implementing a stack with an ArrayList, you pop and push at the end, and adding at the end of an ArrayList does perform faster than a LinkedList.

You can see my findings here... Quite surprising. I guess the overhead of a node creation is greater than the actual array assignment (and the occasional resizing of the internal array).

This post has been edited by EdwinNameless: 15 December 2009 - 04:11 AM