In this unit, we introduced three kinds of list ADTs , including the actual inde

Question

In this unit, we introduced three kinds of list ADTs, including the actual indexed list ADT provided by Java (see table). There are two primary ways such a table could be implemented: arrays and linked structures. Based on your knowledge of these data structures, complete the following table:

On the table, make bold the operations which have a different order. Give a brief explanation for the difference below.

Method Description Array Big-Oh Linked Big-Oh void add(E element) Adds element to the end of the list. void add(int index, E element) Inserts element at the index. E get(int index) Returns element at the index. void remove(int index) Removes element at the index. void remove(E object) Removes first occurrence of the object. void set(int index, E element) Replaces element at the index. int size() Returns number of elements in the list.

Explanation / Answer

void add(E element) :

Array Big-Oh? : O(1)
Linked Big-Oh : O(1)

Explanation : We just need to add at end of array using arr[index] = value, Similarly for Linked list if we maintain pointer that hold last element reference then just add new element at end will take constant time


void add(int index, E element)

Array Big-Oh? : O(n)
Linked Big-Oh : O(n)

Explanation : For Arrays we need to shift the elements next to that index . Lets say index = 0. Then we need to shift n element to its right which will take O(n) time. Thus adding element at index will take O(n) time.

For Linked List, we need to traverse till that index and then add element. Traversing till that Index will take O(n) time.



E get(int index)

Array Big-Oh? : O(1)
Linked Big-Oh : O(n)

Explanation : Arrays are indexed, So get will take O(1) as we need to return element at that index.

For Linked List, we need to traverse till that index. Traversing till that Index will take O(n) time.

?

void remove(int index)
Array Big-Oh? : O(n)
Linked Big-Oh : O(n)

Explanation : For Arrays we need to shift all the elements after removal. Lets say index = 0. Then we need to shift n-1 element to its right which will take O(n) time. Thus removing element at index will take O(n) time.

For Linked List, we need to traverse till that index and then remove element. Traversing till that Index will take O(n) time.



void remove(E object)
Array Big-Oh? : O(n)
Linked Big-Oh : O(n)?

Explanation : For Arrays we need to shift all the elements after removal. Find the element then remove at that index. Lets say element is at index = 0. Then we need to shift n-1 element to its right which will take O(n) time. Thus removing element at index will take O(n) time.

For Linked List, we need to find the element and then remove element. Traversing till that Index will take O(n) time.



?
void set(int index, E element)
Array Big-Oh? : O(1)
Linked Big-Oh : O(n)?

Explanation : For Arrays we need to set arr[index] = element which will take O(1) time

For Linked List, we need to find the element and then set the element at that index. Hence its O(n) time


int size()
Array Big-Oh? : O(1)
Linked Big-Oh : O(1)?

Explanation : For Arrays it will take O(1) time as we will be maintaining a varibale for the number of element added

For Linked List it will take O(1) time as we will be maintaining a variable for the number of element added in list



Thanks, PLEASE UPVOTE if helpful

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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