1. Why is accessing an item by index slower in a linked list than an array? 2. W
ID: 663509 • Letter: 1
Question
1. Why is accessing an item by index slower in a linked list than an array? 2. What is the Big-O running time of the following code fragment? Assume lst1 has N items, and lst2 is initially empty. public static void add( List<Integer> lst1, List<Integer> lst2) { for ( Integer x : lst1 ) lst2.add(0, x); // add to front } a. If an ArrayList is passed for lst1 and lst2. Explain your answer. b. If a LinkedList is passed for lst1 and lst2. Explain your answer. 3. What is the Big-O running time of the following code fragment? public static void erase( List<Integer> lst ) { Iterator<Integer> itr = lst.iterator(); while ( itr.hasNext() ) { Integer x = itr.next(); itr.remove(); } } a. If an ArrayList is passed for lst1 and lst2. Explain your answer. b. If a LinkedList is passed for lst1 and lst2. Explain your answer. 4. What is the Big-O running time of the following code fragment? Assume lst1 has N items, and lst2 has M items. public static int Count( List<Integer> lst1, List<Integer> lst2) { Iterator<Integer> itr1 = lst1.iterator(); int count=0; while ( itr1.hasNext() ) { Integer x = itr1.next(); Iterator<Integer> itr2 = lst2.iterator(); while ( itr2.hasNext() ) if ( x.equals( itr2.next()) ) count++; } return count; } a. If an ArrayList is passed for lst1 and lst2. Explain your answer. b. If a LinkedList is passed for lst1 and lst2. Explain your answer. 5. What is the Big-O running time of the following code fragment? public static int calc( List<Integer> lst ) { int count = 0; int N = lst.size(); for ( int i=0; i<N; i++) { if (lst.get(i) > 0) sum += lst.get(i); else sum += lst.get(i) * lst.get(i); } return sum; } a. If an ArrayList is passed. Explain your answer. b. If a LinkedList is passed. Explain your answer. 6. Suppose a Java method receives a List<Integer> and reverses the order of the items it contains by removing each item from the front of the list, adding each item to a Stack<Integer>, and then removing the items from the stack and inserting each item to the end of the list. What is the expected Big-O running time if: a. If an ArrayList is passed. Explain your answer. b. If a LinkedList is passed. Explain your answer. 7. Show each step of converting a+b*c+(d-e) from infix to postfix notation, using the algorithm described in the textbook that uses a stack.
Explanation / Answer
Please find my answers below for each question asked above.
1. ArrayList has direct reference to every element in the list, so we can get the indexed element in constant time by directly referencing the arraylist with the given index. Where as in LinkedList we need to traverse the list from the beginning element to get to the indexed element.
2.
a) With array List, Big O running time is O(N). An array list is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. If the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied, an expensive operation. When a new element is getting added in the beginning that has to adjust the memory.
b) With Linked List, The Big O running time is O(1). As the new item will be added somewhere in the memory and that will be mapped at the beginning of the linked list.
3. Inserting/deleting at the beginning of array list/linked list works in the same way
a) With array List, Big O running time is O(N). An array list is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. If the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied, an expensive operation. When a new element is getting added in the beginning that has to adjust the memory.
b) With Linked List, The Big O running time is O(1). As the new item will be added somewhere in the memory and that will be mapped at the beginning of the linked list.
4. Count/ indexing works by parsing the entire list
a) For array lis, The Big O running time is O(1). as these are all consecutive locations, this doesnot need to parse the entire list and can get the count in less time.
b) For Linked list, the Big O running time is O(n). As these are not consecutive memory locations, we need to traverse the entire list and count each item in the list.
5.
a) For array list, the Big O time is O(n). We need to get each element and count the values, so it will require more time.
b) For Linked list, the Big O time is O(n). We need to traverse the entire list and get each element and count the values, so it will require more time.
6.
a) For array list, the Big O time is O(n). This removes a single element at first position. After that all elements from the right are shifted to the left via System.arraycopy call, that
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.