Posted on by Kalkicode
Code Single linked list

Add two polynomials using linked list in node js

Js program for Add two polynomials using linked list. Here problem description and other solutions.

/*
    Node JS program for
    Add two polynomials using linked list
*/
class Node
{
	constructor(data, power)
	{
		this.data = data;
		this.power = power;
		this.next = null;
	}
	// Update node value
	updateRecord(data, power)
	{
		this.data = data;
		this.power = power;
	}
}
class AddPolynomial
{
	constructor()
	{
		this.head = null;
	}
	// Display given polynomial nodes
	display()
	{
		if (this.head == null)
		{
			process.stdout.write("Empty Polynomial ");
		}
		process.stdout.write(" ");
		var temp = this.head;
		while (temp != null)
		{
			if (temp != this.head)
			{
				process.stdout.write(" + " + temp.data);
			}
			else
			{
				process.stdout.write("" + temp.data);
			}
			if (temp.power != 0)
			{
				process.stdout.write("x^" + temp.power);
			}
			// Visit to next node
			temp = temp.next;
		}
		process.stdout.write("\n");
	}
	// Add node with given data and power
	addNode(data, power)
	{
		if (this.head == null)
		{
			// Add first node
			this.head = new Node(data, power);
		}
		else
		{
			var node = null;
			var temp = this.head;
			var location = null;
			// Find the valid new node location
			while (temp != null && temp.power >= power)
			{
				location = temp;
				temp = temp.next;
			}
			if (location != null && location.power == power)
			{
				// When polynomial power already exists
				// Then add current add to previous data
				location.data = location.data + data;
			}
			else
			{
				node = new Node(data, power);
				if (location == null)
				{
					// When add node in begining
					node.next = this.head;
					this.head = node;
				}
				else
				{
					// When adding node in intermediate
					// location or end location
					node.next = location.next;
					location.next = node;
				}
			}
		}
	}
	// Add two polynomial
	addTwoPolynomials(other)
	{
		// Define some useful variable
		var result = null;
		var tail = null;
		var node = null;
		// Get first node of polynomial
		var first = this.head;
		var second = other.head;
		// Execute loop until when polynomial are exist
		// And add two polynomial. 
		// Process takes O(n) time.
		while (first != null || second != null)
		{
			// Create node with default value
			node = new Node(0, 0);
			if (result == null)
			{
				// When first resultant node
				result = node;
			}
			if (first != null && second != null)
			{
				if (first.power == second.power)
				{
					// When the polynomial node power are same
					node.updateRecord(first.data + second.data, 
                                      first.power);
					first = first.next;
					second = second.next;
				}
				else if (first.power > second.power)
				{
					// When first polynomial power are larger
					node.updateRecord(first.data, first.power);
					first = first.next;
				}
				else
				{
					// When second polynomial power are larger
					node.updateRecord(second.data, second.power);
					second = second.next;
				}
			}
			else if (first != null)
			{
				// When first polynomial are not empty 
				// Update the current node information
				node.updateRecord(first.data, first.power);
				first = first.next;
			}
			else
			{
				// When second polynomial are not empty 
				node.updateRecord(second.data, second.power);
				second = second.next;
			}
			if (tail == null)
			{
				tail = node;
			}
			else
			{
				// Add new node at end of resultant polynomial
				tail.next = node;
				tail = node;
			}
		}
		// return first node
		return result;
	}
}

function main()
{
	var poly1 = new AddPolynomial();
	var poly2 = new AddPolynomial();
	var result = new AddPolynomial();
	// Add node in polynomial poly1
	poly1.addNode(9, 3);
	poly1.addNode(4, 2);
	poly1.addNode(3, 0);
	poly1.addNode(7, 1);
	poly1.addNode(3, 4);
	// Add node in polynomial poly2
	poly2.addNode(7, 3);
	poly2.addNode(4, 0);
	poly2.addNode(6, 1);
	poly2.addNode(1, 2);
	// Display Polynomial nodes
	console.log("\n Polynomial A");
	poly1.display();
	console.log(" Polynomial B");
	poly2.display();
	result.head = poly1.addTwoPolynomials(poly2);
	// Display calculated result
	console.log(" Result");
	result.display();
}
// Start program execution
main();

Output

 Polynomial A
 3x^4 + 9x^3 + 4x^2 + 7x^1 + 3
 Polynomial B
 7x^3 + 1x^2 + 6x^1 + 4
 Result
 3x^4 + 16x^3 + 5x^2 + 13x^1 + 7

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment