Take the 2-minute tour ×

I have a list of randomly generated numbers and want to store them in a structure, then remove them from the structure in the order they were generated.

So, I need a data structure with best remove first.

Both Linked List and Array List has remove of O(1)

Is one better than the other? If so, in what ways?

share|improve this question
Possible duplicate: stackoverflow.com/questions/322715/… –  David Pärsson Dec 9 '12 at 11:23
It sounds like you need a queue. Overall this can be easily found out with Google. -1 –  Nikolay Kuznetsov Dec 9 '12 at 11:26
yeah but those are fore general remove (i.e. cases in the middle). For me, I am only dealing with cases of remove first, O(1) for both which mean it does not matter which one I use. But I was wondering if my thought process is correct –  ealeon Dec 9 '12 at 11:28
Yes. Queue is exactly what I thought of. But I am forbidden to use it. –  ealeon Dec 9 '12 at 11:29
add comment

1 Answer

up vote 6 down vote accepted

In Java, the LinkedList class implements the Queue interface. Which means it works as a queue. If you use .add() you will put things at the end of the list (queue), and if you use .remove(), you will pull things from the head of the list (queue).

Retrieval from an ArrayList is O(1), but removal is not. Consider the following:


Your list al is now {1, 2, 3}.

Now you do: al.remove(0)

After that, al is {2, 3}. But for this to happen, once you removed the head of the list, all other objects after the head needed to shift down one unit. So it was actually O(n). Removal is only O(1) if you are removing the tail. But you need to be removing the head each time.

share|improve this answer
Array List automatically shifts the elements down? So, if i do al.remove(0) twice. it will get rid of 1 and then 2? i thought the index 0 will just be null after the first removal? –  ealeon Dec 9 '12 at 11:40
@ealeon Think about what would happen if it didn't. Your list would become fragmented when you removed elements from the middle. If your list was fragmented, how could you have random access? How would you know the distance from al[0] to al[324] if there were gaps all throughout the array? The defining characteristic of arrays (and ArrayLists) is contiguity. –  The111 Dec 9 '12 at 11:43
hmm okay. i understand –  ealeon Dec 9 '12 at 11:49
@ealeon Please consider accepting the answer if it helped you understand. :-) Thanks. –  The111 Dec 10 '12 at 23:24
add comment

Your Answer


