Question

How do you implement lists and related ADTs with arrays? Include in your analysis fixed-sized arrays, expandable arrays, and the pros and cons of using arrays to implement them.

Answer 1

Implementing List using array.
here we store elements of list into an array.
functions:
(1)insertion(value , position) : for inserting an element at given position ,we will shift right all elements after that position ,so that it create a space for new elements .
if it is fixed-sized array and array is full then no insertion allowed.
and if it is expandable array and array is full then first expand the array then follow insertion procedure.

(2)deletion(value): to delete first occurrence of value in array ,first we need to search value in the array.
if(value not found) return.
else shift all right elements of given value 1 position left.

(3)get(position) : To get an element from array at any given position,first we check whether array contain position number of element s or not.
if(it contain)then return arr[position-1];

pro:
(a)Accessing an element in an array is fast.we can access any element in array just using index value(O(1) time)

(b)Arrays have better cache locality that can make a pretty big difference in performance.

cons:
(a)Inserting a new element in an array of elements is expensive because a room has to be created for the new elements and to create room existing elements have to be shifted.

(b)Operations like insertion and deletion in arrays consume a lot of time.