macOS Java linked list question

[DesertFox]

Hello,

I have 2 items in each node of my linked list. My goal is to perform polynomial addition and multiplication (assignment from my college prof). The first item in the node is the coefficient and the second is the exponent. Right now im only able to search and delete according to the first item in the list...

How do I check the second items in the node as well in the list as well?

And, also, does anyone know how addition and multiplication is suppose to work with linked lists?

Any help is much appreciated.

Here is the source code:

class LinkListApp
{
public static void main (String [] args )
{
LinkList firstEq = new LinkList(); // create first equation
LinkList secondEq = new LinkList(); // create second equation

// fill equations with coefficient and exponent
firstEq.insertFirst(4, 1);
firstEq.insertFirst(3, 1);
firstEq.insertFirst(2, 2);
firstEq.insertFirst(4, 2);
firstEq.insertLast(3, 3);

secondEq.insertFirst(2, 1);
secondEq.insertFirst(1, 1);
secondEq.insertFirst(4, 2);
secondEq.insertFirst(3, 2);

firstEq.displayList();
secondEq.displayList();

Link x = firstEq.find(4);
if( x != null)
System.out.println("Found link with key " + x.iData);
else
System.out.println("Can't find link");

Link y = firstEq.delete(3);
if( y != null )
System.out.println("Deleted link with key " + y.iData);
else
System.out.println("Can't delete link");


firstEq.displayList();




/*
while (!theList.isEmpty() ) // delete until list is empty
{
Link aLink = theList.deleteFirst();
System.out.print("Deleted ");
aLink.displayLink();
System.out.println("");
}

theList.displayList();
*/
}

}

NOW THE LINKLIST FILE:


class LinkList
{
private Link first; // ref to first link on list
private Link last; // ref to alst link on list

public LinkList()
{
first = null;
last = null;
}

public boolean isEmpty() // true of list is empty
{
return (first==null);
}

// insert at start of list
public void insertFirst( int id, int dd)
{
Link newLink = new Link(id, dd); // makes new link

if (isEmpty() )
last = newLink;

newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}

public void insertLast(int id, int dd) // insert at end of list
{
Link newLink = new Link(id, dd); // make new link

if( isEmpty() ) // if empty list,
first = newLink; // first --> newLink
else
last.next = newLink; // old last --> newLink

last = newLink; // newLink <-- last
}


// find link with given key
public Link find (int key)
{
Link current = first; // start at first
while(current.iData != key ) // while no match
{
if (current.next == null) // if end of list
return null; // didnt find it
else
current = current.next; // go to next link
}
return current; // found it
}

public Link delete(int key)
{
Link current = first;
Link previous = first;
while(current.iData != key )
{
if ( current.next == null )
return null;
else
{
previous = current;
current = current.next;
}
}

if(current == first)
first = first.next;
else
previous.next = current.next;
return current;
}


// delete first item (assumes list is not empty)
public Link deleteFirst()
{
Link temp = first; // save reference to link
first = first.next; // delete it: first --> old
return temp; // return deleted link
}

public void displayList()
{
System.out.print("Equation { coefficient, exponent }: ");
Link current = first; // start at beginning of list
while (current != null )
{
current.displayLink(); // print data
current = current.next;
}

System.out.println();
}
}


AND THE LIST FILE:

class Link
{
public int iData;
public int dData;
public Link next;

public Link (int id, int dd)
{
iData = id;
dData = dd;
}

public void displayLink()
{
System.out.print("{ " + iData + ", " + dData + " } ");
}

}

 

[Eraserhead]

I am totally puzzled, why in the linked list class do you not just use two arrays of doubles/ints?

 

[lazydog]

Hi DessertFox

Looks to me as though your linked list stuff is searching on the coefficient rather than the exponent. I would have thought searching on the exponent would be much more useful since in a (canonical?) polynomial equation the exponents should be unique… eg 4x^3 + 4x^2 + 4x.

If by addition and multiplication you mean symbolic addition and multiplication then for addition you would have something like this:-

equation1: 4x^3 + 3x^2 +2
equation2: 3x^2 + 5x

equation1 + equation2: 4x^3 + 6x^2 + 5x + 2

So addition would involve walking through the linked lists adding the coefficients of items with the same exponent to produce the result.

Mulitplication is a bit more difficult. This involves multiplying each item in the 1st equation by each item in the 2nd equation to produce the result. In multiplication you would multiply coefficients and add exponents. So in the above example:-

equation1 * equation2: 12x^5 + 20x^4 + 9x^4 + 15x^3 +6x^2 + 10x

If you look at the result you'll see you have 2 items that have an exponent of 4. So you would add these together to give

equation1 * equation2: 12x^5 + 29x^4 + 15x^3 + 6x^2 + 10x


hope this helps

b e n