Data Structures and Algorithms - Old Questions

12. Discuss the merits and demerits of contiguous list and linked list.

Merits of Contiguous List / array

• It is used to represent multiple data items of same type by using only single name.

• It can be used to implement other data structures like linked lists, stacks, queues, trees, graphs etc.

• 2D arrays are used to represent matrices.

• Implementation of list using array is easier as compared other implementation.

Demerits of Contiguous List / array

• The size of the array is fixed. Most often this size is specified at compile time. This makes the programmers to allocate arrays, which seems "large enough" than required.

• Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.

• Deleting an element from an array is not possible. Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are weak.

• Generally array's allocates the memory for all its elements in one block whereas linked lists use an entirely different strategy. Linked lists allocate memory for each element separately and only when necessary.

Merits of Linked List

1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program.

2. Linked lists have efficient memory utilization. Here, memory is not preallocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.

3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.

4. Many complex applications can be easily carried out with linked lists.

5. There is no need to define an initial size for a Linked list.

6. Linked List reduces the access time.

Demerits of Linked List

1. They use more memory than arrays because of the storage used by their pointers.

2. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.

3. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.

4. Nodes are stored in-contiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.