12 Replies Latest reply: Jun 15, 2010 3:22 AM by YoungWinston

Hello All,

Could you share any analysis done on the Vector/ArrayList/LinkedList performance while editing/adding the intermediate elements?

I found through some site saying it is contstant time ie., (O(1)) for adding a element at ends.

Where as for the intermediate elements it is O(n-i) for Vector/ArrayList. This is constant time for LinkedList.
n - is the number of elements
i - is the index of the element

Please correct me if i am wrong?

Thanks
Mohamed Javeed
• ###### 1. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Mohamed_Javeed wrote:
I found through some site saying it is contstant time ie., (O(1)) for adding a element at ends.
Yes, except when the internal array needs to be resized for ArrayList (Vector is deprecated so forget about it).
Where as for the intermediate elements it is O(n-i) for Vector/ArrayList.
It's just O(n). There is no O(n-i) notation. You should know that.
This is constant time for LinkedList.
No it's not, it still needs to find the correct place to insert so it's O(n). But it doesn't need to move the other elements after it like ArrayList.
• ###### 2. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
AFAIK, Vector is not deprecated. It merely was retrofitted to be a List in 1.2. ArrayList is not synchronized whereas Vector is.

- Saish
• ###### 3. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Saish wrote:
AFAIK, Vector is not deprecated. It merely was retrofitted to be a List in 1.2. ArrayList is not synchronized whereas Vector is.

- Saish
You're right of course. It's just the minds of many people where Vector is deprecated :)
• ###### 4. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Kayaman wrote:
It's just O(n). There is no O(n-i) notation. You should know that.
Why should the OP know that? Do you have intimate knowledge of the level of the OP's understanding of Big-O notation?
• ###### 5. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
dannyyates wrote:
Why should the OP know that?
Since he knows enough to differentiate between O(1) and O(n) and in general doesn't ask "what's Big-O notation" he should know that. Unless he really just talks the talk and doesn't walk the walk.
Do you have intimate knowledge of the level of the OP's understanding of Big-O notation?
Thank god no.
• ###### 6. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Thanks Kayaman. I dont know about Big O notation. I will read it. Thanks for pointing out.

between, I read in Sun tutorial reg the List implementation,

http://java.sun.com/docs/books/tutorial/collections/implementations/list.html

-------------------------------
"If you frequently add elements to the beginning of the <code>List</code>
or *iterate over the <code>List </code>to delete elements from its
interior*,
you should consider using <code>LinkedList</code>. These operations
require*constant-time in a <code>LinkedList </code>and linear-time in an<code>ArrayList</code>*."

Could you explain here? is my understanding wrong?

• ###### 7. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Mohamed_Javeed wrote:
"If you frequently add elements to the beginning of the <code>List</code>
or *iterate over the <code>List </code>to delete elements from its
interior*,
you should consider using <code>LinkedList</code>. These operations
require*constant-time in a <code>LinkedList </code>and linear-time in an<code>ArrayList</code>*."

Could you explain here? is my understanding wrong?
Well, this example just mentions that if you're already iterating through the list. Then LinkedList's remove is O(1) and ArrayList's is O(n) (because it has to move all the elements after the one deleted back).

But if you just take 2 Lists, one ArrayList and one LinkedList and say "delete element number 7". Then it's O(n) for both cases.
• ###### 8. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Kayaman,

============================================
List list = new ArrayList();//new LinkedList()
for(int i=0; i < 100000; i++){
}
long start = System.currentTimeMillis();
for(int i=0; i < 100000; i++) {
list.remove(6);
}
long end =
System.currentTimeMillis();

System.out.println(end - start);
``````===============================================
I did this for both ArrayList and LinkedList,

below is the result :

ResultArrayList = 19141 ms

From this I assume, LinkedList will have constant time, where as ArrayList will have Linear time while removing some element in the middle.

• ###### 9. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Try to run that again but instead of 6 and 8 as indices, use 50006 and 50008, then again with 99994 and 99992.

Also you assume something about 'removing an element' but you are also adding an element
• ###### 10. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
``````int N = 100000;
List arrayList = new ArrayList<Integer>();

Random rd = new Random();
long time;

time = System.currentTimeMillis();
for(int i=0; i<N; i++){
}

time = System.currentTimeMillis();
for(int i=0; i<N; i++){
}
System.out.println("\tArrayList: " + (System.currentTimeMillis()-time));
System.out.println();
/************************************************/

System.out.println("Test for removing:");
time = System.currentTimeMillis();
for(int i=0; i<N; i++){
}

time = System.currentTimeMillis();
for(int i=0; i<N; i++){
arrayList.remove(0);
}
System.out.println("\tArrayList: " + (System.currentTimeMillis()-time));
System.out.println();
/************************************************/

time = System.currentTimeMillis();
for(int i=0; i<N; i++){
}

time = System.currentTimeMillis();
for(int i=0; i<N; i++){
}
System.out.println("\tArrayList: " + (System.currentTimeMillis()-time));
System.out.println();
/************************************************/

System.out.println("Test for removing randomly:");
time = System.currentTimeMillis();
for(int i=0; i<N; i++){
}

time = System.currentTimeMillis();
for(int i=0; i<N; i++){
arrayList.remove(rd.nextInt(N-i));
}
System.out.println("\tArrayList: " + (System.currentTimeMillis()-time));
/************************************************/``````
And here is the result:
ArrayList: 47

Test for removing:
ArrayList: 4935

ArrayList: 2350

Test for removing randomly: