11 Replies - 4890 Views - Last Post: 19 September 2012 - 07:52 AM Rate Topic: -----

#1 bately  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-September 12

Handling a generic linked list

Posted 15 September 2012 - 11:32 PM

Hi, I'm new to c++.
I'm trying to write a program that will use a generic linked list.
I created the linked list.I need that it will hold once an int and once a pointer to a list of ints.

this is what I've done so far:

double_linked.h

#ifndef _DOUBLE_LINKED_
#define _DOUBLE_LINKED_
#include <iostream>
using namespace std;

template <typename T>
class double_linked
{
    struct node
    {
        T data;
        node* prev;
        node* next;
        node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
    };
    node* head;
    node* tail;
    public:
        double_linked() : head( NULL ), tail ( NULL ) {}

    template<int N>
    double_linked( T (&arr) [N]) : head( NULL ), tail ( NULL )
    {
        for( int i(0); i != N; ++i)
        {
           push_back(arr[i]);
        }
    }

    bool empty() const { return ( !head || !tail ); }
    operator bool() const { return !empty(); }
    void push_back(T&);
    void push_front(T);
    T pop_back();
    T pop_front();
    void const print();
    ~double_linked()
    {
        while(head)
        {
            node* temp(head);
            head=head->next;
            delete temp;
        }
    }
};

template <typename T>
void double_linked<T>::push_back(T &data)
{
    tail = new node(data, tail, NULL);
    if( tail->prev )
        tail->prev->next = tail;
    if( empty() )
        head = tail;
}

template <typename T>
void double_linked<T>::push_front(T data)
{
    head = new node(data, NULL, head);
    if( head->next )
        head->next->prev = head;
    if( empty() )
        tail = head;
}

template<typename T>
T double_linked<T>::pop_back()
{
    if( empty() )
        throw("double_linked : list empty");
    node* temp(tail);
    T data( tail->data );
    tail = tail->prev ;
    if( tail )
        tail->next = NULL;
    else
        head = NULL ;
    delete temp;
    return data;
}

template<typename T>
T double_linked<T>::pop_front()
{
    if( empty() )
        throw("double_linked : list empty");
    node* temp(head);
    T data( head->data );
    head = head->next ;
    if( head )
        head->prev = NULL;
    else
        tail = NULL;
    delete temp;
    return data;
}


template<typename T>
void const double_linked<T>::print()
{
    node* curr2(head);

//    cout<<"size:"<<getQueueSize()<<endl;
    while(curr2!=NULL)
    {
        cout<<" "<<curr2->data<<" ";
        curr2=curr2->next;
    }
    cout<<endl;
}

#endif






try.h

#ifndef _TRY_
#define _TRY_

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

class tryMe
{
    int value;
    double_linked<int> *tryList;
    double_linked<double_linked<int>*> *_plist;

public :


    tryMe(int array[], int size);
    ~tryMe();
    void const print();

};

#endif




try.cpp
#include <iostream>
#include "double_linked.h"
#include "try.h"
using namespace std;


tryMe::tryMe(int array[], int size)
{
    int i;
    double_linked<int> *tryList;
    double_linked<double_linked<int>*> *_plist;

    for (i=0 ; i < size; ++i)
    {
        tryList.push_back(&array[i]);
        cout<<array[i]<<" ";
    }

    _plist.push_front(tryList);

};

void const print()
{

    tryList *tryListM = new tryList;

}





main.cpp
#include <iostream>
#include "double_linked.h"
#include "try.h"
using namespace std;




    int main()
    {
    int arr[] = { 4, 6, 8, 32, 19 } ;
    double_linked<int> dlist ( arr );
    while( dlist )
    std::cout << dlist.pop_back() << " ";

    tryMe *tryMe1 = new tryMe(arr , 5);





    return 0 ;
    }








code blocks sends me an error that :
In constructor ‘tryMe::tryMe(int*, int)’:
error: request for member ‘push_back’ in ‘tryList’, which is of non-class type ‘double_linked<int>*’
error: request for member ‘push_front’ in ‘_plist’, which is of non-class type ‘double_linked<double_linked<int>*>*’


I'm probably getting the pointers all wrong.
Can anyone help me to understand what I have done wrong?
Thank you. (I'm sorry for my bad English).

Attached File(s)



Is This A Good Question/Topic? 0
  • +

Replies To: Handling a generic linked list

#2 Bench  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 856
  • View blog
  • Posts: 2,339
  • Joined: 20-August 07

Re: Handling a generic linked list

Posted 16 September 2012 - 01:02 AM

There are quite a few problems in your code which suggest to me that your time would be best spent learning a few of the basics about pointers and their usage before diving into linked lists;

View Postbately, on 16 September 2012 - 07:32 AM, said:

double_linked<double_linked<int>*> *_plist;

/* .. etc. */

_plist.push_front(tryList); 
_plist itself has a type of 'pointer-to..', the way to access its members involves dereferencing it first. Either with (*_plist). or _plist->.

However, you shouldn't need to create it as a pointer in the first place. It would be better to simply declare it as
double_linked<double_linked<int>*> _plist;

Also, the existence of _plist in that member-function is hiding the name _plist declared in your class.


(There are some decent pointer/linked list tutorials at the end of this post, they're well worth studying!)


View Postbately, on 16 September 2012 - 07:32 AM, said:

I created the linked list.

It would be better to say that you copied it from here: http://www.daniweb.c...y-linked-list-c otherwise some may justifiably ask "Well, if you know how to create a generic linked list class, then why don't you know how to use it".
- And besides, do you really trust the author of that snippet..?

Are you aware that C++ has a standard built-in list type which does everything that you need? You would have an easier time using that one instead of a dodgy linked list snippet copied from the internet; You also wouldn't need to fiddle around with pointers either because it is copyable, and you can simply treat all your ints and lists as normal variables; in any case, it's worth your time learning how to use C++'s built-in libraries (They are considerably easier to learn and use than home-made ones!)
- http://www.mochima.c...orials/STL.html

The snippet you're using is loosely based on some of the same ideas as are found in std::list, but the original author of the snippet didn't include a copy constructor or assignment operator with it (The description does say "no frills" afterall), meaning you'd have to jump through some hoops to use a 'list of lists'



Also, specifically on the subject of pointers and homemade lists, it's worth looking at these links:
Pointers:
http://www.eternally...t_pointers.aspx
http://www.augustcou...torial/ptr.html
http://www.daweidesi...in/pointers.php
http://www.c-faq.com/ptrs/index.html

Linked Lists:
http://www.dreaminco...ure-adventures/
http://www.eternally...t_linklist.aspx

This post has been edited by Bench: 16 September 2012 - 01:12 AM

Was This Post Helpful? 2
  • +
  • -

#3 bately  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-September 12

Re: Handling a generic linked list

Posted 16 September 2012 - 04:24 AM

Thank you!
I come from Java, so using pointers is a bit confusing.

I used that code because I had a problem with mine, so I tried using a simpler one that works and see if I get the same errors.
I know about the list library, I can't use it in this assignment, plus- I prefer learning.
Thank you for directing me to these guides, it's hard to find the right ones .
Was This Post Helpful? 0
  • +
  • -

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6063
  • View blog
  • Posts: 23,517
  • Joined: 23-August 08

Re: Handling a generic linked list

Posted 16 September 2012 - 04:37 AM

See also this excellent guide from our very own KYA.
Was This Post Helpful? 1
  • +
  • -

#5 bately  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-September 12

Re: Handling a generic linked list

Posted 18 September 2012 - 03:58 AM

Now I have another problem, this is the :

IntSet.h
#ifndef _INTSET_
#define _INTSET_
#include <ostream>
#include "dlist.h"
using namespace std;

class IntSet
{
public:

    dlist<int>* _intList;
    static dlist<dlist<int>* > _plist ;

    IntSet();
    IntSet (int * , int );

    IntSet superset();

    int searchSet();

    void print();

};


#endif





IntSet.cpp
#include <ostream>
#include "IntSet.h"
#include "dlist.h"
#include "Node.h"
using namespace std;

dlist<dlist<int>* > IntSet::_plist; //static

//constructor

IntSet::IntSet(int numArray[], int size)
{
    dlist<int> *list;
    int i;

    for (i=0; i < size; i++)
    {
       list.insertInOrder(numArray[i]);//error
       list.printList();//error
    }

    this->_intList = list;

    _plist.printList();//ok prins empty

    this->_plist.insertToHead(&(_intList));

    _plist.printList();//prints memory

};




main.cpp


#include "Node.h"
#include "dlist.h"
#include "IntSet.h"
#include <ostream>
#define SIZE_INT_ARR(a) ((sizeof(a))/(sizeof(int)))
using namespace std;

int main()
{

   int a[]={2,7,5,1,3,8};
    IntSet s1(a,SIZE_INT_ARR(a));


}





When I try to use any of the function of dlist such as -printList, insertInOrder, on list- it gives me an error :
error: request for member ‘insertInOrder’ in ‘list’, which is of non-class type ‘dlist<int>*’
but it's fine if I use it on _plist.
help anyone?
Was This Post Helpful? 0
  • +
  • -

#6 bately  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-September 12

Re: Handling a generic linked list

Posted 18 September 2012 - 10:24 AM

After I talked with a friend who helped me a bit, this is what my code looks now:

IntSet.h

class IntSet
{
public:
    dlist<int> _intList;
    static dlist<dlist<int> > _plist ;

    IntSet (int * , int );
    IntSet() : _intList(dlist<int> (NULL, NULL)){};
    IntSet superset();

    int searchSet();
    void insertInOrder (int);
    void print();
};




IntSet.cpp


IntSet::IntSet(int numArray[], int size)
{

    dlist<dlist<int> > _plist;
    dlist<int> _intList;
    dlist<int> list;
    int i;

    for (i=0; i < size; i++)
    {
       list.insertInOrder(numArray[i]);
       list.printList();
    }

    this->_intList = list;

    this->_plist.insertToHead(_intList);//calls the destructor

    cout<<"print intlist : ";
    this->_intList.printList();

};

void IntSet::print()
{
    this->_intList.printList();
}




main.cpp

int main()
{
   int a[]={2,7,5,1,3,8};

    IntSet s1(a,SIZE_INT_ARR(a));

    s1.print();//prints garbage

    return 0;
}







I have no idea why when I try to insert the linked list(_intList) I created to the head of the linked list(_plist) it calls the destructor.
And when I go back to the main and I try to print the linked list that contains ints it prints random numbers (garbage I guess).

What am I doing wrong? :(
Was This Post Helpful? 0
  • +
  • -

#7 Bench  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 856
  • View blog
  • Posts: 2,339
  • Joined: 20-August 07

Re: Handling a generic linked list

Posted 18 September 2012 - 10:50 AM

View Postbately, on 18 September 2012 - 06:24 PM, said:

I have no idea why when I try to insert the linked list(_intList) I created to the head of the linked list(_plist) it calls the destructor.
And when I go back to the main and I try to print the linked list that contains ints it prints random numbers (garbage I guess).

what does dlist look like?

- Does insertToHead accept an element by-reference or by-value? (If it accepts its argument by-value then it will create a copy and destroy that copy by the time it has returned, which I suspect is why you are seeing your destructor called).

Does dlist have an overloaded copy constructor and assignment operator? If not, then you will need to write one which is capable of creating a deep copy (Following the same concept as Java's Clone methods). C++ uses a "rule of three" which suggests that if you need either a Destructor, Copy Constructor or Assignment operator, then you are probably going to need all three:
- http://en.wikipedia....opy_constructor

This post has been edited by Bench: 18 September 2012 - 10:51 AM

Was This Post Helpful? 0
  • +
  • -

#8 bately  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-September 12

Re: Handling a generic linked list

Posted 18 September 2012 - 04:53 PM

Thank you!

one more thing (hope it's the last):
I want that the _plist will hold a pointer to another int linked list. I need to be able to access the int list through the _plist. I created a temp variable that will hold the head of the list.
now, I initialized the _plist to be:
dlist<Node<int>& > IntSet::_plist;


Node<int>& is the head;

Is this the correct way of thinking?
and if so, how do I pass _intList.temp to the insertToHead function? it only accepts references but not pointers.
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3575
  • View blog
  • Posts: 11,117
  • Joined: 05-May 12

Re: Handling a generic linked list

Posted 18 September 2012 - 10:25 PM

What is the purpose of the static _plist ? Why do you need it? Why must it be static? How do you handle lists and nodes that get deleted? How do you handle multiple threads?

This post has been edited by Skydiver: 18 September 2012 - 10:26 PM

Was This Post Helpful? 0
  • +
  • -

#10 bately  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-September 12

Re: Handling a generic linked list

Posted 19 September 2012 - 12:30 AM

What is the purpose of the static _plist ?
I have a function called `superset` that returns a new 'IntSet', it holds all the numbers in all of the linked list without duplicates.
when I create new sets in the main, I don't actually know how many sets there are in the program, so I wanted to keep tabs of haw many sets I created, and a way to get to the sets and create the superset.

Why must it be static?
I need to make it independent from any other sets.

How do you handle lists and nodes that get deleted?
What I was going to do, if I have a node that is null, means that I erased the int linked list, I'd remove that node and update the super set.
Was This Post Helpful? 0
  • +
  • -

#11 bately  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-September 12

Re: Handling a generic linked list

Posted 19 September 2012 - 03:24 AM

If I try to do it this way:

IntSet.cpp
IntSet::IntSet(int numArray[], int size)
{
    dlist<dlist<int> > listOfLists;
    dlist<dlist<int> > _plist;
    dlist<int> _intList ;
    dlist<int> list;
    int i;

    for (i=0; i < size; i++)
    {
       list.insertInOrder(numArray[i]);
       list.printList();
    }

    this->_intList = list;

   listOfLists.insertToHead( _intList);
  //  this->_plist = listOfLists; 
};



insertToHead in dlist


template <class T>
void dlist<T>::insertToHead ( T const& dataToInsert )
{
    Node<T>* nodeToInsert;
   //if the list is empty make the node to be the head
    if( head == NULL)
    {
        nodeToInsert = new Node<T>(dataToInsert,NULL,NULL);//sending it to the destructor
        head = nodeToInsert;
        tail = nodeToInsert;
        cout<<"list was empty - inserted to head"<<endl;
    }
    //make the node to be the new head
    else
    {
        nodeToInsert = new Node<T>(dataToInsert,head,NULL);
        head = nodeToInsert;
        cout<<"list was not empty - inserted to head"<<endl;
    }

}//insertToHead





~dlist


template<class T>
dlist<T>::~dlist()
{
    cout<<"don't know why the fuck I made it in the destructor!!!"<<endl;
    Node<T>* curr;

    curr = temp;
    //if the list is already empty return
    if (head == NULL)
    {
        cout << "list is already empty" << endl;
        return;
    }
    //erase the list node by node
    else
    {
        while (curr != NULL) 
        {
           
            temp = curr->_next;
            delete curr;//crash here
            cout<<"crashed here"<<endl;
            curr = temp;
        }
    }

}//~dlist





I have no idea why it goes the destructor in the first place?
everything works fine with ints, only when I try to insert to head a dlist it goes to the destructer and crashes.
the error is:
glibc detected free() invalid pointer

valgrind:

==8742== Invalid free() / delete / delete[] / realloc()
==8742==    at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8742==    by 0x400BC4: dlist<int>::~dlist() (in /home/batelyaish/Desktop/ass3/prog)
==8742==    by 0x400EC7: dlist<int>::dlist(dlist<int> const&) (in /home/batelyaish/Desktop/ass3/prog)
==8742==    by 0x40165F: dlist<dlist<int> >::insertToHead(dlist<int> const&) (in /home/batelyaish/Desktop/ass3/prog)
==8742==    by 0x400D11: IntSet::IntSet(int*, int) (in /home/batelyaish/Desktop/ass3/prog)
==8742==    by 0x4009F0: main (in /home/batelyaish/Desktop/ass3/prog)
==8742==  Address 0x56ff260 is 0 bytes inside data symbol "_IO_2_1_stdout_"



Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3575
  • View blog
  • Posts: 11,117
  • Joined: 05-May 12

Re: Handling a generic linked list

Posted 19 September 2012 - 07:52 AM

Where was temp on line 7 of ~dlist() declared? And more importantly, where was it initialized? Then it was not initialized, then it is just pointing to some random memory.

Quote

I have no idea why it goes the destructor in the first place?


If you run your code in a debugger, and set a breakpoint on the destructor, you should be able to look up the callstack to see who is calling the destructor.

You should post your completed updated code. As of now, the best guess as the reason why it is calling the destructor is that the dlist is going out of scope in the IntSet constructor that you posted in post #11.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1