Question

Limit your answers to one paragraph or less.

1. Explain the difference between a statically allocated array, a dynamically allocated array, and a linked list.

2. Linked lists have terrible performance for random access or searching of internal entries. Why?

3. Explain the advantages of adding a tail pointer to a linked list, and of doubly-linked over singlylinked lists.

Answer 1

1)

The main difference between a dynamic array and a regular array is the size. In a regular array the sized is fixed from compilation. In closing the size of an array you can't change it again just think of it set in stone. A dynamic array is basically an array that grow and shrink on demand during run time. An extendable array is a prime example of a dynamic array.the arrays offers constant time access of the elements no matter weather it is static or dynamic array.

on the other hand linked list of a data structure which provide sequential access of the elements. One of the disadvantages of arrays is that memory could be wasted but linked list take only that much memory which is required to store the elements. in arrays the insertion in between the other elements in always slow but in linkedlist the insertion is always efficient

2)

linked list data is a data structure made of nodes where each node in the list is connected with other node by pointers so it have a start and end . the nodes in the list is not indexed so we can not access the list by random access so we have to traverse always from the start .hence the performance will be less as compare to array

3)

advantage of tail pointer is inserting at the end is O(1) instead of O(N).advantage of doubly linked list is we can move both forward and backward in the list and the delete operation in DLL is more efficient if pointer to the node to be deleted is given.