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

    Vector, ArrayList, LinkedList which one is better for editing/adding

    843793
      Hello All,

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

      Please share you experience.

      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
          Kayaman
          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
            800387
            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
              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
                796085
                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
                  Kayaman
                  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
                    843793
                    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*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
                      Kayaman
                      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
                        843793
                        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
                          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
                            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(N-i));
                                    }
                                    System.out.println("\tLinkedList: " + (System.currentTimeMillis()-time));
                            
                                    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:
                            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
                              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
                                Mohamed_Javeed wrote:
                                Where as for the intermediate elements it is O(n-i) for Vector/ArrayList. This is constant time for LinkedList.
                                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... :-)

                                Winston