Question

There are two popular implementations of the List Abstract Data Types

¨An array implementation of the List Abstract Data Types

¨A linked list implementation of the List Abstract Data Types

Discuss the advantage/disadvantage of these implementations

Answer 1

Array Implementation of List Abstract Data Types:

Advantages:
1. In arrays, we have indexes for every element and thus, it is very easy to access every element as it is index based searching, It can be achieved in O(1) time.

Disadvantages:
Insertion and Deletion takes time complexity O(n) in worst case, as it would require shifting of elements and traversing all the elements in worst case.

The Static Allocation of array leads to memory wastage, as a fixed memory is allocated. The elements are arranged in a contigous memory location. So, unavailability of contigous memory locations can create a problem.

Linked List Implementation of List Abstract Data Types
Advantages:

The elements of Linked list are randomly located in memory, and pointers are used to keep the address of every node. Although extra memory is required to save pointers but it allows random location of elements in memory.

The insertion and deletion is very fast in Linked list as only rearrangement of pointers is required.

Disadvantages:
Searching takes O(n) time in worst case, as it is required to traverse the entire list to find the element.

(If you like the answer, please hit an upvote, Thankyou.)