• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Insertion Sorting a Simply Linked List

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ?
 
Bartender
Posts: 1845
10
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Rancher
Posts: 5008
38
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Also posted at: http://www.dreamincode.net/forums/topic/386705-i-need-help-with-insertion-sort-in-linked-lists/
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Norm Radder wrote:Also posted at: http://www.dreamincode.net/forums/topic/386705-i-need-help-with-insertion-sort-in-linked-lists/



Thanks for the information. Have a cow.


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

Have a happy holiday everyone,
Henry
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic