Jack Fletcher
Greenhorn
Posts: 13
Hi guys,

I have a homework assignment in which I need to write a SortedLinkedList<E> class.
My project is a system for a library and both books and users are stored in LinkedLists after their data is read in from a text file.
I currently have got the system functioning with regular LinkedLists but now need to switch this to be automatically sorted.

The users are placed in one LinkedList and the books in another. The users should be sorted by their surnames, in ascending order. If their surnames are the same then the user's first names should be used to determine their sorting.
With the books, they should be sorted by their author's surname. The ordering here is unimportant in the case that two author's have the same surname.

I understand that I will need to override the 'add' method and use a comparator here although I have not coded this before and have no idea how to start going about it.

Any help would be greatly appreciated! :-)
Thanks.

Kemal Sokolovic
Bartender
Posts: 825
5
You should check the Insertion Sort algorithm, because that's the effect you want to have (with slight modifications). Though it's not very fast in terms of running time (O(n^2)) it would be a good starting point for you.
Examine that algorithm and try to make it work with a simpler implementation (try with list of numbers). Once you get it and get it to work you can easily incorporate it with your application.

Red Smith
Ranch Hand
Posts: 136
1
Jack Fletcher wrote:Hi guys,

I have a homework assignment in which I need to write a SortedLinkedList<E> class.
My project is a system for a library and both books and users are stored in LinkedLists after their data is read in from a text file.
I currently have got the system functioning with regular LinkedLists but now need to switch this to be automatically sorted.

I tried this and it appears that

has to become SortedLinkedList<E extends Comparable> since you are have to compare two E. But I was surprised even that is not enough. E has to be applied to Comparable as well:

Overriding add(E) does seem the way to go.

I found this on the web with regard to Comparable versus Comparator:

Comparable

A comparable object is capable of comparing itself with another object. The class itself must implements the java.lang.Comparable interface in order to be able to compare its instances.

Comparator

A comparator object is capable of comparing two different objects. The class is not comparing its instances, but some other classâ€™s instances. This comparator class must implement the java.util.Comparator interface.

Campbell Ritchie
Sheriff
Posts: 49379
62
It’s actually Foo<E extends Comparable<? super E>>. That allows a superclass of E to implement Comparable.