This content has been marked as final.
Show 12 replies

1. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Kayaman May 25, 2010 5:01 AM (in response to 843793)Mohamed_Javeed wrote:
Yes, except when the internal array needs to be resized for ArrayList (Vector is deprecated so forget about it).
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(ni) for Vector/ArrayList.
It's just O(n). There is no O(ni) 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
800387 May 25, 2010 7:16 AM (in response to Kayaman)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
Kayaman May 26, 2010 1:02 AM (in response to 800387)Saish wrote:
You're right of course. It's just the minds of many people where Vector is deprecated :)
AFAIK, Vector is not deprecated. It merely was retrofitted to be a List in 1.2. ArrayList is not synchronized whereas Vector is.
 Saish 
4. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
796085 May 26, 2010 3:40 AM (in response to Kayaman)Kayaman wrote:
Why should the OP know that? Do you have intimate knowledge of the level of the OP's understanding of BigO notation?
It's just O(n). There is no O(ni) notation. You should know that. 
5. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
Kayaman May 26, 2010 4:29 AM (in response to 796085)dannyyates wrote:
Since he knows enough to differentiate between O(1) and O(n) and in general doesn't ask "what's BigO notation" he should know that. Unless he really just talks the talk and doesn't walk the walk.
Why should the OP know that?
Do you have intimate knowledge of the level of the OP's understanding of BigO notation?
Thank god no. 
6. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
843793 May 26, 2010 6:07 AM (in response to Kayaman)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
Snippet from the link.

"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*constanttime in a <code>LinkedList </code>and lineartime 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
Kayaman May 26, 2010 6:12 AM (in response to 843793)Mohamed_Javeed wrote:
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).
"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*constanttime in a <code>LinkedList </code>and lineartime in an<code>ArrayList</code>*."
Could you explain here? is my understanding wrong?
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
843793 May 26, 2010 7:29 AM (in response to Kayaman)Kayaman,
============================================
List list = new ArrayList();//new LinkedList()
for(int i=0; i < 100000; i++){
list.add(i);
}
long start = System.currentTimeMillis();
for(int i=0; i < 100000; i++) {
list.remove(6);
list.add(8, 99);
}
long end =
System.currentTimeMillis();
System.out.println(end  start);=============================================== I did this for both ArrayList and LinkedList, below is the result : ResultArrayList = 19141 ms LinkedList= 16 ms From this I assume, LinkedList will have constant time, where as ArrayList will have Linear time while removing some element in the middle. any comments?

9. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
800268 May 26, 2010 7:49 AM (in response to 843793)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
796764 Jun 4, 2010 2:52 AM (in response to 843793)
And here is the result:int N = 100000; List linkedList = new LinkedList<Integer>(); List arrayList = new ArrayList<Integer>(); Random rd = new Random(); long time; System.out.println("Test for adding:"); time = System.currentTimeMillis(); for(int i=0; i<N; i++){ linkedList.add(i); } System.out.println("\tLinkedList: " + (System.currentTimeMillis()time)); time = System.currentTimeMillis(); for(int i=0; i<N; i++){ arrayList.add(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++){ linkedList.remove(0); } System.out.println("\tLinkedList: " + (System.currentTimeMillis()time)); time = System.currentTimeMillis(); for(int i=0; i<N; i++){ arrayList.remove(0); } System.out.println("\tArrayList: " + (System.currentTimeMillis()time)); System.out.println(); /************************************************/ System.out.println("Test for adding randomly:"); time = System.currentTimeMillis(); for(int i=0; i<N; i++){ linkedList.add(rd.nextInt(i+1), i); } System.out.println("\tLinkedList: " + (System.currentTimeMillis()time)); time = System.currentTimeMillis(); for(int i=0; i<N; i++){ arrayList.add(rd.nextInt(i+1), 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++){ linkedList.remove(rd.nextInt(Ni)); } System.out.println("\tLinkedList: " + (System.currentTimeMillis()time)); time = System.currentTimeMillis(); for(int i=0; i<N; i++){ arrayList.remove(rd.nextInt(Ni)); } System.out.println("\tArrayList: " + (System.currentTimeMillis()time)); /************************************************/
Test for adding:
LinkedList: 15
ArrayList: 47
Test for removing:
LinkedList: 0
ArrayList: 4935
Test for adding randomly:
LinkedList: 44438
ArrayList: 2350
Test for removing randomly:
LinkedList: 53868
ArrayList: 2334
So depend on what you are using the list for, you can choose between LinkedList and ArrayList for better performance. If you need to insert/remove a lot of elements at different index, ArrayList will be a better choice. 
11. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
EJP Jun 4, 2010 3:06 AM (in response to 796764)That's not correct. The issue with LinkedList is finding the item at a specified index, which is O(N). It is best when used sequentially, when its insert/delete performance is O(1). Conversely ArrayList's strength is random access, which is O(1), but its insert/delete performance is O(N). 
12. Re: Vector, ArrayList, LinkedList which one is better for editing/adding
YoungWinston Jun 15, 2010 3:22 AM (in response to 843793)Mohamed_Javeed wrote:
Just to muddy the waters a bit, you might want to look at ConcurrentSkipListMap, which is a Map based on a skip list, which is a form of linked list that offers logarithmic seek time at the expense of some space overhead. There's also LinkedHashMap... :)
Where as for the intermediate elements it is O(ni) for Vector/ArrayList. This is constant time for LinkedList.
Winston