xercise Show how to implement the Vector\'s operations using (a) Fixed-Size Arra

Question

xercise Show how to implement the Vector's operations using (a) Fixed-Size Array Sizent t (b) Growable Array (incremental and doubling strategies) (c) Singly Linked List d) Doubly Linked List Compute the time and space complexity for all operations. Main vector operations: at(int i): returns the element at indexi without removing it set(int i, Object o): replace the element at index i with o - insert(int i, Object o): insert a new element o to have indexi _ erase(inti): removes the element at index i Additional operations sizel) and emptyl) .

Explanation / Answer

//fixed size_ array
//let assume array is global and is referenced by a[] and total number of elements be size_

//Time complexity = O(1)

//Space complexity = O(n) array of size n
int at(int i)
{
if(i>=size_)
{
cout<<"invalid index";
return 0;
}
returns a[i];
}

//Time complexity = O(1)

//Space complexity = O(n) array of size n

int set(int i,Object o)
{
if(i>=size_)
{
cout<<"invalid index";
return 0;
}
a[i]=o;
}

-in fixed size_d array insertion at any index is not possible
-in fixed size_d array deletion at any index is not possible
size = size_

//variable size_ array
//let assume array is global and is referenced by a[] and initial total initial number of elements be size_

//Time complexity = O(1)

//Space complexity = O(n) array of size n

int at(int i)
{
if(i>=size_)
{
cout<<"invalid index";
return 0;
}
returns a[i];
}

  

//Time complexity = O(1)

//Space complexity = O(n) array of size n

int set(int i,Object o)
{
if(i>=size_)
{
cout<<"invalid index";
return 0;
}
a[i]=o;
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int insert(int i,Object o)
{
if(i==size_)
{
resize_();
a[size_]=o;
return 0;
}
int temp= a[i];
for(int j=i+1;j<size_;j++){
a[j] = temp;
temp = a[j];
}
a[i]=o
return 0;
}
void resize_() {
size__t newsize_ = size_ * 2;
int* newArr = new int[newsize_];

memcpy( newArr, arr, size_ * size_of(int) );

size_ = newsize_;
delete [] arr;
arr = newArr;
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int erase(int i)
{
for(int j=i;i<size_-1;i++){
a[j] = a[j+1];
}
  
}

//Time complexity = O(1)

int size()
{
return size_;
}

//Time complexity = O(1)

bool empty()
{
if(size_>0)
return false;
return true;
}

-- Singly linked list

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int at(int i)
{
struct s* ptr = root;
int j=0;
while(ptr!=NULL)
{
if(j==i)
return ptr->data;
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int set(int i, Object o)
{
struct s* ptr = root;
int j=0;
while(ptr!=NULL)
{
if(j==i)
{
ptr->data = o;
return 0;
}
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int insert(int i, Object o){
struct s* ptr = root;
struct s*temp;
struct s* newNode = (struct s*)malloc(sizeof(struct s));
newNode->data = o;
newNode->next = NULL;
int j=0;
while(ptr!=NULL)
{
if(j==i)
{
newData->next = ptr->next;
ptr-> next = newData;
return 0;
}
temp = ptr;
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int erase(int i){
struct s* ptr = root;
struct s*temp;
int j=0;
while(ptr!=NULL)
{
if(j==i)
{
temp->next= ptr->next;
return 0;
}
temp = ptr;
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

int size(){
struct s* ptr = root;
int j=0;
while(ptr!=NULL)
{
ptr= ptr->next;
j++;
}
return j;
}

//Time complexity = O(n)

bool empty(){
if(size()>0)
return false;
return true;
}

-- Doubly linked list

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int at(int i)
{
struct s* ptr = root;
int j=0;
while(ptr!=NULL)
{
if(j==i)
return ptr->data;
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int set(int i, Object o)
{
struct s* ptr = root;
int j=0;
while(ptr!=NULL)
{
if(j==i)
{
ptr->data = o;
return 0;
}
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int insert(int i, Object o){
struct s* ptr = root;
struct s*temp;
struct s* newNode = (struct s*)malloc(sizeof(struct s));
newNode->data = o;
newNode->next = NULL;
newNode->prev = NULL;
int j=0;
while(ptr!=NULL)
{
if(j==i)
{
newData->next = ptr->next;
newData->next->prev = newData;
ptr-> next = newData;
newData->Prev = ptr;
return 0;
}
temp = ptr;
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

//Space complexity = O(n) array of size n

int erase(int i){
struct s* ptr = root;
struct s*temp;
int j=0;
while(ptr!=NULL)
{
if(j==i)
{
temp->next= ptr->next;
temp->next->prev = temp;
return 0;
}
temp = ptr;
ptr= ptr->next;
j++;
}
}

//Time complexity = O(n)

int size(){
struct s* ptr = root;
int j=0;
while(ptr!=NULL)
{
ptr= ptr->next;
j++;
}
return j;
}

//Time complexity = O(n)

bool empty(){
if(size()>0)
return false;
return true;
}

Related Questions

Navigate

• Browse (All)
• Browse X
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.