File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

SortedLinkedList class - Creating an automatically sorted Linked List

 
Jack Fletcher
Greenhorn
Posts: 13
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Java Python Ruby
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Netscape Opera Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 47232
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It’s actually Foo<E extends Comparable<? super E>>. That allows a superclass of E to implement Comparable.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic