Java linked list question

Discussion in 'Mac Programming' started by DesertFox, Mar 17, 2007.

  1. macrumors member

    Joined:
    Nov 25, 2004
    #1
    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 + " } ");
    }

    }
     
  2. macrumors G4

    Eraserhead

    Joined:
    Nov 3, 2005
    Location:
    UK
    #2
    I am totally puzzled, why in the linked list class do you not just use two arrays of doubles/ints?
     
  3. macrumors 6502a

    Joined:
    Sep 3, 2005
    Location:
    Cramlington, UK
    #3
    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
     

Share This Page