Bubble Sort Manually a Linked List in Java

Question

This is my first question here. I am trying to manually sort a linked list of integers in java and I can not figure out what is wrong with my code. Any suggestions? I don't get any error, however I still have my output unordered. I tried a few different ways, but nothing worked. I appreciate if anyone can help me with that.

public class Node {

    int data; 
    Node nextNode;

    public Node(int data) {
        this.data = data;
        this.nextNode = null;       
    }

    public int getData() {
        return this.data;
    }
} // Node class


public class DataLinkedList implements DataInterface {  
    private  Node head;
    private int size; 

    public DataLinkedList(){
        this.head = null;
        this.size = 0;
    }

    public void add(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
        } else {
            Node currentNode = head;
            while(currentNode.nextNode != null) {
                currentNode = currentNode.nextNode;
            }
            currentNode.nextNode = node;
        }
        size++;     
    }

    public void sort() {
        if (size > 1) {
            for (int i = 0; i < size; i++ ) {
                Node currentNode = head;
                Node next = head.nextNode;
                for (int j = 0; j < size - 1; j++) {
                    if (currentNode.data > next.data) {
                        Node temp = currentNode;
                        currentNode = next;
                        next = temp;
                    } 
                    currentNode = next;
                    next = next.nextNode;                   
                } 
            }
        }
    }

    public int listSize() {     
        return size;
    }

    public void printData() {
        Node currentNode = head;
        while(currentNode != null) {
            int data = currentNode.getData();
            System.out.println(data);
            currentNode = currentNode.nextNode;
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }
} // DataInterface class

public class DataApp {

    public static void main (String[]args) {

        DataLinkedList dll = new DataLinkedList();

        dll.add(8);
        dll.add(7);
        dll.add(6);
        dll.add(4);
        dll.add(3);
        dll.add(1);

        dll.sort();
        dll.printData();
        System.out.println(dll.listSize());
    }
} // DataApp class

you do Node currentNode = head; each times. but you do not change the head. actualy you compare the first element with other size-times — feech, Apr 25 '15 at 19:33

Baltasarq · Accepted Answer · 2015-04-27T11:09:10.363

The problem, as expected, comes in method sort():

public void sort() {
        if (size > 1) {
            for (int i = 0; i < size; i++ ) {
                Node currentNode = head;
                Node next = head.nextNode;
                for (int j = 0; j < size - 1; j++) {
                    if (currentNode.data > next.data) {
                        Node temp = currentNode;
                        currentNode = next;
                        next = temp;
                    } 
                    currentNode = next;
                    next = next.nextNode;                   
                } 
            }
        }
    }

A minor problem is just do always execute the bubble sort n*n times. It is actually better check whether there was a change between any pair in the list. If it was, then there is the need to run again all over the list; if not, there isn't. Think of the marginal case in which a list of 100 elements is already sorted when sort() is called. This means that nodes in the list would be run over for 10000 times, even when there is actually nothing to do!

The main problem, though, is that you are exchanging pointers to the nodes in your list.

if (currentNode.data > next.data) {
    Node temp = currentNode;
    currentNode = next;
    next = temp;
}

If you translate currentNode by v[i] and next by v[i - 1], as if you were sorting an array, that would do. However, you are just changing pointers that you use to run over the list, without effect in the list itself. The best solution (well, provided you are going to use BubbleSort, which is always the worst solution) would be to exchange the data inside the nodes.

if (currentNode.data > next.data) {
    int temp = currentNode.data;
    currentNode.data = next.data;
    next.data = temp;
}

However, for a matter of illustration of the concept, I'm going to propose changing the links among nodes. These pointers are the ones which actually mark the sorting in the list. I'm talking about the nextNode attribute in the Node class.

Node exchange in a single linked list

Enough chat, here it is:

public void sort() {
        if (size > 1) {
            boolean wasChanged;

            do {
                Node current = head;
                Node previous = null;
                Node next = head.nextNode;
                wasChanged = false;

                while ( next != null ) {
                    if (current.data > next.data) {
                        /*
                        // This is just a literal translation
                        // of bubble sort in an array
                        Node temp = currentNode;
                        currentNode = next;
                        next = temp;*/
                        wasChanged = true;

                        if ( previous != null ) {
                            Node sig = next.nextNode;

                            previous.nextNode = next;
                            next.nextNode = current;
                            current.nextNode = sig;
                        } else {
                            Node sig = next.nextNode;

                            head = next;
                            next.nextNode = current;
                            current.nextNode = sig;
                        }

                        previous = next;
                        next = current.nextNode;
                    } else { 
                        previous = current;
                        current = next;
                        next = next.nextNode;
                    }
                } 
            } while( wasChanged );
        }
    }

The explanation for a "double" code managing the node exchange is that, since you have to change the links among nodes, and this is just a single linked list, then you have to keep track of the previous node (you don't have a header node, either), which the first time is head.

if ( previous != null ) {
    Node sig = next.nextNode;

    previous.nextNode = next;
    next.nextNode = current;
    current.nextNode = sig;
} else {
    Node sig = next.nextNode;

    head = next;
    next.nextNode = current;
    current.nextNode = sig;
}

You can find the code in IdeOne, here: http://ideone.com/HW5zw7

Hope this helps.

Fantastic! Thanks a million for the detailed explanation Balasarq. I was having a really hard time trying to sort it. Btw, I can not vote your answer up as I don't have 15 reputation. lol — Caico, Apr 26 '15 at 20:49
The question is that you had it solved. :-) You can always come back when you have more reputation, if you want. Cheers. — Baltasarq, Apr 27 '15 at 11:06
I know, it's a post of 3 years old, but that doesn't matter your answer @Baltasarq , it helped me tremendous. Thanks!! — Marco de Boer, Dec 13 '18 at 23:24

score 4 · Answer 2 · answered Apr 25 '15 at 19:35

You need to swap the data not just the nodes.

    public void sort() {
    if (size > 1) {
        for (int i = 0; i < size; i++ ) {
            Node currentNode = head;
            Node next = head.nextNode;
            for (int j = 0; j < size - 1; j++) {
                if (currentNode.data > next.data) {
                    int temp = currentNode.data;
                    currentNode.data = next.data;
                    next.data = temp;
                } 
                currentNode = next;
                next = next.nextNode;                   
            } 
        }
    }
}

Thanks Saicharan. You guys are very helpful. – Caico Apr 26 '15 at 20:58 — Caico, Apr 26 '15 at 20:58

score 1 · Answer 3 · answered Dec 27 '18 at 05:57

you can write this methode like this:

class Node {
   int data = 0;
   Node next;

   public Node(int data) {
     this.data = data;
   }
}



public void sort() {

    Node current = head;
    while (current != null) {

        Node second = current.next;
        while (second != null) {

            if (current.data > second.data) {
                int tmp = current.data;
                current.data = second.data;
                second.data = tmp;
            }
            second = second.next;
        }
        current = current.next;
    }
}

Thanks. Your answer helped me solve bubblesort method for a doubly linked list. — CanCoder, Sep 18 '19 at 15:55

Bubble Sort Manually a Linked List in Java

3 Answers3

Linked