aspose file tools*
The moose likes Beginning Java and the fly likes SortedLinkedList class - Creating an automatically sorted Linked List Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "SortedLinkedList class - Creating an automatically sorted Linked List" Watch "SortedLinkedList class - Creating an automatically sorted Linked List" New topic
Author

SortedLinkedList class - Creating an automatically sorted Linked List

Jack Fletcher
Greenhorn

Joined: Oct 09, 2012
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

Joined: Jun 19, 2010
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.


The quieter you are, the more you are able to hear.
Red Smith
Ranch Hand

Joined: Aug 05, 2007
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
SortedLinkedList<E>

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:

public class SortedLinkedList<E extends Comparable<E>> extends LinkedList<E>

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

Joined: Oct 13, 2005
Posts: 38865
    
  23
It’s actually Foo<E extends Comparable<? super E>>. That allows a superclass of E to implement Comparable.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: SortedLinkedList class - Creating an automatically sorted Linked List