Code fragment 1:

for (int k = list1.size() - 1; k >= 0; k--) {
    list2.add(list1.remove(k));
}

Code fragment 2:

while (!list1.isEmpty()) {
    list2.add(list1.remove(0));
}

In this question you will be asked to analyze the worst-case time complexity of each of the code fragments given different implementations of the List ADT. For each analysis, you should assume that list1 starts out with N items and list2 starts out empty. You may further assume that each implementation includes a numItems data member that is updated and used appropriately.

Express your complexities using "Big-O" notation and briefly justify your answers.

1. Assume that list1 and list2 are ArrayLists where both arrays have enough unused space so that they never need to be resized during the operations performed by either of the code fragments.
   1. What is the worst-case time complexity of code fragment 1?
   2. What is the worst-case time complexity of code fragment 2?
2. Assume that list1 and list2 are LinkedLists where the LinkedList class has been implemented as a circular, singly-linked chain of nodes with a reference to the tail.
   1. What is the worst-case time complexity of code fragment 1?
   2. What is the worst-case time complexity of code fragment 2?
3. Assume that list1 and list2 are LinkedLists where the LinkedList class has been implemented as a doubly-linked chain of nodes with references to the head and to the tail.
   1. What is the worst-case time complexity of code fragment 1?
   2. What is the worst-case time complexity of code fragment 2?