Sorting a Linked List of Strings

Question

public class LinkedList {
    private Node top;

    public LinkedList() {
        top = null;
    }

    public void add(String data) {
        Node temp = new Node(data, top);
        top = temp;
    }

    public void sort() {
        LinkedList sortedList = new LinkedList();
        Node i;
        Node j;
        String temp;
        String temp2;
        String temp3;
        for (i = top; i != null; i.getNext()) {
            for (j = i.getNext(); j != null; j.getNext()) {
                if (i.getData().compareTo(j.getData()) < 0) {
                    temp = i.getData();
                    i.setData(temp);
                    temp2 = j.getData();
                    j.setData(temp2);
                    temp3 = temp;
                    temp = temp2;
                    temp2 = temp3;
                    sortedList.add(temp3);
                } else if (i.getData().compareTo(j.getData()) > 0) {
                    temp3 = i.getData();
                    sortedList.add(temp3);
                }
            }
        }
    }
}

Can someone go over my code and tell me why my temp and temp2 never get assigned and used? And why this isn't working?

When I run my main I just get the original linked list not the sorted one.

Is my logic correct? I am trying to sort the strings in an ascending order.

Can you please mention what is ```top```? Is it the first or last Node? Can you verify if the input list has proper data. — Sandesh Gupta, Mar 23 '18 at 11:07
You should Use Collections.sort() method. Also Visit this url for more better understanding. https://stackoverflow.com/questions/10042/how-do-i-create-a-linked-list-data-structure-in-java — Umesh Kumar Sharma, Mar 23 '18 at 11:13
When debugging i find that its repeating the same data value over and over..? — Ali Khan, Mar 23 '18 at 11:15
What does `i.getNext()` do? Perhaps you meant `i = i.getNext()` in the `for` loop? --- http://idownvotedbecau.se/nodebugging/ --- Besides, how do you expect good help when you don't post all the relevant code? — Andreas, Mar 23 '18 at 11:18
My bad. it should have been i = i.getNext(). now im getting my sorted linked list to print but its not sorted. its still the same as the original one. — Ali Khan, Mar 23 '18 at 11:21
Which sorting algorithm did you implement? Please clearly state that in the question and add the corresponding tag to your question so that experts on this sorting algorithm find your question. — Zabuzard, Mar 23 '18 at 11:29

cisk · Answer 1 · 2018-03-23T11:31:36.510

0

Since the OP updated his code snippet, the following code can't work because the LinkedList mentioned is a custom List and not the java.util.LinkedList.

Didn't manage to run your code because of the missing "top" variable. By the way if you need to have all values of i and j to a single and sorted LinkedList try this:

    LinkedList sortedList = new LinkedList();

    sortedList.addAll( ALL_YOUR_VALUES FROM i )
    sortedList.addAll( ALL_YOUR_VALUES FROM j )

    Collections.sort(sortedList);
    // now your LinkedList should be sorted

edited Mar 23 '18 at 11:31

answered Mar 23 '18 at 11:13

cisk

589
3
13

That does not work since OPs `LinkedList` is a **custom implementation**, not `java.util.LinkedList`. It does not implement `Collection`, the methods can thus not be used. – Zabuzard Mar 23 '18 at 11:28

Zabuzard · Answer 2 · 2018-03-23T11:47:03.693

Explanation

You are assigning the (possibly) sorted values to a new list sortedList. This list has nothing to do with your original list (this). And thus your original list won't change.

In the end you need to copy over the structure of sortedList to your current instance, or directly sort in-place.

Solution

So assuming that your sorting actually works, append something like this to the end of sort():

// Copy data of sorted list over to own instance
Node currentSortedElement = sortedList.top;
Node currentNonSortedElement = top;

while (currentSortedElement != null) {
    // Extract data and copy over
    currentNonSortedElement.setData(currentSortedElement.getData());

    // Prepare next iteration
    currentSortedElement = currentSortedElement.next;
    currentNonSortedElement = currentNonSortedElement.next;
}

Therefore take a look at the following lists

index      | 0  1  2  3  4  5
-----------|-----------------
sorted     | 1  4  4  6  8  9
non-sorted | 4  1  6  9  8  4

The algorithm will just copy the data of each item from the sorted list to the item of the non-sorted list at the same index, so

index      | 0  1  2  3  4  5
-----------|-----------------
sorted     | 1  4  4  6  8  9
           | |  |  |  |  |  |
           | v  v  v  v  v  v
non-sorted | 1  4  4  6  8  9

Notes

According to your comment you try to implement Bubblesort. Consider taking a look at the related question Bubble Sort Manually a Linked List in Java which shows a working code example, with explanation.

Hey, thanks for the explaination now im getting a null pointer exception at currentNonSortedElement.setData(currentSortedElement.getData()); — Ali Khan, Mar 23 '18 at 16:44
@AliKhan Sounds like your `currentNonSortedElement` object is `null`. Which usually means you have a logic error in your code. A good opportunity to open a new question :) But first make sure to read [What is a NullPointerException, and how do I fix it?](https://stackoverflow.com/questions/218384/what-is-a-nullpointerexception-and-how-do-i-fix-it). If an answer helped, consider up-voting and/or accepting it. — Zabuzard, Mar 23 '18 at 18:28

Sorting a Linked List of Strings

2 Answers2

Explanation

Solution

Notes