DoublyLinkedList quickSort

[Dane2259]

I'm trying to do a quickSort with a Doubly LinkedList. I can partition the original list into a lower and upper sublist, but have been unsuccessful going any further. Below is the code for the class DoublyLinkedList. The methods that perform the quick sort are at the bottom (partition, recQuickSort, and quickSort). I'll posted the main method in another post. Any suggestions would be appreciated. Thanks in advance.

public class DoublyLinkedList
{
    public class DoublyLinkedListNode
    {
        public int info;
        public DoublyLinkedListNode next;
        public DoublyLinkedListNode back;

            //Default Constructor
            //Postcondition: info = 0;
            //                    next = null; back = null;
        public DoublyLinkedListNode()
        {
            info = 0;
            next = null;
            back = null;
        }
        public DoublyLinkedListNode(int item)
        {
            info = item;
            next = null;
            back = null;
        }
        public void displayInfo()
        {
            System.out.print(info + " ");
        }
    }

    protected int count;
    protected DoublyLinkedListNode first;
    protected DoublyLinkedListNode last;

    public DoublyLinkedList()
    {
        first = null;
        last = null;
        count = 0;
    }

    public void initializeList()
    {
        first = null;
        last = null;
        count = 0;
    }

    public boolean isEmpty()
    {
        return (first == null);
    }

    public int length()
    {
        return count;
    }

    public void print()
    {
        DoublyLinkedListNode current = first;

        while (current != null)
        {
            current.displayInfo();
            current = current.next;
        }//end while
    }//end print

    public void insertNode(int insertItem)
    {
        DoublyLinkedListNode newNode = new DoublyLinkedListNode(insertItem);
        if (isEmpty())
        {
            first = newNode;
            last = newNode;
            count++;
        } 
        else
        {
            last.next = newNode;
            newNode.back = last;
        }
        last = newNode;
    }

    public DoublyLinkedListNode partition(DoublyLinkedList list,
                            DoublyLinkedListNode first, DoublyLinkedListNode last)
    {
        DoublyLinkedListNode smallIndex = first;
        DoublyLinkedListNode index = smallIndex.next;
        DoublyLinkedListNode temp = new DoublyLinkedListNode();
        int pivot = first.info;

        while (index != last.next)
        {
            if((index.info) < pivot)
            {
                smallIndex = smallIndex.next;
                temp.info = index.info;
                index.info = smallIndex.info;
                smallIndex.info = temp.info;
            }
            index = index.next;
        }
        temp.info = first.info;
        first.info = smallIndex.info;
        smallIndex.info = temp.info;
        System.out.print("The list in partition is: "); list.print();
        System.out.print("\n");
        return smallIndex;
    }

    public void recQuickSort(DoublyLinkedList list, DoublyLinkedListNode first,
                                     DoublyLinkedListNode last)
    {
        while(first != last)
        {
            DoublyLinkedListNode pivotLocation = partition(list, first, last);
            recQuickSort(list, first, pivotLocation.back);
            recQuickSort(list, pivotLocation.next, last);
        }
    }

    public void quickSort(DoublyLinkedList list)
    {
        recQuickSort(list, list.first, list.last);
    }
}

[Taywin]

From a quick glance on your program, line 75 is not needed. Also, line 76 will cause a problem because you are not counting nodes after you have already initialise the list once.

Also, you may need to implement the swap() method before you could go further. The sort requires to have a swap() method. It is critical to be able to deal with swap method.

PS: In swap, you will differently deal with a node when it's back or next value is null.