I am working on a java linked list problem which asks me to deal with large integers, which the integer is too large to fit in primitive data types.

There are three java files. The first is LargeInteger.java which I have to work on. The second is LLNode.java which provides the linked list. The third one is a JUnit test file.

Please help me on this one and I will rate. Thanks.

Here is LargeInteger.java:

package largeinteger;

import largeinteger.LLNode;

/** The LargeInteger class

* This class represents a large, non-negative integer using a linked list.

* Each node stores a single digit. The nodes represent all digits in *reverse* order:

* the least significant digit is the first node, and the most significant the last node.

* For example, 135642 is represented as 2->4->6->5->3->1 in that order.

*/

public class LargeInteger {

private LLNode head; // head of the list

private int size; // size (i.e. number of digits)

// Returns size

public int size() { return size; }

// Returns the linked list (used only for JUnit test purpose)

public LLNode getList() { return head; }

public LargeInteger() {

head = null; size = 0;

}

/** Constructor that takes a String as input and constructs the linked list.

* You can assume that the input is guaranteed to be valid: i.e. every character

* in the string is between '0' and '9', and the first character is never '0'

* (unless '0' is the only character in the string). You can use input.charAt(i)-'0'

* to convert the character at index i to the integer value of that digit.

* Remember: the list nodes must be in reverse order as the characters in the string.

*/

public LargeInteger(String input) {

// TODO

}

/** Divide *this* large integer by 10 and return this.

* Assume integer division: for example, 23/10 = 2, 8/10 = 0 and so on.

*/

public LargeInteger divide10() {

// TODO

return null;

}

/** Multiply *this* large integer by 10 and return this.

* For example, 23*10 = 230, 0*10 = 0 etc.

*/

public LargeInteger multiply10() {

// TODO

return null;

}

/** Returns a *new* LargeInteger object representing the sum of this large integer

* and another one (given by that). Your code must correctly handle cases such as

* the two input integers have different sizes (e.g. 2+1000=1002), or there is a

* carry over at the highest digit (e.g. 9999+2=10001).

*/

public LargeInteger add(LargeInteger that) {

// TODO

return null;

}

/** Returns a new LargeInteger object representing the result of multiplying

* this large integer with a non-negative integer x. You can assume x is either

* a positive integer or 0. Hint: you can use a loop and call the 'add' method

* above to accomplish the 'multiply'.

*/

public LargeInteger multiply(int x) {

// TODO

return null;

}

/** Recursive method that converts the list referenced by curr_node back to

* a string representing the integer. Think about what's the base case and

* what it should return. Then think about what it should return in non-base case.

* Hint: refer to the 'printing a list backwards' example we covered in lectures.

*/

private String toString(LLNode curr_node) {

// TODO

return null;

}

/** Convert this list back to a string representing the large integer.

* This is a public method that jump-starts the call to the recursive method above.

*/

public String toString() {

return toString(head);

}

// Recursive method to compute factorial

public static LargeInteger factorial(int n) {

if(n==0) return new LargeInteger("1");

return factorial(n-1).multiply(n);

}

// Recursive method to compute power

public static LargeInteger pow(int x, int y) {

if(y==0) return new LargeInteger("1");

return pow(x, y-1).multiply(x);

}

}

Here is LLNode.java:

package largeinteger;

/** Generic LLNode class

* Note that both data members are public

* so you can access them directly without

* having to use the getters and setters.

*/

public class LLNode {

public T data;

public LLNode link;

public LLNode() {

this(null, null);

}

public LLNode(T data, LLNode link) {

this.data = data;

this.link = link;

}

}

Here is also the JUnit test file PublicLargeIntegerTest.java:

package largeinteger;

import static org.junit.Assert.*;

import org.junit.Test;

public class PublicLargeIntegerTest {

private LargeInteger number;

@Test

public void testConstructor0() {

number = new LargeInteger("0");

assertTrue(number.size()==1);

assertTrue(number.getList().data==0);

assertTrue(number.getList().link==null);

}

@Test

public void testConstructor1() {

number = new LargeInteger("123");

assertTrue(number.size()==3);

LLNode node = number.getList();

assertTrue(node.data==3);

node = node.link;

assertTrue(node.data==2);

node = node.link;

assertTrue(node.data==1);

node = node.link;

assertTrue(node==null);

}

@Test

public void testToString0() {

number = new LargeInteger("123");

assertTrue(number.toString().equals("123"));

}

@Test

public void testToString1() {

number = new LargeInteger("111222333444555666777888999000");

assertTrue(number.toString().equals("111222333444555666777888999000"));

}

@Test

public void testDivide10() {

number = new LargeInteger("15");

LargeInteger result = number.divide10();

assertTrue(number==result); // returns the same LargeInteger object

assertTrue(number.getList().data==1);

assertTrue(number.getList().link==null);

assertTrue(number.size()==1);

assertTrue(number.toString().equals("1"));

}

@Test

public void testDivide10More() {

number = new LargeInteger("9");

LargeInteger result = number.divide10();

assertTrue(number==result); // returns the same LargeInteger object

assertTrue(number.getList().data==0);

assertTrue(number.getList().link==null);

assertTrue(number.size()==1);

assertTrue(number.toString().equals("0"));

number = new LargeInteger("123456789");

assertTrue(number.divide10().toString().equals("12345678"));

assertTrue(number.size()==8);

assertTrue(number.getList().data==8);

}

@Test

public void testMultiply10() {

number = new LargeInteger("15");

LargeInteger result = number.multiply10();

assertTrue(number==result);

assertTrue(number.toString().equals("150"));

assertTrue(number.size()==3);

assertTrue(number.getList().data==0);

}

@Test

public void testMultiply10More() {

number = new LargeInteger("0");

assertTrue(number.multiply10().toString().equals("0"));

assertTrue(number.multiply10().size()==1);

assertTrue(number.multiply10().getList().data==0);

}

@Test

public void testAdd0() {

LargeInteger i1 = new LargeInteger("123");

LargeInteger i2 = new LargeInteger("456");

number = i1.add(i2);

assertTrue(number.toString().equals("579"));

assertTrue(number.size()==3);

assertTrue(number!=i1); // check return is a new object

assertTrue(number!=i2); // check return is a new object

}

@Test

public void testAdd1() {

LargeInteger i1 = new LargeInteger("987");

LargeInteger i2 = new LargeInteger("876");

number = i1.add(i2);

assertTrue(number.toString().equals("1863"));

assertTrue(number.size()==4);

assertTrue(number!=i1);

assertTrue(number!=i2);

}

@Test

public void testAdd2() {

LargeInteger i1 = new LargeInteger("999");

LargeInteger i2 = new LargeInteger("1");

number = i1.add(i2);

assertTrue(number.toString().equals("1000"));

assertTrue(number.size()==4);

number = i2.add(i1);

assertTrue(number.toString().equals("1000"));

assertTrue(number.size()==4);

assertTrue(number!=i1);

assertTrue(number!=i2);

}

@Test

public void testMultiply0() {

number = new LargeInteger("123");

assertTrue(number.multiply(1)!=number); // check return is a new object

assertTrue(number.multiply(1).toString().equals("123"));

assertTrue(number.multiply(2).toString().equals("246"));

assertTrue(number.multiply(2).size()==3);

}

@Test

public void testMultiply1() {

number = new LargeInteger("123");

assertTrue(number.multiply(12).toString().equals("1476"));

assertTrue(number.multiply(12).size()==4);

assertTrue(number.multiply(0).toString().equals("0"));

assertTrue(number.multiply(0).size()==1);

assertTrue(number.multiply(123).toString().equals("15129"));

}

@Test

public void testFactorial0() {

number = LargeInteger.factorial(5);

assertTrue(number.toString().equals("120"));

}

@Test

public void testFactorial1() {

number = LargeInteger.factorial(20);

assertTrue(number.toString().equals("2432902008176640000"));

assertTrue(number.size()==19); // make sure size is also correct

}

@Test

public void testPow0() {

number = LargeInteger.pow(2, 10);

assertTrue(number.toString().equals("1024"));

}

@Test

public void testPow1() {

number = LargeInteger.pow(5, 20);

assertTrue(number.toString().equals("95367431640625"));

assertTrue(number.size()==14); // make sure size is also correct

}

}