Question

Answer the following questions:

• Compare and contrast arrays and linked-lists. What are the advantages and disadvantages of either data structure?

• Describe why binary search is more effective for finding an element in the array rather than searching through it in a linear fashion. Under what circumstances can binary search work correctly?

Answer 1

Arrays:-

An array is the linear data structure with a collection of similar type of data. It's size if fixed and all element in an array in a contiguous memory location. Memory allocation happens in compile time.

LinkedList:-

LinkedList is the linear data-structure where you can store any type of data. It's dynamic in size and it stores the element in a node(which has two-part 1.data-> to store value 2.pointer to next node ) in a non-contiguous memory location. Memory allocation happens in run time.

Advantage of Linked List:

1. Dynamic nature:- The size of linked List is dynamic in nature i.e we can increase and decrease the size of LinkedList according to our need but in case of an array, you can declare size only once.

2. Easy to insert and delete element:- In linked list to insert/delete an element at a specific location you just have to update the pointer of previous and next node but in the case to array you have to shift all the element.

Disadvantage of Linked List:

1. In LinkedList to store every element, we need an extra pointer to store the address of the next node.

2. To access the particular element in LinkedList you have to do liner search but an array, you can directly go to a specific location by array_name[location]

Binary search is more effective than linear search because of the less time complexity to find the element. If you search the element in a linear fashion then the time complexity will be O(n) and if you go for binary search then time complexity will O(logn).

Binary search work correctly only when an element is in sorted order. Then only you will get the correct value because binary search follows the method where it will compare the middle element with the element we want to find if the value will be same then it will give the result and if the middle element is greater than element then it search the element in the left side else in right side part.