• Post Reply Bookmark Topic Watch Topic
  • New Topic

sorted list  RSS feed

 
Ioannis Michailidis
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everybody,

I have the following class, and two questions on it:



1. Now lets assume, that we have the nodes i and k already in the collection, and we use addElement() to add node j inbetween. The while loop will go until run <- i. Therefore run.next <- j at both sides of the assignment (line 23). According to my understanding, the run.next to the left should point at j, but the run.next in the constructor should point at k. What is going on here? I guess this is a beginners question, I would appreciate some keywords I can search for.

2. The object in the method's field should always implement the interface Ordered. How do I make this clear to the potential user of this method?

Thanks in advance.
ioannis
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ioannis Michailidis wrote:2. The object in the method's field should always implement the interface Ordered. How do I make this clear to the potential user of this method?

Use generics, viz:
public class SortedList<E extends Ordered> implements Collection
(I presume you want anyone to be able to use this class)

And actually, Ordered should probably specify a type too.

That actually helps you in lots of ways, because you don't have to cast. Your SortedNode then becomes:
static class SortedNode<E extends Ordered>
(there's no need for it to be an inner class)

and the declaration for your addElement() method becomes:
public void addElement(E o)

I'm afraid I didn't understand your first question, but one thing you might find useful for a class like this is to have Ordered.compare(null) return -1 - ie, any Ordered value is always "less than" null.

BTW - You do understand that your Ordered interface already exists in the form of java.lang.Comparable? I assume this is just an exercise, so maybe you want to "roll your own", but just thought I'd mention it.

Winston
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What happens if the new node is greater than all existing nodes already in the list?
By the way: does <− mean “less than”? If so, please use the < symbol and no −.
 
Ioannis Michailidis
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks to both of you for your quick replies.

I probably did not explain my first question correctly. What is the value of run.next in the line 23? In my eyes, the left run.next should point at the SortedNode j and the right run.next at the SortedNode k. Does this mean, that the compiler starts from the right at which point run.next is still k (j does not exist yet) and after j has been created, the compiler jumps to the left, where run.next is then j (run is at all times i). If so, although some kind of anveturous, it would also explain line 17, where the new root would point to the old...

I used "<-" as an arrow, according to Knuth. I didn't take into account the case where the new node is the last, i guess it should point at null...
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!