Solved

linked list of my own datatype?

Posted on 2000-03-04
14
185 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
Comment Utility
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
Comment Utility
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
Comment Utility
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
 

Author Comment

by:scottd1978
Comment Utility
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
Comment Utility
I tried setting the head = to NULL.

head = NULL;
0
 
LVL 22

Expert Comment

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

Author Comment

by:scottd1978
Comment Utility
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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 22

Expert Comment

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

Author Comment

by:scottd1978
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Thanks again!  I have a feeling I'll be back for this one.  
0
 
LVL 22

Expert Comment

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

Author Comment

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

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

743 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now