Sorting Doubly Linked lists

[malik.epperson]

I need help with a homework assignment. I am to create a doubly linked list that reads the numbers from file and then compare the time it takes to sort the numbers using three different sorting algorithms. Here is the code that I have. The algorithms are not working(insertion sort is not sorting and the others are giving many errors) can anyone help?

#ifndef DOUBLYLINKED_H
#define DOUBLYLINKED_H

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Node.h"

template<typename TYPE>
class DoublyLinked
{
public:
    DoublyLinked()
        :headPtr(nullptr), tailPtr(nullptr)
    {
    }

    //destructor
    ~DoublyLinked()
    {
        if (!isEmpty())
        {
            std::cout << "Destroying Nodes..." << std::endl;
            Node<TYPE> *currPtr = headPtr;
            Node<TYPE> *tempPtr = nullptr;

            while (currPtr != nullptr)
            {
                tempPtr = currPtr;
                std::cout << "Deleting: " << tempPtr->data << std::endl;
                currPtr = currPtr->nextPtr;
                delete tempPtr;
            }
        }
        std::cout << "All nodes destroyed." << std::endl;
    }

    void mergeSort()
    {
        clock_t time = 0;
        time = clock();
        mergeSortHelper(headPtr);
        time = clock() - time;
        print();
        std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
    }

    void insertionSort()
    {
        clock_t time = 0;
        time = clock();
        insertionSortHelper(headPtr);
        time = clock() - time;
        print();
        std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
    }

    bool isEmpty() const
    {
        if (headPtr == nullptr && tailPtr == nullptr)
        {
                return true;
        }
        else
            return false;
    }

    void addNode(const TYPE &value)
    {
        Node<TYPE> *newPtr = getNewNode(value);

        if (isEmpty())
            headPtr = tailPtr = newPtr;//add first node to list
        else
        {
            tailPtr->nextPtr = newPtr;
            tailPtr = newPtr;
        }
    }

    bool Delete(TYPE key)
    {
        if (!isEmpty())
        {
            Node<TYPE> *currPtr = headPtr, *tempPtr;

            while (currPtr != nullptr)
            {
                if (currPtr->data == key)
                {
                    if (currPtr->prevPtr == nullptr)
                    {
                        headPtr = currPtr->nextPtr;
                        delete currPtr;
                        std::cout << key << " has been deleted.\n";
                        break;
                    }
                    else if (currPtr->nextPtr == nullptr)
                    {
                        tailPtr = currPtr->prevPtr;
                        delete currPtr;
                        std::cout << key << " has been deleted.\n";
                        break;
                    }
                    else
                    {
                        tempPtr = currPtr->prevPtr;
                        tempPtr->nextPtr = currPtr->nextPtr;
                        delete currPtr;
                        std::cout << key << " has been deleted.\n";
                        break;
                    }
                }
                else
                {
                    tempPtr = currPtr;
                    currPtr = currPtr->nextPtr;
                }
            }
            if (currPtr == nullptr)
            {
                std::cout << key << " is not in the list.\n";
                return false;
            }
        }
        else
        {
            std::cout << "\nThe list is empty. There is nothing to delete.\n";
            return false;
        }
        return true;
    }

    Node<TYPE>* mergeSortHelper(Node<TYPE> *subListA)
    {
        Node<TYPE> *subListB;

        if ((subListA == nullptr) || (subListA->nextPtr == nullptr))
            return nullptr;

        subListB = split(subListA);

        return merge(mergeSortHelper(subListA), mergeSortHelper(subListB));
    }

    Node<TYPE>* merge(Node<TYPE> *subListA, Node<TYPE> *subListB)
    {
        if (subListA == nullptr)
            return subListB;
        else if (subListB == nullptr)
            return subListA;
        else if (subListA->data <= subListB->data)
        {
            subListA->nextPtr = merge(subListA->nextPtr, subListB);
            return subListA;
        }
        else
        {
            subListB->nextPtr = merge(subListA, subListB->nextPtr);
            return subListB;
        }
    }

    Node<TYPE>* split(Node<TYPE> *source)
    {
        Node<TYPE> *secondNode;
        if (source == nullptr || source->nextPtr == nullptr)//in the case there is only one item in the list or the list is empty
        {
            return nullptr;
        }
        else
        {
            secondNode = source->nextPtr;
            source->nextPtr = secondNode->nextPtr;
            secondNode->nextPtr = split(secondNode->nextPtr);
            return secondNode;
        }
    }

    void quickSort()
    {
        clock_t time = 0;
        time = clock();
        quickSortHelper(headPtr, tailPtr);
        time = clock() - time;
        std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
    }

    void quickSortHelper(Node<TYPE> *l, Node<TYPE> *h)
    {
        if (h != nullptr && l != h && l != h->nextPtr)
        {
            Node<TYPE> *p = partition(l, h);
            quickSortHelper(l, p->prevPtr);
            quickSortHelper(p->nextPtr, h);
        }
    }

    Node<TYPE>* partition(Node<TYPE> *l, Node<TYPE> *h)
    {
        //set h as pivot
        int x = h->data;

        Node<TYPE> *i = l->prevPtr;
        for (Node<TYPE> *j = l; j != h; j = j->nextPtr)
        {
            if (j->data <= x)
            {
                i = (i == NULL) ? l : i->nextPtr;
                swap((i->data), (j->data));
            }
        }
        i = (i == NULL) ? l : i->nextPtr;
        swap((i->data), (h->data));
        return i;
    }

    void swap(TYPE a, TYPE b)
    {
        TYPE t = a;
        a = b;
        b = t;
    }

    void insertionSortHelper(Node<TYPE> *q)
    {
        int n;
        Node<TYPE> *curr;
        curr = q;

        if (curr->nextPtr == NULL)
            return;

        while (curr != NULL)
        {
            n = 0;
            Node<TYPE> *ptr = curr;
            Node<TYPE> *temp = curr->nextPtr;
            curr = curr->nextPtr;

            while (temp != NULL && (ptr->data) > (temp->data))
            {
                n++;
                temp = temp->prevPtr;
            }

            if (n)
            {
                (ptr->prevPtr)->nextPtr = ptr->nextPtr;
                if (ptr->nextPtr != nullptr)
                {
                    (ptr->nextPtr)->prevPtr = ptr->prevPtr;
                }
                if (temp == nullptr)
                {
                    temp = *q;
                    ptr->prevPtr = nullptr;
                    ptr->nextPtr = temp;
                    ptr->nextPtr->prevPtr = ptr;
                    *q = ptr;
                }
                else
                {
                    temp = temp->nextPtr;
                    (temp->prevPtr)->nextPtr = ptr;
                    ptr->prevPtr = temp->prevPtr;
                    temp->prevPtr = ptr;
                    ptr->nextPtr = temp;
                }
            }
        }
    }

    void print() const
    {
        if (isEmpty())
        {
            std::cout << "The list is empty." << std::endl;
            return;
        }

        Node<TYPE> *currPtr = headPtr;

        std::cout << "The list contains: ";

        while (currPtr != nullptr)
        {
            std::cout << currPtr->data << ' ';
            currPtr = currPtr->nextPtr;
        }
        std::cout << "\n\n";
    }

    private:
        Node<TYPE> *headPtr; //pointer to first node in the list
        Node<TYPE> *tailPtr; //pointer to the last node in the list

        Node<TYPE> *getNewNode(const TYPE &value)
        {
            return new Node<TYPE>(value);
        }
};
#endif

[Ancient Dragon]

Rather than attempting to swap link pointers it is a lot easier to swap the data and leave all the pointers alone.

[malik.epperson]

How do I go about doing that?

[rubberman]

An approach I have used in the past quite effectively was to create an array with the data in the list, sort that, and then use the sorted array to recreate the linked list. Sorting a linked list directly is a real PITA, and AD's suggestion is one possible method. BTW, what ARE the 3 sorting algorithms you are to use. Obviously, from your post, an insertion sort is one. I am going to assume (possibly wrongly) that the others are a bubble sort, and a quicksort?

For the insertion sort, walk through the list and insert the data into an array at the appropriate position (possibly needing to move the items below it down one element, hence the "insertion"). Then you can move the data from the array back into the list on a 1-to-1 basis.

[malik.epperson]

I can choose any sort that I want. I tried to set up merge sort, quicksort and insertion sort.

[rubberman]

Ok. Then for all of these, using the list-to-array-sort-back-to-list methodology is the most straight forward in my experience. Using qsort() for an array is trivial - you just need a comparison function, which is also valid for bubble and insertion sorts. For your case, you will likely find that the insertion sort is the most efficient, if implemented properly - consider head/tail optimizations for large lists. Use memmove() to move the data elements down one index location in the array instead of moving each separately from the insertion point. Think about these points and see what you can do to implement them, and at that point I will critique your work if you are still having problems.

Finally, consider writing out the algorithms you are going to implement in pseudo code. I will be happy to comment on that as well.

[malik.epperson]

is this a good code to convert the list to a vector (i have to sort lists of different sizes of integers)

TYPE* convertToVector(Node<TYPE> headPtr)
    {
        Node<TYPE> currPtr = headPtr;
        while (currPtr != NULL)
        {
            int i = 0;
            vector<TYPE> list;
            list[i] = currPtr->data;
            i++;
            currPtr = currPtr->nextPtr;
        }

        return list;
    }

[Ancient Dragon]

How do I go about doing that?

Easy -- whenever a swap is needed swap the data that's within the two nodes instead of the pointers. If there are several data items in the nodes then I'd put the data in a structure and the structure object with the node. That will make swaping much easier.

struct data
{
   int x,y,z;
   char stuff[80];
};

struct node
{
   struct node* next;
   struct node* prev;
   struct data dat;
}

void swap(struct node* n1, struct node* n2)
{
   struct data temp;
   temp = n1->dat;
   n1->dat = n2->dat;
   n2->dat = temp;

}

[malik.epperson]

I believe that I have got a hold of converting a linked list into a vector, but how do I take the sorted vector and put it back into a new linked list? If i use the add function wouldnt that just add to the unsorted linked list?

[malik.epperson]

Here is some code adjustments I have made to mergesort and I have created functions that convert the linked list to a vector and one that converts the sorted vector back to the linked list.

#ifndef DOUBLYLINKED_H
#define DOUBLYLINKED_H

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <time.h>
#include "Node.h"

template<typename TYPE>
class DoublyLinked
{
public:
    DoublyLinked()
        :headPtr(nullptr), tailPtr(nullptr),
    {
        int count = 0;
    }

    //destructor
    ~DoublyLinked()
    {
        if (!isEmpty())
        {
            std::cout << "Destroying Nodes..." << std::endl;
            Node<TYPE> *currPtr = headPtr;
            Node<TYPE> *tempPtr = nullptr;

            while (currPtr != nullptr)
            {
                tempPtr = currPtr;
                std::cout << "Deleting: " << tempPtr->data << std::endl;
                currPtr = currPtr->nextPtr;
                delete tempPtr;
            }
        }
        std::cout << "All nodes destroyed." << std::endl;
    }

    void mergeSort()
    {
        clock_t time = 0;
        time = clock();
        vector <TYPE> list = convertToVector(headPtr);
        mergeSortHelper(list);
        convertToLinkedList(list);
        time = clock() - time;
        print();
        std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
    }

    void insertionSort()
    {
        clock_t time = 0;
        time = clock();
        insertionSortHelper(headPtr);
        time = clock() - time;
        print();
        std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
    }

    bool isEmpty() const
    {
        if (headPtr == nullptr && tailPtr == nullptr)
        {
                return true;
        }
        else
            return false;
    }

    void addNode(const TYPE &value)
    {
        Node<TYPE> *newPtr = getNewNode(value);

        if (isEmpty())
            headPtr = tailPtr = newPtr;//add first node to list
        else
        {
            tailPtr->nextPtr = newPtr;
            tailPtr = newPtr;
        }
        count = count + 1;
    }

    bool Delete(TYPE key)
    {
        if (!isEmpty())
        {
            Node<TYPE> *currPtr = headPtr, *tempPtr;

            while (currPtr != nullptr)
            {
                if (currPtr->data == key)
                {
                    if (currPtr->prevPtr == nullptr)
                    {
                        headPtr = currPtr->nextPtr;
                        delete currPtr;
                        std::cout << key << " has been deleted.\n";
                        break;
                    }
                    else if (currPtr->nextPtr == nullptr)
                    {
                        tailPtr = currPtr->prevPtr;
                        delete currPtr;
                        std::cout << key << " has been deleted.\n";
                        break;
                    }
                    else
                    {
                        tempPtr = currPtr->prevPtr;
                        tempPtr->nextPtr = currPtr->nextPtr;
                        delete currPtr;
                        std::cout << key << " has been deleted.\n";
                        break;
                    }
                }
                else
                {
                    tempPtr = currPtr;
                    currPtr = currPtr->nextPtr;
                }
            }
            if (currPtr == nullptr)
            {
                std::cout << key << " is not in the list.\n";
                return false;
            }
        }
        else
        {
            std::cout << "\nThe list is empty. There is nothing to delete.\n";
            return false;
        }
        return true;
    }

    vector<TYPE> convertToVector(Node<TYPE> *Ptr)
    {
        Node<TYPE> *currPtr = headPtr;
        while (currPtr != NULL)
        {
            int i = 0;
            vector<TYPE> list(count);
            list[i] = currPtr->data;
            i++;
            currPtr = currPtr->nextPtr;
        }

        return list;
    }

    void convertToLinkedList(vector<TYPE> &vec)
    {
        Node<TYPE> *currPtr = headPtr, *tempPtr;
        while (currPtr != NULL)
        {
            if (vec[0] == currPtr->data)
            {
                headPtr = currPtr;//establish first number of sorted vector as head node
                currPtr->prevPtr == nullptr;// ensure node is head node as it previous pointer will point to nothing
                tempPtr = currPtr;
                currPtr = currPtr->nextPtr;
                break;
            }
            else
            {
                currPtr = currPtr->nextPtr;
            }
        }
        for (int i = 1; i < vec.size(); i++)
        {
            while (currPtr != NULL)
            {
                if (vec[i] == currPtr->data)
                {
                    tempPtr->nextPtr = currPtr;
                    currPtr->prevPtr = tempPtr;
                    tempPtr = currPtr;
                    currPtr = currPtr->nextPtr;

                }
                else
                    currPtr = currPtr->nextPtr;
            }
        }
    }

    vector <TYPE>* mergeSortHelper(vector<TYPE> *list)
    {
        vector<TYPE> left, right, result;
        if (list.size() <= 1) {
            return list;
        }
        int middle = (list.size() / 2);
        for (int i = 0; i < middle; i++) {
            left.push_back(list[i]);
        }
        for (int i = middle; i < list.size(); i++) {
            right.push_back(list[i]);
        }
        left = mergeSort(left);
        right = mergeSort(right);
        result = merge(left, right);
        return result;
    }

    vector<TYPE> merge(const vector<TYPE> &left, const vector<TYPE> &right)
    {
        vector<TYPE> result;
        const int leftSize = left.size(), rightSize = right.size();
        int leftPos = 0, rightPos = 0;
        while (leftPos < leftSize && rightPos < rightSize) {
            if (left[leftPos] < right[rightPos]) {
                result.push_back(left[leftPos]);
                leftPos++;
            }
            else {
                result.push_back(right[rightPos]);
                rightPos++;
            }
        }
        if (leftPos == leftSize) {
            while (rightPos < rightSize) {
                result.push_back(right[rightPos]);
                rightPos++;
            }
        }
        else {
            while (leftPos < leftSize) {
                result.push_back(left[leftPos]);
                leftPos++;
            }
        }
        return result;
    }

    void quickSort()
    {
        clock_t time = 0;
        time = clock();
        quickSortHelper(headPtr, tailPtr);
        time = clock() - time;
        std::cout << "The time it took to complete this function is " << ((float)time / CLOCKS_PER_SEC) << " seconds.\n";
    }

    void quickSortHelper(Node<TYPE> *l, Node<TYPE> *h)
    {
        if (h != nullptr && l != h && l != h->nextPtr)
        {
            Node<TYPE> *p = partition(l, h);
            quickSortHelper(l, p->prevPtr);
            quickSortHelper(p->nextPtr, h);
        }
    }

    Node<TYPE>* partition(Node<TYPE> *l, Node<TYPE> *h)
    {
        //set h as pivot
        int x = h->data;

        Node<TYPE> *i = l->prevPtr;
        for (Node<TYPE> *j = l; j != h; j = j->nextPtr)
        {
            if (j->data <= x)
            {
                i = (i == NULL) ? l : i->nextPtr;
                swap((i->data), (j->data));
            }
        }
        i = (i == NULL) ? l : i->nextPtr;
        swap((i->data), (h->data));
        return i;
    }

    void swap(TYPE a, TYPE b)
    {
        TYPE t = a;
        a = b;
        b = t;
    }

    void insertionSortHelper(Node<TYPE> *q)
    {
        int n;
        Node<TYPE> *curr;
        curr = q;

        if (curr->nextPtr == NULL)
            return;

        while (curr != NULL)
        {
            n = 0;
            Node<TYPE> *ptr = curr;
            Node<TYPE> *temp = curr->nextPtr;
            curr = curr->nextPtr;

            while (temp != NULL && (ptr->data) > (temp->data))
            {
                n++;
                temp = temp->prevPtr;
            }

            if (n)
            {
                (ptr->prevPtr)->nextPtr = ptr->nextPtr;
                if (ptr->nextPtr != nullptr)
                {
                    (ptr->nextPtr)->prevPtr = ptr->prevPtr;
                }
                if (temp == nullptr)
                {
                    temp = *q;
                    ptr->prevPtr = nullptr;
                    ptr->nextPtr = temp;
                    ptr->nextPtr->prevPtr = ptr;
                    *q = ptr;
                }
                else
                {
                    temp = temp->nextPtr;
                    (temp->prevPtr)->nextPtr = ptr;
                    ptr->prevPtr = temp->prevPtr;
                    temp->prevPtr = ptr;
                    ptr->nextPtr = temp;
                }
            }
        }
    }

    void print() const
    {
        if (isEmpty())
        {
            std::cout << "The list is empty." << std::endl;
            return;
        }

        Node<TYPE> *currPtr = headPtr;

        std::cout << "The list contains: ";

        while (currPtr != nullptr)
        {
            std::cout << currPtr->data << ' ';
            currPtr = currPtr->nextPtr;
        }
        std::cout << "\n\n";
    }

    private:
        Node<TYPE> *headPtr; //pointer to first node in the list
        Node<TYPE> *tailPtr; //pointer to the last node in the list

        Node<TYPE> *getNewNode(const TYPE &value)
        {
            return new Node<TYPE>(value);
        }
};
#endif

I am getting alot of errors though andI dont know how to correct them. here is the errors I am getting.

Error 2 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int doublylinked.h 140
Error 6 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int doublylinked.h 191
Error 9 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int doublylinked.h 210
Error 3 error C2334: unexpected token(s) preceding '{'; skipping apparent function body 141
Error 7 error C2334: unexpected token(s) preceding '{'; skipping apparent function body 192
Error 10 error C2334: unexpected token(s) preceding '{'; skipping apparent function body doublylinked.h 211
Error 1 error C2143: syntax error : missing ';' before '<' doublylinked.h 140
Error 5 error C2143: syntax error : missing ';' before '<' doublylinked.h 191
Error 8 error C2143: syntax error : missing ';' before '<' 210
Error 4 error C2061: syntax error : identifier 'vector' doublylinked.h 155
Error 11 error C1903: unable to recover from previous error(s); stopping compilation doublylinked.h 141

[rubberman]

Well, here is one problem (starting at line 140):

vector<TYPE> convertToVector(Node<TYPE> *Ptr)
{
    Node<TYPE> *currPtr = headPtr;
    while (currPtr != NULL)
    {
        int i = 0;
        vector<TYPE> list(count);
        list[i] = currPtr->data;
        i++;
        currPtr = currPtr->nextPtr;
    }
    return list;
}

// This would be better.
vector<TYPE>* convertToVector(Node<TYPE> *headPtr)
{
    vector<TYPE>* list = new vector<TYPE>;
    Node<TYPE> *currPtr = headPtr;
    while (currPtr != NULL)
    {
        list->push_back(currPtr->data);
        currPtr = currPtr->nextPtr;
    }
    return list;
}

Note that inside your look, you are creating a new list on each iteration. You need to create the list outside of the loop. Also, by creating an object on the heap (vector<TYPE>*) and returning the pointer, you avoid the overhead of copying the entire list on return.

Also note my change in the function signature. I assume you meant to pass in the head pointer? :-)

Anyway, these are common issues in your code. You are getting there, but you have work to do yet! Keep it up.

[rubberman]

Do note that I don't try to solve all of your problems in one post. However, I do try to get you to see where some of your fundamental problems lay.

Oh, and here is a link to the www.cplusplus.com documentation on list sorting: http://www.cplusplus.com/reference/algorithm/sort/

[malik.epperson]

I am having issues with the function that you just helped me with. I am getting th two following errors on line 16 of the code you posted,

Error   1   error C2143: syntax error : missing ';' before '<'
Error   2   error C4430: missing type specifier - int assumed. Note: C++ does not support default-int

[rubberman]

Please show what code you actually wrote. This line is wrong (my bad): vector<TYPE>* list = new vector<TYPE>;

It should be vector<TYPE>* list = new vector<TYPE>();
Sorry about that! :-)

That still won't shut up the compiler - fun with templates!

[malik.epperson]

I figured everything out and got the sorts to work! Thanks eeryone for your help!!!