Efficiency of ArrayList vs LinkedList

Posted on 2011-10-16
Last Modified: 2012-05-12
My algorithms textbook says that the first method below, makeList, would have a running time of O(N) if the list is a LinkedList, and a running time of O(N^2) if the list is an ArrayList. Then it says the second method below, mySum, is the opposite. It has a running time of O(N^2) if the list is an LinkedList, and a running time of O(N) if the list is an ArrayList. What causes the switch in running time speed from N to N^2 in these two cases?

public static void makeList(List<Integer> lst, int N)
     for(int = 0; i < N; i++)
          lst.add(0, i);

public static void mySum(List<Integer> lst)
     int total = 0;
     for(int = 0; i < N; i++)
     total += lst.get(i)    
Question by:shampouya
    LVL 37

    Accepted Solution

    For array lists, when you add an item you have to copy the whole thing but it's easy to add things to linked lists since you can just tag them on the end.

    Getting something with an index is super fast with arraylists, but since linked lists just all point to the next element, you have to go through the whole thing just to find the ith element.

    So the N comes because it's in a for loop that runs N times. Then the other N to make the N squared comes from the copy (in the first one) and the search (in the second one).
    LVL 85

    Expert Comment

    by:Mike Tomlinson
    I agree with Tommy's explanation.

    *But...we should note that your code examples are using List<>, not LinkedList<>.

    Both ArrayList and List<> use an underlying Array:

        "The List(T) class is the generic equivalent of the ArrayList class. It implements the IList(T) generic interface using an array whose size is dynamically increased as required."

    Differences in speed between ArrayList and List<> come from boxing/unboxing of value types.  The main benefit to List<> over ArrayList is type safety.

    .Net provides the LinkedList<> class, which uses an actual "linked list"...albeit a "doubly linked list":

        "Represents a doubly linked list. ... Because the LinkedList(T) is doubly linked, each node points forward to the Next node and backward to the Previous node."
    LVL 85

    Expert Comment

    by:Mike Tomlinson
    You didn't specifically say this was in .Net, but I thought I'd point this out since names can be deceiving.  Make sure you look closely at the documentation for whatever language you're using!
    LVL 6

    Assisted Solution

    - ArrayList has a requirement to ensure that elements are allocated contiguously. So the way it goes is:
        - Allocate default size (say 4). So when a new list is created, you have space for 4 elements.
        - When you add 5th element, ArrayList would: 1) Allocate new chunk of memory (say as 2*curr_list_size = 8 in this case). 2) copy existing elements from old to new memory. and finally 3) release old memory.
    - LinkedList has a no requirement to keep elements in contiguous. So the way it goes is:
        - When a new element is inserted, allocate memory for 1 element somewhere in the memory (not contiguous)
        - Update the next/prev links in existing element(s) in the list near which new element is inserted.
    Given this, the insertion time in LinkedList is constant, where as in ArrayList which has to keep de/allocating big chunks of memory and copying old contents etc, it's slower.
    PS: Do note that if you know number of elements to be inserted then you can create the ArrayList with appropriate size to begin with, thus avoiding the problem described above. In this case ArrayList insertion would be faster than LinkedList!)

    Access (read/get):
    - ArrayList:
        - given that elements are allocated contiguously, you can directly index into Nth memory slot if you know you want to get Nth element.
    - LinkedList:
        - given that elements are not contiguous, if you wish to get Nth element, you have to traverse through the links of 1st to (N-1)th elements' links to get to Nth element.

    So LinkedList is slow when it comes to random access (get).

    LVL 37

    Expert Comment

    My answers are based on the question, not the language. The List in the code is not meant to imply a specific kind of list but is just a placeholder for either a linked list or an array.

    Kashyap gives a good example of building somewhat more efficient arraylists. But if you resize them the way he suggests, the adding would be O(Nlg(N)) not O(N^2) so the algorithms book must be considering arrays that grow only 1 element at a time.

    Usually when comparing arrays and linked lists they talk about inserting new items in the middle, not at the end, since this requires a shift and it doesn't matter how the growing is done. I'm assuming that the lst.add(0, i) is adding i to the 0th position in the array which requires shifting.

    Since this is inserting, not appending, the Array insertion will always be slower than the linked list.

    Since this question is based on an Algorithms book, it is talking about inserts and accesses as I have described them. The other things that have been said are correct and valuable but apply to real world structures, not your academic excercise.


    Author Closing Comment


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Find Ransomware Secrets With All-Source Analysis

    Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

    The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
    Introduction A frequently used term in Object-Oriented design is "SOLID" which is a mnemonic acronym that covers five principles of OO design.  These principles do not stand alone; there is interplay among them.  And they are not laws, merely princ…
    how to add IIS SMTP to handle application/Scanner relays into office 365.
    Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…

    760 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    9 Experts available now in Live!

    Get 1:1 Help Now