Doubly Linked List InsertInOrder Algorithm

[drummin2somebeats]

Hi. I'm getting a segmentation fault when I get to the loop in main trying to print out the characters. I think my insertInOrder and insert functions are wrong, but I just can't figure out anything. I'm new to double linked lists and new to templates. Oh, and I ignored all the other functions in the LinkedList class because they were working last time I checked. So I narrowed it down to the insert and insertInOrder. Any help would be appreciated.
Thanks
--
James


LinkedList.h

template <class T>
void LinkedList<T>::insertInOrder(T value, bool (*charcmp)(char, char))
{
    if(!empty())
    {
        curr = front;
        while(charcmp(curr -> data, value))
        {
            curr = curr -> next;
        }
        curr = curr -> prev;
        insert(value);
    }
    else
        pushback(value);
}

template <class T>
void LinkedList<T>::insert(T value)
{
    if(!empty())
    {
        node_t<T> *NewT;
        NewT = new node_t<T>;
        NewT -> data = value;
        if(curr -> prev != NULL && curr -> next != NULL)
        {
            NewT -> prev = curr;
            NewT -> next = curr -> next;
            curr -> next = NewT;
            curr = curr -> next;
            curr = curr -> next;
            curr -> prev = NewT;
            N++;
        }
        else if(curr -> prev == NULL)
            pushfront(value);
        else if(curr -> next == NULL)
            pushback(value);
    }
    else
        pushback(value);
}

main.cpp

#include "LinkedList.h"
#include <iostream>
using namespace std;

bool charcmp(char a, char b)
{
    return (a < b);
}

int main()
{
    LinkedList<char> clist;

    clist.insertInOrder('g',charcmp);
    clist.insertInOrder('n',charcmp);
    clist.insertInOrder('i',charcmp);
    clist.insertInOrder('t',charcmp);
    clist.insertInOrder('x',charcmp);
    clist.insertInOrder('u',charcmp);
    clist.insertInOrder('e',charcmp);
    clist.insertInOrder('f',charcmp);
    clist.insertInOrder('b',charcmp);
    clist.insertInOrder('a',charcmp);
    clist.insertInOrder('e',charcmp);
    clist.popback();

    clist.begin();
    for(int i=0; i<clist.size(); i++)
    {
        cout<<*clist<<" ";
        clist++;
    }
    cout<<endl;
    cout<<"should have abeefgintux"<<endl<<endl;
}

[firedraco]

Shouldn't your cmp function be:

bool (*charcmp)(T, T)? (Possibly const references on the Ts)

Anyway, check your insertInOrder(). What happens if you have one element, say 'a', and you are trying to add 'z'? You'd check it against the front, it would be true, you'd go to the next element (NULL I assume), then the next check would crash.

Also, using the member variable curr to store state seems kind of hard to understand. Just make a temporary variable and pass it around if you need it.

[drummin2somebeats]

Thanks for the reply.
About the cmp function, the entire main was written by the teacher and he wrote the cmp function like that.

But I changed up my insertInOrder (I might have messed it up even more)

template <class T>
void LinkedList<T>::insertInOrder(T value, bool (*charcmp)(char, char))
{
    if(!empty())
    {
        curr = front;
        while(charcmp(curr -> data, value) && curr != NULL)
        {
                curr = curr -> next;
        }
        if(curr == NULL)
            pushback(value);
        else
        {
            curr = curr -> prev;
            insert(value);
        }
    }
    else
        pushback(value);
}

I'm sorry if I'm making some stupid mistake. I just can't figure this thing out.

EDIT: Ok, so now the insertinOrder works, I guess. It doesn't segmentation fault at least. But the stuff is out of order. But then it segmentation faults later on in the program when I try to clear the list. I'm working on my clear() function right now

[firedraco]

I think you want your cur != NULL check before your cur->data check otherwise if curr is NULL you will crash before you can check if it is NULL.

Also, what happens if front > value? You will set curr to cur->prev and that will be NULL as well.

Maybe you should try to write out what the insertInOrder function should be doing in psuedocode first, then turn it into C++.

[drummin2somebeats]

Am I getting closer? I've been screwing with this code for 3 days. I've asked one of my classmates and both of us put together can't figure out the insertInOrder function. We have the rest of the program figured out, but it's this one function.

template <class T>
void LinkedList<T>::insertInOrder(T value, bool (*charcmp)(char, char))
{
    if(!empty())
    {
        begin();
        while(curr != NULL && charcmp(curr -> data, value))
        {
            curr = curr -> next;
        }
        if(curr -> prev == NULL)
            pushfront(value);
        else if(curr -> next == NULL)
            pushback(value);
        else
            insert(value);
    }
    else
        pushfront(value);
}

thanks
--
James

[firedraco]

begin();

What does this do?

Anyway, it looks OK to me...is there still a problem now?

[drummin2somebeats]

Here's begin()

template <class T>
void LinkedList<T>::begin()
{
        curr = front;
}

MAJOR EDIT:

I fixed it! hahaha!
If anyone stumbles upon this post later on, here's the final insertInOrder:

template <class T>
void LinkedList<T>::insertInOrder(T value, bool (*charcmp)(char, char))
{
    if(!empty())
    {
        begin();
        while(curr != NULL && charcmp(curr -> data, value))
        {
            next();
        }
        node_t<T> *NewT;
        NewT = new node_t<T>;
        NewT -> data = value;
        if(curr -> prev != NULL)
        {
            NewT -> next = curr;
            NewT -> prev = curr -> prev;
            curr -> prev = NewT;
            previous();
            previous();
            curr -> next = NewT;
            N++;
        }
        else if(curr -> prev == NULL)
            pushfront(value);
    }
    else
        pushfront(value);
}

Thanks to firedraco for your help :)
--
James