CHAPTER - 5

APPLICATIONS OF LINKED LISTS

Polynomial Arithmetic
Polynomial consists of two components, a coefficient and an exponent and ‘x’ is a formal parameter.
The polynomial is the sum of terms, each of which consists of coefficient and an exponent for the
formal parameter.
In computer we implement the polynomial as the list of structures consisting of coefficients and
exponents using single linked lists.

Representation of polynomials in memory using Single linked lists

Example:

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 1

Polynomial Single linked lists ADT type definitions
typedef struct node {

int coeff;

int expo;

struct node *next;

};

typedef struct node NODE

{
int count;
NODE * head;

};
Creating and representing a polynomial using Single linked lists
Algorithm insertpoly(NODE * head)
{
NODE * head, newNode,current;
int coeff=c;
int expo=e;
1) if (head)
{
headcoeff=null;
headexpo=null;
headcount=0;
return(head);
}
2) Repeat steps while (currentnext!=null)
{
newNode = ((NODE *)malloc(sizeof(NODE));
Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 2
newNodedata=num;
newNodecoeff=c;
newNodeexpo=e;
newNodenext=null;
current = currentnext;
// Displaying the nodes in the list
printf(“%d”, currentdata);
printf(“%d”, currentcoeff);
printf(“%d”, currentexpo);
}// End of insertpoly
POLYNOMIAL ADDITION
Input two polynomial expressions and compare the powers of both the expressions. If the powers are
equal then add the coefficients of the formal parameter x.

Method for Polynomial Addition

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 3
1) Repeat thru step 3 while there are terms in both polynomials yet to be processed.
2) Obtain the values for each term.
3) If the powers associated with the two terms are equal then if the terms do not cancel then
Insert the sum of the terms into the sum polynomial obtain the next terms in both polynomials to be
added.
else
4) If the power of the first polynomial > power of the second then insert the term from first polynomial
obtain the next term in the first polynomial.
else
Insert the term from second polynomial into sum polynomial. Obtain the next term in the second
polynomial.
4) Copy remaining terms from the nonempty polynomial into the sum polynomial.
5) Return the address of the sum polynomial.
Algorithm polyadd(NODE *head, NODE *p, NODE * q)
// This algorithm is used to add two polynomials
NODE *p,q,r;
1) Repeat steps while((p-->next!=null)&&(qnext!=null))
{
2) if (pexpo > qexpo)
{
r = polyinsert(r, pexpo, pcoeff);
p=pnext;
}
else
3) if (pexpo < qexpo)
{
r = polyinsert(r, qexpo, qcoeff);
q = qnext;
Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 4
}
else
4) r = pcoeff + qcoeff;
e = qexpo;
r = polyinsert(r,e,c);
p = pnext;
q = qnext;
}
5) Repeat steps while(pnext!=null)
{
r = polyinsert(r, pexpo, pcoeff);
printf(“%d”, r);
printf(“%d”, pexpo);
printf(“%d”, pcoeff);
p = pnext;
}
6) Repeat steps while(qnext!=null)
{
r = polyinsert(r, qexpo, qcoeff);
printf(“%d”, r);
printf(“%d”, qexpo);
printf(“%d”, qcoeff);
q = qnext;
}

POLYNOMIAL MULTIPLICATION
Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 5
Method:

1) In this approach we will multiply the 2nd polynomial with each term of 1st polynomial.

2) Store the multiplied value in a new linked list.

3) Then we will add the coefficients of elements having the same power in resultant polynomial.

Example:

Input: Poly1: 3x^2 + 5x^1 + 6,

Poly2: 6x^1 + 8

Output: 18x^3 + 54x^2 + 76x^1 + 48

On multiplying each element of 1st polynomial with elements of 2nd polynomial, we get

18x^3 + 24x^2 + 30x^2 + 40x^1 + 36x^1 + 48

On adding values with same power of x,

18x^3 + 54x^2 + 76x^1 + 48

Input: Poly1: 3x^3 + 6x^1 - 9,

Poly2: 9x^3 - 8x^2 + 7x^1 + 2

Output: 27x^6 - 24x^5 + 75x^4 - 123x^3 + 114x^2 - 51x^1 – 18

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 6

 Algorithm multiplypoly(NODE * p, NODE * q, NODE * r)
// This algorithms implements polynomial multiplication using linked lists.
NODE * r = NULL;
int coeff = c;
int expo = e;
1) Start
2) Repeat steps while((pànext!=NULL)&&(qànext!=NULL))
{
3) c = pàcoeff * qàcoeff;
4) e = pàexpo + qàexpo;
5) r = insertpoly(r, c, e);
6) p = pànext;
7) q = qànext;
}
8) Repeat steps while (pànext!=null)
{
r = insertpoly(r,c,e);
printf(“%d”, “%d”, “%d”, r,c,e);
p = pànext;
}
9) Repeat steps while(qànext!=null)
{
r = insertpoly(r,c,e);
printf(“%d”, “%d”, “%d”, r,c,e);
q = qànext;
}
10) Stop

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 7

SPARSE MATRIX

A matrix in which number of zero entries are much higher than the number of non zero entries is
called sparse matrix. The natural method of representing matrices in memory as two-dimensional
arrays may not be suitable for sparse matrices. One may save space by storing for only non zero
entries.
Sparse Matrix Representations

A sparse matrix can be represented by using TWO representations, those are as follows...

1. Triplet Representation

2. Linked Representation

1. Triplet Representation

In this representation we consider only non-zero values along with their row and column index
values. In this representation the 0th row stores total rows, total columns and total non-zero values in
the matrix.

2. Linked Representation
In linked list representation, linked list data structure is used to represent a sparse matrix.

In linked list representation, each node consists of four fields whereas, in array representation, there
are three fields, i.e., row, column, and value.

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 8

The following are the fields in the linked list:

Row: It is an index of row where a non-zero element is located.

Column: It is an index of column where a non-zero element is located.

Value: It is the value of the non-zero element which is located at the index (row, column).

Next node: It stores the address of the next node.

Array implementation of sparse matrix in C

#include <stdio.h>

int main()

// Sparse matrix having size 4*5

int sparse_matrix[4][5] =

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 9

{0 , 0 , 7 , 0 , 9 },

{0 , 0 , 5 , 7 , 0 },

{0 , 0 , 0 , 0 , 0 },

{0 , 2 , 3 , 0 , 0 }

};

// size of matrix

int size = 0;

for(int i=0; i<4; i++)

for(int j=0; j<5; j++)

if(sparse_matrix[i][j]!=0)

size++;

// Defining final matrix

int matrix[3][size];

int k=0;

// Computing final matrix

for(int i=0; i<4; i++)

{
Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 10
for(int j=0; j<5; j++)

if(sparse_matrix[i][j]!=0)

matrix[0][k] = i;

matrix[1][k] = j;

matrix[2][k] = sparse_matrix[i][j];

k++;

// Displaying the final matrix

for(int i=0 ;i<3; i++)

for(int j=0; j<size; j++)

printf("%d ", matrix[i][j]);

printf("\t");

printf("\n");

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 11

}

return 0; }

typedef struct node {

int rows;

int columns;

int value;

struct node *next;

};

typedef struct node NODE

int count;

NODE *head;

};

Algorithm createsparsematrix(NODE * head)

// This algorithm creates head structure for a linked list head node

// Local declarations

NODE *head;

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 12

1) Start

2) // Allocate memory for the list

head = (NODE *) malloc(sizeof(NODE));

3) If (head)

4) // Set list head to null

head ànext = NULL;

5) / * Set list count to zero */

headàcount = 0;

6) Stop

Algorithm insertSparsematrix(int r, int c, int r)

// This algorithm creates the nodes to represent sparse matrix

NODE * newnode, current;

1) Start

2) if (current == NULL)

current = createsparsematrix(r,c,val);

else

3) Repeat steps while (currentànext != NULL)

newnode = ((NODE *) malloc(sizeof(NODE));

newnode à rows = r;
Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 13
newnodeàcolumns = c;

newnodeàvalue = num;

current = currentànext;

printf(“%d”, currentàrows);

printf(“%d”, currentàcolumns);

printf(“%d”, currentàvalue);

count++;

4) Stop

Operations on Sparse matrices

Sparse matrix Addition

1. In order to add two sparse matrices the lists are traversed until the end of one of the lists is reached.

2. In the process of traversal, the row indices stored in the nodes of these lists are compared. If they
don't match, a new node is created and inserted into the resultant list.

3. If the row indices match, column indices for the corresponding row positions are compared. If they
don't match, a new node is created and inserted into the resultant list.

4. If the column indices match, a new node is created and inserted into the resultant list by copying
the row and column indices from any of the nodes and the value equal to the sum of the values in the
two nodes.

5. After this, the pointers in both the lists are advanced to make them point to the next nodes in the
respective lists. This process is repeated in each iteration. After reaching the end of any one of the
lists, the iterations come to an end and the remaining nodes in the list whose end has not been reached
are copied, as it is in the resultant list.
Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 14
Example

Consider the following sparse matrices:

If the procedures add is applied to the above linked list representations then we get the resultant list,
as shown in Figure below.

Figure: Result of application of the procedures add.

Algorithm SparseAdd(NODE * t1, NODE * t2, NODE * temp)

// This algorithm implements Sparse matrix addition using linked lists

NODE * temp = NULL;

1) Start

2) Repeat steps while((t1 != NULL)&&((t2 != NULL)

3) if(t1àrow== t2àrow)

tempàrow = t1àrow;

tempàcolumns = t1àcolumns;

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 15

tempàvalue= t1àvalue;

tempànext = NULL;

t1 = t1ànext;

t2 = t2ànext;

4) if(t1àcolumns < t2àcolumns)

tempàrow = t1àrow;

tempàcolumns = t1àcolumns;

tempàvalue= t1àvalue;

re=insertSparseMatrix(temp);

t1 = t1ànext;

else

5) tempàrow = t2àrow;

tempàcolumns = t2àcolumns;

tempàvalue= t2àvalue;

re=insertSparseMatrix(temp);

t2 = t2ànext;

else

6) if(t1àrows< t2àrows)

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 16

tempàrow = t1àrow;

tempàcolumns = t1àcolumns;

tempàvalue= t1àvalue;

re=insertSparseMatrix(temp);

t1 = t1ànext;

else

7) tempàrow = t1àrow;

tempàcolumns = t1àcolumns;

tempàvalue= t1àvalue;

re=insertSparseMatrix(temp);

8) Repeat steps while (t1 != NULL)

tempàrow = t1àrow;

tempàcolumns = t1àcolumns;

tempàvalue= t1àvalue;

t1 = t1ànext;

printf(“%d”, re, tempàrows, tempàcolumns, tempàvalue);

9) Repeat steps while (t2 != NULL)

tempàrow = t2àrow;

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 17

tempàcolumns = t2àcolumns;

tempàvalue= t2àvalue;

t2 = t2ànext;

printf(“%d”, re, tempàrows, tempàcolumns, tempàvalue);

10) Stop

REPRESENTATION OF COMPLEX NUMBERS

A complex number contains real and imaginary part. The structure defined for a complex number can
be

tyedef struct complexnum

float real;

float imaginary;

};

To gain access to individual structure members, a structure membership operator must be used.

Example:

complexnum.real = 3.2;

To access the address of structure variables then the structure membership operator used will be

(&complexnum)àreal = 3.2;

Prepared by Dr.B.GOPI, Asst.Professor, KIST, KAKUTUR Page 18