Multilists

Multilists

• Basic concept: A multi-list is a data structure in which there are multiple links from a node.

• In a general multi-list, each node can have any number of pointers to other nodes and there may or may not be inverses for each pointer.

• Multi-lists is a technique in which multiple lists are embedded into a single structure. In multi-list the pointers are used to make multiple link routes through data.

1. Example 1: Multiple orders of one set of elements

Suppose, we have the names and ages of the students as (Monika, 25), (Varsha, 23), (Supriya, 27), (Swati, 24). We can order the above elements alphabetically (By name) or we can order them by numbers (By age). Here the solid link is for ascending order of names and the dotted link is for ascending order of age.

2. Sparse matrix representation using multi-lists

• Defintion: A sparse matrix is a kind of matrix which has a very few non zero elements, as compared to the size m x n of the matrix.

• For example - If the matrix is of size 100 x 100 and only 10 elements are non zero. The concept of sparse matrix has came forward in computer science to investigate such a representation which will store only non-zero elements of the matrix and still carry out the operations quite efficiently.

Representations of sparse matrices :

• The representation of sparse matrix will be a triplet only. In the sense that basically the sparse matrix means very few non-zero elements having in it. Rest of the spaces are having the values zero which are basically useless values or simply empty values. So in this efficient representation we will consider all the non-zero values along with their positions.

• The 0^th row will store total rows of the matrix, total columns of the matrix and total

• For example - Suppose a matrix is 6 × 7 and number of non zero terms are say 8. In our sparse matrix representation the matrix will be stored as

In above representation, the total number of rows and columns of the matrix (6 × 7) are given in 0^th row. Also total number of non-zero elements are given in 0th row of value column i.e. 8.

Here the above array is say named "Sparse". Then

Sparse [0][0] = 6

Sparse [0][1] = 7

Sparse [0][2] = 8

Sparse [1][0] = 0

Sparse [1][1]=6

Sparse [1][2] =-10     and so on.

While representing the sparse matrix using linked list, we will make use of two types of nodes, header node and element node.

Ex. 1.12.1 For the given sparse matrix, write the diagrammatic linked list representation.