Solved

linked list of my own datatype?

Posted on 2000-03-04
14
189 Views
Last Modified: 2010-04-02
I'm trying to create a linked-list that will hold instances of classes that I created.  I'm very new to linked lists and only a bit more experienced with classes.  I'm stuck on a segmentation fault that seems to be happining in the constructor when I create the object for the first item in the list.  The Object class works fine.  Here is a copy of the class-definition, class, and the test program .... PLEASE HELP!!!
:-)
ps.  

list.h
#ifndef LIST_H
#define LIST_H
#include <iostream.h>
#include "/home/mud/classes/object/object.cpp"

template<class T>
class List;

template<class T>
class Node
{
        friend List<T>;
        private:
                T item;
                Node *next;
};

template<class T>  
class List
{
public:
        List();
        ~List();

        void add(T new_item);
        void kill(int x);


private:
        Node<T>* head;

};


#endif // LIST_H

list.cxx

#ifndef LIST_CXX
#define LIST_CXX
#include <iostream.h>
#include <stdlib.h>
#include "list.h"
#include "/home/mud/classes/object/object.cpp"

template<class T>
List<T>::List()
{
        // create an empty instance of the object requested
        T empty(4);

        head = new Node<T>;
        head->item = empty;
        head->next = NULL;
}

template<class T>
List<T>::~List()
{
        Node<T>* p;
        while(head->next != NULL)
        {
                p = head->next;
                delete head;
                head = p;
        }
        delete head;
}

template<class T>
void List<T>::add(T new_item)
{
        // create an instance of the object
        T x(new_item);

        // create two node pointers
        Node<T>* q;
        Node<T>* p;

        // create an empty node
        p = new Node<T>;
        p->item = 0;
        p->next = NULL;

        if(head->next == NULL)
        {
                head->item = x;
                head->next = p;
        }
        else
        {
                q = head;

                do
                {
                        q = q->next;
                }while(q->next != NULL);

                q->item = x;
                q->next = p;
        }

}

template<class T>
void List<T>::kill(int x)
{
        Node<T>* p;
        Node<T>* q;

        p = head;

        if(head->item.getNum() == x)
        {
                head = head->next;
        }
        else
        {
                while(p->item.getNum() != x)
                {
                        q = p;
                        p = p->next;
                }

                q->next = p->next;
        }

        delete p;

}

#endif // LIST_CXX

list.cpp

#ifndef OBJ_LIST
#define OBJ_LIST
#include <iostream.h>
#include "list.h"
#include "list.cxx"
#include "/home/mud/classes/object/object.cpp"

int main()
{
        List<Object> first_list;

     
//      first_list.kill(3);
     
        return 0;

}

#endif  // OBJ_LIST
0
Comment
Question by:scottd1978
  • 7
  • 7
14 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 2583735
I'll give you some pointers (no pun intended) to get you going again.  Then work on it and ask again if you need more help.   (and post the new code if you neeed more help0

in  the constructor.

List<T>::List()
{
// create an empty instance of the object requested
T empty(4);

head = new Node<T>;
head->item = empty;
head->next = NULL;
}

you've got problems.  You can't always create a T object with a single parameter of 4.  Like if T is a character string, that won't work.  Besides, that doesn't look like an empty list to me, it looks like a list with one item in it.

Instead indicate the list is empty by setting the head pointer to NULL.  not pointingto a node whose next is NULL.  Make head itself NULL.  This will be the indication of an emty list.  otherparts of you code may need to test for this condition to determine if the list is empty.

continues

0
 
LVL 22

Expert Comment

by:nietod
ID: 2583746
In

void List<T>::add(T new_item)

you pass the item to be added by value, it would be better to pass a constant reference (are you familar with references?)  like

void List<T>::add(const T &new_item)

The the first thing you do is to create a copy of the item to be added like

   T x(new_item);

Why?  You don't need that.  You have the parameter new_item and the node that will be created will store its own copy of the parameter.  You don't need this copy for anything.

int
                        // create two node pointers
                        Node<T>* q;
                        Node<T>* p;

It might be a good idea to give the pointers descriptive names.
Hint, one of them is going to be set to point tot he last item in the list.

then in
                        // create an empty node
                        p = new Node<T>;
                        p->item = 0;

why set item to 0?  How do you know that is even allowed?  You don't know that T is numeric, it mught be a string,  It might be a class of some sort.  Besides, why 0?  You want to store new_item.

Now in
                        if(head->next == NULL)

you are looking to see if the list is empty, but the condition for that is based no head, not what head points to.

When you make that change the next section of code (that if and its else) should get simpler.

continues
0
 
LVL 22

Expert Comment

by:nietod
ID: 2583752
In

void List<T>::kill(int x)

How do you want this to work?  i.e. how do you indicate which item to kill?  Currently it "looks" at each item using

p->item.getNum() != x

but that means that T has to be a class that has a member function called "getNum"  So T couldn't be a string or an int (or just about anything else).

So before you can consider how to delete from the list, you need to consider how you know which item to delete from the list.  

You might just wnat to have a delete that deletes the first item or the last item.

Note in add and delete you have code that seems to work like

if (list is empty)
  performa add/delete one way
else
  perform add/delete another way.

that should be avoided  Often the two ways are very similar and you can create one section of code that does both ways except for maybe a single statement or two that is in a if.  This is always more desirable as the special case code you have is harder to test and harder to maintain.

done for now, work on it and post what you get done.
0
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 

Author Comment

by:scottd1978
ID: 2584987
first off, thanks for all the tips.

although the class is a template class, it's customized for 7 different classes that I want to keep track of (I will rename it when completed).  

if I comment out everything in the constructor, I still get the segmentation fault.








0
 

Author Comment

by:scottd1978
ID: 2584988
I tried setting the head = to NULL.

head = NULL;
0
 
LVL 22

Expert Comment

by:nietod
ID: 2585078
Post the new code.  One line like that has no context and is meaninless.
0
 

Author Comment

by:scottd1978
ID: 2585108
List<T>::List()
{
        // create an empty instance of the object requested
//      T empty(4);

//      head = new Node<T>;
//      head->item = NULL;
//      head->next = NULL;
        head = NULL;
}

eof

even if I comment out the last line (head = NULL;) I get the Segmentation Fault.

The rest of the code remains the same.  

I'm not too concerned about the rest of the code, I just want to know why I'm getting the seg fault.
0
 
LVL 22

Expert Comment

by:nietod
ID: 2585157
Where do you get the segmentation failt?   Not in that code.   The problem is somewhere else.  
0
 

Author Comment

by:scottd1978
ID: 2585232
List<T>::List()
{
        // create an empty instance of the object requested
//      T empty(4);

//      head = new Node<T>;
//      head->item = NULL;
//      head->next = NULL;
        head = NULL;
}

eof

even if I comment out the last line (head = NULL;) I get the Segmentation Fault.

The rest of the code remains the same.  

I'm not too concerned about the rest of the code, I just want to know why I'm getting the seg fault.
0
 

Author Comment

by:scottd1978
ID: 2585235
The problem occurs in the test program when declaring the list.

list.cpp

#ifndef OBJ_LIST
#define OBJ_LIST
#include <iostream.h>
#include "list.h"
#include "list.cxx"
#include "/home/mud/classes/object/object.cpp"

int main()
{
        List<Object> first_list;

       
//      first_list.kill(3);
       
        return 0;

}

#endif  // OBJ_LIST

0
 
LVL 22

Accepted Solution

by:
nietod earned 50 total points
ID: 2585389
Does the problem occur before the return statement?  When the return statement is executed, the destructor is called.  If the destructor has a bug, then you will crash on the return.

The last destrctor you posted had

   while(head->next != NULL)

this would crash when head is NULL.
0
 

Author Comment

by:scottd1978
ID: 2585726
Thanks again!  I have a feeling I'll be back for this one.  
0
 
LVL 22

Expert Comment

by:nietod
ID: 2585854
 post what you get done.  Even if it seems to be working, it probably can be improved.
0
 

Author Comment

by:scottd1978
ID: 2586411
will do ... I probably won't be able to get back to it for a couple of days though :-(
0

Featured Post

Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question