Sort Method for Doubly Linked List

Question

Trying to figure out how to sort my doubly linked list. I get a null pointer exception here:

while (temp.getNext()!=null){

Is there a better approach or any advice to get this going the right way?

public void sort() {
    //bubble sort!
    boolean swapped = (head != null);
    while (swapped) {
        swapped = false;

        EntryNode temp = head;

        //can't swap something with nothing
        while (temp.getNext()!=null){
            if (temp.getLastName().compareTo(temp.getNext().getLastName()) > 0) {
                swapped = true;

                //special case for two nodes
                if (size == 2) {
                    //reassign head and tail
                    tail = temp;
                    head = temp.getNext();
                    tail.setPrev(head);
                    head.setNext(tail);
                    tail.setNext(null);
                    head.setNext(null);
                }
                //if swapping is at head
                else {

                    if (temp == head) {
                        head = temp.getNext();
                        temp.setNext(head.getNext());
                        head.getNext().setPrev(temp);
                        head.setPrev(null);
                        head.setNext(temp);
                        temp.setPrev(head);
                    }

                    else {
                        temp.setNext(temp.getNext().getNext());
                        temp.setPrev(temp.getNext());
                        temp.getNext().setNext(temp);
                        temp.getNext().setPrev(temp.getPrev());
                    }
                }
            }
            //loop through list
            temp = temp.getNext();
        }
    }
}

This has to be homework. You don't sort linked lists in the real world. — user207421, Mar 14 '12 at 02:49
@EJP In LISP-based languages you sort linked lists all the time — Óscar López, Mar 14 '12 at 03:04

score 2 · Accepted Answer · edited May 23 '17 at 10:34

2

Use the merge sort algorithm, is often the best choice for sorting a (single or doubly) linked list. There's already a post discussing the relevant implementation issues.

edited May 23 '17 at 10:34

Community

1
1

answered Mar 14 '12 at 02:44

Óscar López

232,561
37
312
386

score 1 · Answer 2 · answered Mar 14 '12 at 02:31

1

I think you should check for:

while(temp != null)

because you are already assigning

temp = temp.getNext()

at the end of the while loop.

answered Mar 14 '12 at 02:31

torrential coding

1,755
2
24
34

score 0 · Answer 3 · answered Mar 14 '12 at 02:38

0

The simple approach is to put the list contents into an array, use Arrays.sort to sort the array, and finally rebuild the list from the sorted array.

answered Mar 14 '12 at 02:38

Stephen C

698,415
94
811
1,216

This approach will need two traversals of the list, ideally you should sort the doubly linked list in one traversal or in O(nlg n)(when using recursion) – Shankhoneer Chakrovarty Mar 14 '12 at 06:16
@ShankhoneerChakrovarty - This is not correct. The OP is doing a bubble sort, and that requires N traversals of the list. Adding 2 more traversals is not going to affect the complexity. It is provably impossible to sort a list of arbitrary comparable objects in better than `O(NlogN)` comparisons ... which roughly equates to `O(logN)` traversals. Once again, adding a constant 2 more traversals doesn't change the complexity. (The sorts that are better than `O(NlogN)` rely on special properties of the domain of values being sorted.) – Stephen C Mar 14 '12 at 06:59

Sort Method for Doubly Linked List

3 Answers3