programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Help me sort my Singly Linked List

Ranch Hand
Posts: 122
Okay guys, I searched a lot but can't seem to understand the sorting of a SLLNode... I noticed a method called Bubble Sort, I understand how it works, but can't think of a way to implement it to my code... Can you please give me a hand?

Bartender
Posts: 10575
66
Kaspersky Ukshini wrote:Okay guys, I searched a lot but can't seem to understand the sorting of a SLLNode... I noticed a method called Bubble Sort, I understand how it works, but can't think of a way to implement it to my code... Can you please give me a hand?

I'm afraid nobody here is going to write it for you Kaspersky. Why don't you show us what you've done so far?

I should warn you that it's likely to be fairly fiddly, because in order to move a Node - which you'll need to do in order to "swap" it - you'll need to keep track of the Node before it (assuming the List is forward-pointing). Luckily, in a bubble sort, the Nodes you swap are always adjacent, so it's less hassle, but you'll still need to keep track of the Nodes before and after the ones you're actually swapping.

Another little tip for you: When "moving" Nodes in any linked list, try and disturb the List as little as possible while you're doing it. The technique I learned I call "bridging", although I'm not sure that it's technically correct. Suppose you have a set of Nodes:

... → A → B → C → D → ...

and you want to swap B and C around. The sequence goes something like this:

• 1. Point B to D. This effectively "removes" C from the List, since nothing points to it any more, so anything that happens to be traversing the List at this point will move from A to B to D. However, since C still points to D, any traversal that happened to be on C at the time will still move on to D.
• 2. Point A to C. This effectively "removes" B from the List, and re-attaches C after A, so anything that happens to be traversing the List at this point will now move from A to C to D; however, since B also points to D, any traversal that happened to be on B at the time will still move on to D.
• 3. Finally, point C to B. This re-attaches B to its new position in the List.

• It's by no means the only way to do it, but there are sequences that make it more likely for Nodes to be repeated, so be careful. [*]

And if you don't follow the description, get out a piece of paper and write it down in diagrams - linked lists are tricky, and a picture is often worth a thousand words.

HIH

Winston

[*] PS: Repeated Nodes can happen with the above procedure as well - specifically, the sequence A → B → C → B → D - but it would be very unusual. Indeed, I don't think repetition can be prevented without synchronization, although I'm sure someone will correct me if I'm wrong.

Kaspersky Ukshini
Ranch Hand
Posts: 122
This is what I've come up with until now:

I'm copying my D.L list into another one, and then create another one. The reason is simple, I compare two D.L lists (which are the same), the first with all, once i find the biggest, I add it as first into another list.. then I get the 2nd element, compare with the rest.

It's working but not in all the cases... I'm missing something!

EDIT: Fixed it!! THANKYOU!