Category Archives: Java Abstract Data Type Implementation

LargeInt Abstract Data Type Implementation : Using Link List

This program demonstrates the Large Integer Abstract Data Type implementation using link list in Java.

The Operation implemented :
1. Declaring Large Integer Data Type
2. Addition of two Large Non negative Integers

The Operation which are under implementation
3. Addition of two Large negative Integers
4. Subtraction of two Large Integers
5. Multiplication of two Large Integers
6. Divide of two Large Integers

The implementation logic and memory representation is shown in the below picture.

LargeInt Abstract Data Type

LargeInt Abstract Data Type

Find the Java Code below :

This Class shows the showcase/usecase (How to use LargeInt Class) of the LargeInt Class

/*
* This class demonstrates use of Large Int Class in Java.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 14th April, 2014
*/
public class UseLargeIntDemo{
/**
* The main method
* @param void
* @return Sting[].
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String snumberOne="",snumberTwo="";
LargeInt numberOne = null, numberTwo = null, sum = null;
System.out.println("Please Enter Large Integer Number 1 : ");
snumberOne = sc.next();
System.out.println("Please Enter Large Integer Number 2 : ");
snumberTwo = sc.next();
numberOne = new LargeInt(snumberOne); // Creating Object of LargeInt for number 1
numberTwo = new LargeInt(snumberTwo); // Creating Object of LargeInt for number 2
sum = numberOne.add(numberTwo); // Performing Addition Operation
System.out.println(sum); // Printing Data
}
}

This is the actual implementation of LargeInt Class


/*
* This class represents the LargeInt Abstract Data Type in java. It have Add Method Implemented.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 14th April, 2014
*/
class LargeInt {
private List L;
private LargeInt(){
L = new List();
}

public LargeInt(String str){
L = new List();
populate(str);
}
/**
* This method populates the string into the list.
* @param String
* @return void.
*/
void populate(String str){
int i=0;
int length = str.length();
while(i<length){
this.prepend(str.charAt(i)-'0');
i++;
}
while(i<100){
this.append('0'-'0');
i++;
}
}

/**
* This method appends single digit in beguning of the list.
* @param int
* @return void.
*/
public void append(int num){
this.L.append(num);
}
/**
* This method appends single digit at last of the list.
* @param int
* @return void.
*/
public void prepend(int num){
this.L.prepend(num);
}
/**
* This method adds the number digit by digit from two lists.
* @param LargeInt
* @return LargeInt.
*/
public LargeInt add(LargeInt B){
LargeInt c = new LargeInt();
int carry = 0,sum = 0;
ListNode temp1=this.L.getHead();
ListNode temp2=B.L.getHead();
while(temp1!=null){
sum = temp1.getData()+temp2.getData()+carry;
if(sum%10!=0){
carry = sum/10;
sum = sum%10;
}else{
if(sum==10){
carry = sum/10;
sum = sum%10;
}else{
carry = 0;
}
}
c.prepend(sum);
temp1=temp1.getNext();
temp2=temp2.getNext();
}
if(carry!=0)
c.prepend(carry);
return c;
}
/**
* This method prints the number represented by the list.
* @param int
* @return void.
*/
public void print(){
this.removeZeroes();
this.L.print();
}

@Override
public String toString() {
this.removeZeroes();
return L.toString();
}
/**
* This method remove the unneccessary zeros from the list.
* @param void
* @return void.
*/
public void removeZeroes(){
ListNode temp=this.L.getHead();
while(temp!=null){
if(temp.getData()==0){
this.L.popFront();
}else{
return;
}
temp=temp.getNext();
}
}
}

This is the List used for implementation


/*
* This class demonstrates Link List Node Representation in java.
* @author : Madan Gopal Singh
* @version : 3.0
* @date : 14th April, 2014
*/
class ListNode{

private int data;
private ListNode next;

public ListNode(){}

public ListNode(int num){
data=num;
next = null;
}

public int getData(){
return data;
}

public void setData(int x){
data = x;
}

public void setNext(ListNode p){
next = p;
}
public ListNode getNext(){
return next;
}
}
/*
* This class demonstrates Link List Representation in java.
* @author : Madan Gopal Singh
* @version : 3.0
* @date : 14th April, 2014
*/
class List{
private ListNode Head;
public List(){
Head=null;
}
public ListNode getHead(){
return Head;
}
public void setHead(ListNode p){
Head = p;
}
/**
* This method returns last node of the list.
* @return ListNode.
*/
public ListNode last(){
ListNode temp=Head;
if(Head==null) return null;
while(temp.getNext()!=null){
temp=temp.getNext();
}
return temp;
}
/**
* This method appends the node at last in the list.
* @param int
* @return void.
*/
public void append(int num){
ListNode new_node = new ListNode(num);
ListNode temp=Head;
if(temp==null){
Head = new_node;
return;
}
while(temp.getNext()!=null) temp=temp.getNext();
temp.setNext(new_node);
}
/**
* This method appends the node at beguning of the list.
* @param int
* @return void.
*/
public void prepend(int num){
ListNode new_node = new ListNode(num);
new_node.setNext(Head);
Head = new_node;
}
/**
* This method delete the last node of the list.
* @param void
* @return void.
*/
public void popBack(){
ListNode temp=Head,prev=null;
//NULL list
if(Head==null){System.out.println("List is Empty");}
//single element
if(Head.getNext()==null){
//delete Head;
Head=null;
return;
}
while(temp.getNext()!=null){
prev = temp;
temp=temp.getNext();
}
temp=null;
prev.setNext(null);
}
/**
* This method prints the list data.
* @param void
* @return void.
*/
public void print(){
ListNode temp=Head;
while(temp!=null){
System.out.print(temp.getData());
temp=temp.getNext();
}
}

@Override
public String toString() {
ListNode temp=Head;
String listData="";
while(temp!=null){
listData += temp.getData();
temp=temp.getNext();
}
return listData;
}
/**
* This method append the pased list to last of the current list.
* @param List
* @return void.
*/
public void copy(List L){
Head = null;
ListNode temp = L.Head;
while(temp!=null){
this.append(temp.getData());
temp=temp.getNext();
}
}
/**
* This method prints the list data in reverse order.
* @param void
* @return void.
*/
public void printReverse(){
ListNode curr=Head;
ListNode prev_last=null;

while(Head!=null && prev_last!=Head){
curr = Head;
while(curr.getNext()!=prev_last){
curr = curr.getNext();
}
System.out.println(curr.getData());
prev_last = curr;
}
}

/**
* This method deletes the node from bugining of the lise.
* @param void
* @return void.
*/
public void popFront(){
ListNode temp=Head,next=null;
//NULL list
if(Head==null){System.out.println("List is Empty");}
//single element
if(Head.getNext()==null){
//delete Head;
Head=null;
return;
}else{
next = temp.getNext();
Head = next;
}
}

}

I appreciate all your feed backs.

Advertisements