Representation of polynomials using Generalized Linked List

Hello and welcome. In this week's blog, we will look at a specific application of linked lists. We have dealt with polynomials since high school and now we will write a program to add two polynomials. We will be using a linked list to store the polynomials. Let's start by understanding what is a linked list?

What is a Linked List?

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

Image Credits - GeeksforGeeks

• Linked List is a sequence of links that contains items. 
• Each link contains a connection to another link. 
• Linked list is the second most-used data structure after array.

There are various types of Linked Lists. Most commonly used are singly linked lists, doubly linked lists, and circularly linked lists. Each type has its own applications.

So, what is a Generalized Linked List?

A Generalized Linked List L is defined as a finite sequence of n>=0 elements, l1, l2, l3, l4, …, ln, such that li is either atom or the list of atoms. Thus

L = (l1, l2, l3, l4, …, ln)

where n is the total number of nodes in the list.

Image Credits - GeeksforGeeks

Generalized linked lists are used because although the efficiency of polynomial operations using a linked list is good but still, the disadvantage is that the linked list is unable to use multiple variable polynomial equations efficiently. It helps us to represent multi-variable polynomial along with the list of elements.

A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + …. + jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is a non-negative integer, which is called the degree of a polynomial.

An essential characteristic of the polynomial is that each term in the polynomial expression consists of two parts:

• one is the coefficient
• other is the exponent

• The sign of each coefficient and exponent is stored within the coefficient and the exponent itself.
• Additional terms having equal exponent is a possible one.
• The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent.

Every polynomial can be written in this fashion, factoring out the main variable z, followed by a second variable y, etc. Looking carefully now at P(x,y,z) we see that there are two terms in the variable z, Cz2 + Dz, where C and D are polynomials themselves but in the variables x and y. Looking closer at C(x,y), we see that it is of the form Ey3 + Fy2, where E and F are polynomials in x. Continuing in this way we see that every polynomial consists of a variable plus coefficient exponent pairs. Each coefficient is itself a polynomial (in one less variable) if we regard a single numerical coefficient as a polynomial in zero variables.

Polynomials can be stored in a Linked List as follows, after following the above rules:

Image credits - GeeksforGeeks

Now, we have a basic understanding of Linked Lists and GLL. Let's use this knowledge to build a family tree in which we can store hierarchical data. In the next blog, we will store data of family members in a GLL. Stay tuned :)

-Sarvesh Patki

K-72

References-

[1]Tutorials Point -https://www.tutorialspoint.com/index.htm

[2] GeeksforGeeks - https://www.geeksforgeeks.org/