Posted on by Kalkicode
Code Single linked list

Add two polynomials using linked list in kotlin

Kotlin program for Add two polynomials using linked list. Here problem description and explanation.

/*
    Kotlin program for
    Add two polynomials using linked list
*/
class Node
{
	var data: Int;
	var power: Int;
	var next: Node ? ;
	constructor(data: Int, power: Int)
	{
		this.data = data;
		this.power = power;
		this.next = null;
	}
	// Update node value
	fun updateRecord(data: Int, power: Int): Unit
	{
		this.data = data;
		this.power = power;
	}
}
class AddPolynomial
{
	var head: Node ? ;
	constructor()
	{
		this.head = null;
	}
	// Display given polynomial nodes
	fun display(): Unit
	{
		if (this.head == null)
		{
			print("Empty Polynomial ");
		}
		print(" ");
		var temp: Node ? = this.head;
		while (temp != null)
		{
			if (temp != this.head)
			{
				print(" + " + temp.data);
			}
			else
			{
				print(temp.data);
			}
			if (temp.power != 0)
			{
				print("x^" + temp.power);
			}
			// Visit to next node
			temp = temp.next;
		}
		print("\n");
	}
	// Add node with given data and power
	fun addNode(data: Int, power: Int): Unit
	{
		if (this.head == null)
		{
			// Add first node
			this.head = Node(data, power);
		}
		else
		{
			var node: Node ? ;
			var temp: Node ? = this.head;
			var location: Node ? = 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 = 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
	fun addTwoPolynomials(other: AddPolynomial ? ): Node ?
	{
		// Define some useful variable
		var result: Node? = null;
		var tail: Node ? = null;
		var node: Node ? ;
		// Get first node of polynomial
		var first: Node ? = this.head;
		var second: Node ? = 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 = 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;
	}
}
fun main(args: Array < String > ): Unit
{
	val poly1: AddPolynomial = AddPolynomial();
	val poly2: AddPolynomial = AddPolynomial();
	val result: AddPolynomial = 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
	println("\n Polynomial A");
	poly1.display();
	println(" Polynomial B");
	poly2.display();
	result.head = poly1.addTwoPolynomials(poly2);
	// Display calculated result
	println(" Result");
	result.display();
}

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