- Question 3 1 Pts Examine The Table On Page 29 Describing The Time Complexity Performance Of Various Array Based Implemen 1 (32.31 KiB) Viewed 41 times
Chapter 2 Array-Based Lists In this chapter, we will study implementations of the List and Queue in- terfaces where the underlying data is stored in an array, called the backing array. The following table summarizes the running times of operations for the data structures presented in this chapter: ArrayStack ArrayDeque DualArrayDeque RoolishArrayStack gel(i)/sel(i,x) add(i,x)/remove(i) O(1) On-i) O(1) O(min{i,n-i}) O(1) O(min{i,n- i}) O(1) O(n-i) Data structures that work by storing data in a single array have many advantages and limitations in common: • Arrays offer constant time access to any value in the array. This is what allows get(i) and sel(i,x) to run in constant time. • Arrays are not very dynamic. Adding or removing an element near the middle of a list means that a large number of elements in the array need to be shifted to make room for the newly added element or to fill in the gap created by the deleted element. This is why the operations add(i,x) and remove(i) have running times that depend on n and i. • Arrays cannot expand or shrink. When the number of elements in the data structure exceeds the size of the backing array, a new array 29