[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Efficiency of ArrayList vs LinkedList

Posted on 2011-10-16
6
Medium Priority
?
422 Views
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)
{
     lst.clear();
     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)    
}
0
Comment
Question by:shampouya
6 Comments
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 1000 total points
ID: 36976401
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).
0
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 36976454
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:
http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx

    "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":
http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx

    "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."
0
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 36976461
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!
0
[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

 
LVL 6

Assisted Solution

by:theKashyap
theKashyap earned 1000 total points
ID: 36979614
Insertion:
- 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).

HTH
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36980353
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.

0
 

Author Closing Comment

by:shampouya
ID: 37015609
thanks
0

Featured Post

Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Software development teams often use in-memory caches to improve performance. They want to speed up access to, or reduce load on, a backing store (database, file system, etc.) by keeping some or all of the data in memory.   You should implement a…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Screencast - Getting to Know the Pipeline

872 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