This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Linked List Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Linked List" Watch "Linked List" New topic
Author

Linked List

Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
Hello all,

I have a linked list of Items in aisles. I now want to sort the list by aisle. I have already defined my mergeSort to work specifically for the string item 'item' to put the item in alpha order. What would be my options for now sorting by int aisle value? Would I need to add some sort of selection sort to re-sort it by aisle? Or did I really mess it up by making my mergeSort only usable for the string item?

My Grocery class contains constructors, gets, and sets for items and aisles.

Heres my code for GList


Here's my Test Class


Any ideas in the right direction would be helpful. Thanks.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
You're reinventing a lot of things that are in the standard libraries, but I suspect it's for school and if that's the assignment, doing such things can be a perfectly wonderful way to learn, so let's go for it.

Your sort compares items like this:

if(first1.info.getItem().compareTo(first2.info.getItem())<0)

To make this sort on either items or aisles, let's pull the code that changes out to its own class. I'll call it CompareWidget for now. Then the line will look like:

if( compareWidget.compare(first1, first2) ) < 0 )

Can you imagine how you'd write the class CompareWidget, make an instance and use it in the sort? See if you can make that work so it gives you exactly the results you get now. We'll wait right here.

...

Ok, now are you comfortable with polymorphism, extending classes or implementing interfaces? That might be enough hint to get you sorting on aisle number. If not, show us how you're doing and we'll pick up from there.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
We just learned the very basics of polymorphism. Alot of what was involved was not gone into detail in that the semster is about over.

But I did think of a way that I could resolve this would be to write my own SeqSort method. But that could get real messy and confusing when it comes to swapping part of the nodes.

Needless to say I talked to the instructor today about it, she said that I would have to change my MergeSort back to reading the aisle values instead of the item, just to get the aisles to print in order. She is not so much concerned with the items being in alpha order as the aisle.

This assignment has taught me so much more about linked lists, than the whole semester has. Alot of my learning has come from trial and error.
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
But a question as you say create another class called compareWidget, Wouldn't the initial start of the merge sort have to change in that it would have to take in a value in it parameter heading as such:

public void mergeSort()<----right here to say if your sending a String item or Int Aisle?? {
first = recMergeSortItem(first);
}//end mergeSort

I thought a real simple way would be to create 2 mergeSorts in my class have one specific for item and the other specific for Aisle and name the methods as such
public void mergeSortItem()
private LinkedListNode divideListItem()
private LinkedListNode mergeListItem()
private LinkedListNode recMergeSortItem()
or
public void mergeSortAisle()
private LinkedListNode divideListAisle()
private LinkedListNode mergeListAisle()
private LinkedListNode recMergeSortAisle()

But this won't work... because the intital call to mergeSort does not use parameters. Oh well was a nice thought.

But I think I see the logic to this compareWidget class. That is then where the mergeSort would then take either the road to item or to aisle? Is this right?
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296

But this won't work... because the intital call to mergeSort does not use parameters.


Is it because it can't take parameters (i.e. your instructor gave you method signatures that you aren't allowed to change) or because it just currently does not take a parameter?


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
because it just currently does not take a parameter?


I didn't have it set up to take any, wasn't quite sure in depth what would all have to be changed to allow this. Also, the instructor, when I mentioned this thought it was a good idea but she also I don't believe was sure on how this could be changed or didn't look into it any further. There were no definitions of this not being allowed for the assignment. The initial instructions are open for uniqueness.

Basically what she does want is 4 classes;
- Grocery - to have gets and sets, constructors.
- Glist - constructors, methods to insert, print list by item(use recursion), print list by aisle(need to sort first)
- InvalidAisleException - to catch invalid aisles.
- Testing class - to create the list, read items from file and add to the list, print by item(as read in from file), print by aisle, then print again by item to verify that it was sorted.

I took it on my self to try to get it to sort the list alpha. It is not a requirement. She explained that the last print was not intended to actually sort it alpha. She claimed that it was only intended to show that the list did resort the list items after running a sort and printing by aisle.

Example of a print out would be:
Enter the input file name: C:\\TestFile4.txt

bread is a duplicated item.
soup is a duplicated item.

The file C:\\TestFile4.txt contains the following items:
milk in aisle 1
bread in aisle 2
eggs in aisle 1
cheese in aisle 1
cream in aisle 1
soup in aisle 5
ketchup in aisle 5
yogurt in aisle 1

The list print by aisle is:
Aisle: 1
milk
eggs
cheese
cream
yogurt
Aisle: 2
bread
Aisle: 5
soup
ketchup

The list printed by item is:
milk in aisle 1
eggs in aisle 1
cheese in aisle 1
cream in aisle 1
yogurt in aisle 1
bread in aisle 2
soup in aisle 5
ketchup in aisle 5

But I was trying to get the last portion to print as such:

The list printed by item is:
bread in aisle 2
cheese in aisle 1
cream in aisle 1
eggs in aisle 1
ketchup in aisle 5
milk in aisle 1
soup in aisle 5
yogurt in aisle 1

And I was merely interested if there was a way that it could have been incorporated to work in such a way. I think it is a good way to learn new things by experimenting.
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
Could someone also take a look at my print by aisle method:

I am getting this for a result:


But should get:


Heres my print method:


I've tried several changes to my loop and am now really getting mind confused as to what I have already tried. I think I am now at a point where I am basically recoding things I have already tried.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296


It is never possible for this condition to be false.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296

This while loop will either execute infinitely or only execute once.
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
If I change it to this I get the same thing for results


results:
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
If I change it to

or this


I get this:
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
Ok now I tried this:



I get this for results:



Why is only the Aisle 5 not printing correctly?
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
Now I tried this:



and get this:



Any help in a new direction would be appreciated.
Thanks.
Shananne DuFrame
Ranch Hand

Joined: Nov 13, 2006
Posts: 51
resolved the problem, thanks anyhow.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Linked List
 
Similar Threads
? in a Linked List
Reversing a doubly linked list
Generic Java - Linked List
Generics: cannot make a static reference to the non-static type
trying to call a method but cannot find symbol