Question

What are the pros and cons of using a linked implementation of a sparse matrix, as opposed to an array-based implementation?

Answer 1

Answer:

Linked lists and arrays are both linear data structures but while an array is a collection of items that can be accessed randomly, a linked list can be accessed sequentially.

A sparse matrix contains very few non-zero elements. For example;

_                        _

|  0   0   3  0  6    |

|   0   5   0  0  4   |

|   2   0   0  0  0   |

|_ 0   0   0  0  0 _|

In the implementation of a sparse matrix, the following are some of the pros and cons of using a linked list over an array;

PROS

i.  Linked lists are dynamic in nature and are readily flexible - they can expand and contract without having to allocate and/or de-allocated memory compared to an array where an initial size might need to be set and controlled almost manually. This makes it easy to store and remove elements from the sparse matrix.

ii. No memory wastage. Since the size of a linked list can grow or shrink at run time, there's no memory wastage as it adjusts depending on the number of items it wants to store. This is in contrast with arrays where you might have unallocated slots. Also, because the zeros of the sparse matrix need not be stored when using linked lists, memory is greatly conserved.

CONS

i. One of the biggest cons of linked lists is the difficulty in traversing items. With arrays, this is just of an order of 0(1) since the only requirement is the index of the item. With linked lists, traversal is sequential which means slow access time.

ii. Storage is another bottle neck when using linked lists in sparse matrix implementation. Each node item in a linked list contains other information that needs to be stored alongside the value such as the pointer to the next or previous item.