Solved

# Efficiency of ArrayList vs LinkedList

Posted on 2011-10-16

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)

}