• Post Reply Bookmark Topic Watch Topic
  • New Topic

Insertion Sorting a Simply Linked List  RSS feed

 
Andrei Paduraru
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi , I am trying to add a sorting method to this code and I cannot figure it out how.

This is my Linked list class:

And this is my Node class:

Can anyone help me with this ?
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks to me like you're actually 75% there.

I presume this is the bit of code you have added and are having problems with:


My questions to this:
What is the purpose of this "sort" method?
What parameters should it take?
What is "data"? Where should this value come from?


From its name, my guess would be that the purpose is to sort the entire list.
From the code within it I would guess that you are trying to insert data at a specific point in the list.
Possibly this code belongs to a different method: public void insertInOrder(Node data)
which
- assumes that the list is already in order
- inserts the data into the linked list at the correct place.

You can then use the insertInOrder method from a sort() method.
 
Andrei Paduraru
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Basically I have an array of hexadecimal numbers that I converted to decimal numbers and I want to add them in my linked list but I do not want to sort them in the array, I want them to be sorted in my LinkedList class when I call the method in my main class.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Andrei Paduraru wrote:Basically I have an array of hexadecimal numbers that I converted to decimal numbers and I want to add them in my linked list but I do not want to sort them in the array, I want them to be sorted in my LinkedList class when I call the method in my main class.

Well, there's a couple of things you could do to help things out:
1. Make your Node class a static nested class of your LinkedList class. That way, your list class has access to its private members. If you think about it, it actually makes sense because your Node really only works with your LinkedList class.
2. Add a 'tail' field to your list that points to the last Node; or contains null if the List is empty. Then your add(Object) operation should work in constant time.

Alternatively, implement your list as a "ring" with an 'anchor' Node that always contains null as its "data" and never gets removed, which acts as the link between the last and first Nodes (or links to itself if the list is empty). Then you can simulate an "add at end" operation with:There are actually quite a few advantages to a ring implementation, which makes me wonder why it isn't taught more.

The other thing I would suggest: Write down every step of an insertion sort (if that's what you want to implement) in detail and in English (or your native language) before you write one line of it in your class.

HIH

Winston
 
Norm Radder
Rancher
Posts: 2240
28
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Thanks for the information. Have a cow.


To the OP, for future reference, please read this ... http://www.coderanch.com/how-to/java/BeForthrightWhenCrossPostingToOtherSites

Have a happy holiday everyone,
Henry
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!