Beginner with C++ and goofy run time problem with DBL Linked List

[kharri5]

Greetings To all!

To whomever, an advanced thank you if you help me. I am a Java programmer initially, but I have begun learning C++ and am doing something with a Double Linked List (Error occurs whether it's double or single, I teste it). Filling the contents of the list I have managed, but when I try and print each item of the list doing this, I get a run time error, which when I go to debugger looks like its trying to access a NULL

=========================================================
ListNode *p = head;

cout << "[ ";

for( ; p != NULL; p = p->next)
{
cout << p->data << " ";
}

cout << "]"

=========================================================

Now this code works fine in Java, but in C++ it makes a stink at me, a runtime stink. I shouldn't be overstepping the boundaries of the list, becuase the stopping condition in the for loop should catch before that happens, but I'm not sure what is going on. I'm stabbing at it being a NULL access that's not allowed, but I'm not sure that this is the error, becuase C++ is so fantastically wonderful at describing its errors of course(hopefully catching the sarcasm here)

Anywho, if some kind soul might shed some light on this stupid poor novice, I would appreciate becuase I'm sure it's something I missed that is probably trivial. (I tend to do that a lot). Thanks again!

[Narue]

>becuase C++ is so fantastically wonderful at describing its errors of course
Java errors are no less cryptic, you're just used to them.

>I shouldn't be overstepping the boundaries of the list
You shouldn't, but you probably are if you fail to terminate the list at any point with NULL. For example, if the list is terminated by an uninitialized pointer, it probably won't be NULL, so the condition will fail and you'll walk beyond the end of the list and get an access violation. I would imagine that this is the case since Java initializes references to null, and if you were used to that you may not be watching out for an uninitialized pointer in C++.

Can you post a complete program that exhibits the problem?

[kharri5]

Ah touche! Indeed Java errors can be quite convoluted as well...

Anyway getting on with it. The program right now is quite small as it is in test form. Basically I have the .h file of course with the declarations, but I can assume, I hope, you don't need to see that (If it is necessary let me know). So here are the cpp for main and the list class

There are the two functions, which I will display here below:

void SortedList::Insert(string s)
{
    if(head == NULL)
    {
        head = tail = new ListNode;
        head->data = s;
    }

    else
    {
        ListNode *temp = tail;
        string comp = temp->data;
        char c;

        c = s[0];

        if( (int)c > (int)comp[0] ) // for purposes of alphabetic post insertion
        {
            temp->next = new ListNode;
            temp->next->data = s;
            tail = temp->next;
            tail->prev = temp;
        }
    }
}

void SortedList::PrintIt()
{
    ListNode *p = head;

    cout << "[ ";

    for(; p != NULL; p = p->next)
    {
        cout << p->data << " ";
    }

    cout << "]";
}

And then the main function simply calls like so:

SortedList x;

int main()
{
    string a = "apple";
    string o = "orange";
    string p = "peach";
    string f = "fruit"; // "fruit" shouldn't get into the list
    x.Insert(a);
    x.Insert(o);
    x.Insert(p);
    x.Insert(f);

    x.PrintIt();

    return 0;
}

Thank you for answering my thread, and if I can provide any more information that might increase understanding of my current problem let me know. If you can figure out my problem, I would be very open to constructive suggestions and comments that might guide me, should you be willing to give them. Thanks again.

[Drowzee]

Ya might want to put some code tags in there.
That's awfully hard to read.

Anyway, is SortedList a custom class/struct of yours?
Might be nice to have that code, too...

And if it's not available, methinks we've found the problem.

[kharri5]

Darn, it did not post out the way I wanted it to. That is decidedly tough to read.

Yes, the SortedList is a custom class defined in the .h file...I will repost cleaner post here. The whole workspace worth.

SortedList.h File is as follows:

==========================================================

#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

/*
 *  SortedList class
 *    
 *  A SortedList is a collection of strings in alphabetical order
 * 
 *  Operations:
 *     constructor Initialize the list to be empty.
 *     Insert      Add a given string to the list.
 *     Print       Print (to the given ostream) the strings in the list in
 *                 order, enclosed in square brackets, separated by spaces.
 *     Lookup      Return the number of times a given string occurs in the list.
 */

class SortedList 
{
  public:

    // constructor
    SortedList();

    // modifiers
    void Insert(string s);

    // other operations
    int Lookup(string s);
    void Print(ostream &output);
	void PrintIt();

  private:

    struct ListNode 
	{
       string data;
	   ListNode *prev;
       ListNode *next;
    };
    
    // pointer to the first node of the list
    ListNode *head;
	ListNode *tail;
};

The SortedList.cpp file is as follows:

=========================================================

#include "SortedList.h"

using namespace std;
/*
*
* Soretd List Constructor
*
*/

SortedList::SortedList()
{
	head = tail = NULL;
}

/**
 * function: Insert
 * parameters: String
 * returns: void
 *
 */

void SortedList::Insert(string s)
{
	if(head == NULL)
	{
		head = tail = new ListNode;
		head->data = s;
	}

	else
	{
	    ListNode *temp = tail;
		ListNode *prevM = NULL;
	    string comp = temp->data;
	    char c;

	    c = s[0];

	    if( (int)c > (int)comp[0] )
		{
		    temp->next = new ListNode;
		    temp->next->data = s;
			tail = temp->next;
			tail->prev = temp;
		}
	}
}

void SortedList::PrintIt()
{
	ListNode *p = head;

	cout << "[ ";

	for(; p != NULL; p = p->next)
	{
		cout << p->data << " ";
	}

	cout << "]";
}

And the main file is:

=========================================================

#include "SortedList.h"

SortedList x;

int main()
{
	string a = "apple";
	string o = "orange";
	string p = "peach";
	string f = "fruit";
	x.Insert(a);
	x.Insert(o);
	x.Insert(p);
	x.Insert(f);

	x.PrintIt();

	return 0;
}

=========================================================

And that is the whole code so far. Hope that looks cleaner, sorry about the previous posting of it

[Drowzee]

You're creating nodes without tracking all your pointers. Always, always, ALWAYS set your next pointer to NULL once you've made a new node.

void SortedList::Insert(string s)
{
	if(head == NULL)
	{
		head = tail = new ListNode;
		head->data = s;
                head->next = NULL;//Good practice, in my opinion.
                head->prev = NULL;

	}

	else
	{
	    ListNode *temp = tail;
		ListNode *prevM = NULL;
	    string comp = temp->data;
	    char c;

	    c = s[0];

	    if( (int)c > (int)comp[0] )
		{
		    temp->next = new ListNode;
		    temp->next->data = s;
			tail = temp->next;
			tail->prev = temp;
			tail->next = NULL; //Here was where it went wrong.
		}
	}
}

[Narue]

Add this to your declaration of ListNode:

ListNode(): prev(0), next(0) {}

That will fix the issue with access violations by properly terminating each node, but your Insert algorithm is incorrect. Remember that there are three cases when inserting into a sorted list: when the list is empty, when the new node is less than the head, and when the new node is greater. If you don't account for all three of these cases, your insertion is broken:

struct ListNode 
{
  string data;
  ListNode *prev;
  ListNode *next;

  ListNode(): prev(0), next(0) {}
  ListNode(const string& s, ListNode *p, ListNode *n)
    : data(s), prev(p), next(n) {}
};

void SortedList::Insert(string s)
{
  if(head == NULL)
  {
    head = tail = new ListNode;
    head->data = s;
  }
  else if (s < head->data)
  {
    head = new ListNode(s, 0, head);
  }
  else
  {
    ListNode *temp = head;

    while (temp->next != 0 && temp->next->data < s)
      temp = temp->next;

    temp->next = new ListNode(s, temp, temp->next);

    if (temp == tail)
      tail = temp->next;
  }
}

>As I suspected
:rolleyes:

[Drowzee]

Beginning ego deflation process...
...
.....
......
Process complete.
Please don't hurt me.

[kharri5]

Thank you for your help...I salute you. I am now taking the items into account and will be implementing the problem fixes later tonight. Thanks again.

Oi, Akan zya nai desu yo!

[Drowzee]

I don't feel like I can quite take credit for my less-optimal solution... Bleh...

Narue, that

ListNode(): prev(0), next(0) {}

You posted...
What is that called? Is that a variant of a constructor?

... I don't see that usage of it in my books over here.

[Dave Sinkula]

>What is that called?
An initialization list.

[Drowzee]

Yeah, and this thing calls itself a complete reference... hmph.

Thanks, Dave. That will probably come in useful very soon.

[Dave Sinkula]

Yeah, and this thing calls itself a complete reference... hmph.

Please tell us it's not an old Schildt.

[Drowzee]

... It is. So, I'm missing something, I guess?

[Dave Sinkula]

Herb Schildt's writing is easy to follow and understand. Unfortunately his earlier works were full of bad coding practice, newb errors, and misconceptions. I hear his work is getting better in later editions, but...

Well here are a few examples:
http://catb.org/~esr/jargon/html/B/bullschildt.html
http://www.plethora.net/~seebs/c/c_tcr.html
http://www.accu.org/bookreviews/public/reviews/c/c002217.htm
http://www.cs.technion.ac.il/users/yechiel/CS/BadBooksC+C++.html

[Drowzee]

So, third edition, Copyright 98 is one of the old, crummy ones?

[Narue]

>So, third edition, Copyright 98 is one of the old, crummy ones?
As far as I (and many others) are concerned, all of his books are crummy, and the chances of a good one coming out are incredibly slim.

>Oi, Akan zya nai desu yo!
Prove it. ;)

[Drowzee]

I'm glad this isn't my book, then. And that I haven't been contaminated by it too much.

But should I tell the guy who is insisting I read it to help me in this project? hmm...

[Narue]

>But should I tell the guy who is insisting I read it to help me in this project?
Wiley published the C++ standard. Buy that, then hit your friend with it until he realizes the error of his ways. Or until he's a bloody pulp, whichever comes first.

[Drowzee]

Nah. He can buy it. He's an employee. I'm just an intern. And he was getting on my case that I didn't seem to be learning code well enough, so... yeeeaah. Not a good idea to assault the people here. Pay's sweet, I need something on my resume that ain't scholastic, and I really do need the practice in coding and writing documents.

I guess I'll tell him. Point him to Dave's links. Hope he doesn't think I'm too 'uppity'.

[Narue]

Send him here if he gives you any lip. I'll be happy to set him straight. :)

[Drowzee]

Fortunately, he was understanding, and after I had him go through the links, he said he 'didn't want to spread bad information', and tried to take the book. But I think, in small doses, it's probably okay. I might go get Bjarne Stroustrup's text at some point... or maybe a copy of the standards, if that would help.
So, for the moment, the bullschlidt sits on the desk. I'm going to be double-checking my work against other sources, of course...