Linked List Constructor help...

[fp_unit]

Hello,

I'm trying to write a linked list in C++ and I'm having a bit of trouble. I understand the absolute basics of a list (front/back insertion, destructor) but I'm having a bit of trouble putting my ideas into code. Lets see if I can show what I have so far:

struct Node
{
    int data;
    Node* nextPtr;
};

class LinkedList
{
public:
    LinkedList() : nodePtr(0) {  }
    ~LinkedList();

private:
    Node* nodePtr;
};

LinkedList::~LinkedList()
{
    Node* tmpPtr;
    while(nodePtr->nextPtr != 0)
    {
        tmpPtr = nodePtr;
        nodePtr = nodePtr->next;
        delete nodePtr;
    }
}

2 questions:

1.) Does my constructor basically do the following?

Node * bla;
bla->data = 0;
bla->nextPtr = 0;

2.) Am I on basically the right track?

Please try not to "give it all away" so to speak, if necessary try to push me slightly in the right direction. This is my first time trying to write a List class from scratch and I feel like theres lots to learn.

Thanks.

[ender]

In my opinion you are heading in the right general direction, but not quite hitting the target.

You should take a careful look at your destructor to see if it is really going to do what you think it will do. Think about what tmpPtr is pointing to what and what you are deleting, and how that might affect your while loop.

Your constructor is not quite right. Remember that a pointer does just that, it points. What you do to the pointer itself does nothing to what it points to (unless you explicitly tinker with what it points to with * or ->). Think about that and then think about what declaring a pointer does. Does delaring a pointer create what it points to?

You are doing good! Keep it up!

-Ted

[fp_unit]

Good eye. I made 2 updates (constructor, deletion of tempPtr in destructor) and to me it looks OK. I can't compile this yet or even spend more than 5 minutes working on it ATM because I'm also trying to do some C++ homework right now. I should be done in an hour or so, and if my constructor/destructor look good then I'm going to write the appendHead and appendTail member functions.

struct Node
{
    int data;
    Node* nextPtr;
};

class LinkedList
{
public:
    LinkedList() : nodePtr->nextPtr(0) {  }
    ~LinkedList();

private:
    Node* nodePtr;
};

LinkedList::~LinkedList()
{
    Node* tmpPtr;
    while(nodePtr->nextPtr != 0)
    {
        tmpPtr = nodePtr;
        nodePtr = nodePtr->nextPtr;
        delete tmpPtr;
    }
}

Does that look better? I basically made a typo in the destructor the first time, if my destructor's right then that's what I was trying to do all along... I gotta watch out for those typing errors. And can I use the arrow operator in the member initializer list of the constructor like I'm doing? I don't really think that any data should be filled in to the first node, I'm thinking right now that I will use that as a head node - a pointer to the first element in the List, instead of it being the first node in the List.

Thanks for your help.

[ender]

Yes, the destructor looks ok now.

As for your constructor, you will not be able to use an initialization list in this case. Remember, the pointer just points. You have not set what it will be pointing to yet. Therefore you can't set the values to what it points to either. I hope I'm not giving it away.

Think about why you delete something (tmpPtr). Now think of another keyword that might shed some light on this. And you are correct that it will just 'point' to the head of the list, however this is still a pointer!

Doing great!

-Ted

[fp_unit]

OK I had a few errors still, I think I'm bug free now

I got the following code working, too bad I have to go to class now. (I forgot to allocate a new node... duh...)

#ifndef LIST_H_
#define LIST_H_

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* nextPtr;
};

class LinkedList
{
public:
    LinkedList()
    {
        nodePtr = new Node;
        nodePtr->nextPtr = 0;
    }
    ~LinkedList();

private:
    Node* nodePtr;
};

LinkedList::~LinkedList()
{
    while(nodePtr->nextPtr != 0)
    {
        Node* tmpPtr = nodePtr;
        nodePtr = nodePtr->nextPtr;
        delete tmpPtr;
    }
}

#endif

and main

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

int main()
{
    LinkedList test;
    return 0;
}

I'll probably keep having to modify it as I add features to the class, but thats the goal, is for me to learn lists. I have drawn a few out on paper which I recommend to people just learning, it really helps to visualize the list. Anyways hopefully I'll add some functionality to this class tonite, or maybe even after class today. We'll see. I'll keep you guys updated.

[Valmont]

Let's try to be as object oriented as we can be. The struct leaves us with access to its public members. Encapsulate the struct as well. And there is no need to initialize the the nodePointer or the nextPointer:

class LinkedList
{
public:
  LinkedList();    
  ~LinkedList();
private:
  struct Node
  {
    int data;
    Node* nextPtr;
  };
  Node* nodePtr;
};

//-----------------------------------------

LinkedList::LinkedList() : nodePtr(0)
{}

//------------------------------------------

LinkedList::~LinkedList()
{
    while(nodePtr->nextPtr != 0)
    {
        Node* tmpPtr = nodePtr;
        nodePtr = nodePtr->nextPtr;
        delete tmpPtr;
    }
}

//------------------------------------------}

[Valmont]

Another (more professional) option is this:

#include <iostream>
#include <cstdlib>
#include <stdexcept>

using namespace std;

class Node
{
  public:
    Node() : next_(0)
    {}
    Node( int data, Node* nxt) : data_(data), next_(nxt)
    {}
    const int& get_data() const
    {
      return data_;
    }
    Node* next() const
    {
      return next_;
    }  
    private:
      friend class LinkedList;
      int data_;
      Node* next_;      
};

//--

class LinkedList
{
public:
  LinkedList();    
  ~LinkedList();
  void prepend(int const val);
  int const first() const;
  Node* get_head() const;
private:  
  Node* head_;
};

//-----------------------------------------

LinkedList::LinkedList() : head_(0)
{}

//------------------------------------------

LinkedList::~LinkedList()
{
  if(head_ != 0)
  {
    while(head_->next_ != 0)
    {
      Node* temp = head_;
      head_ = head_->next_;
      delete temp;
    }
    head_ = 0;
  }  
}

//------------------------------------------

void LinkedList::prepend(const int val)
{
  Node* const tmp = new Node(val, head_);
  head_ =  tmp;
}  

//------------------------------------------

const int LinkedList::first() const
{
  if(head_ == 0)
  {
    throw domain_error("ERROR: List is empty");
  }
  return head_->data_;    
}  

//------------------------------------------

Node* LinkedList::get_head() const
{
  return head_;
}  

//------------------------------------------

int main(int argc, char *argv[])
{
  LinkedList L;
  
  L.prepend(5);
  L.prepend(6);
  L.prepend(7);
  
  try
  {
    cout<<L.first()<<endl;
    for( Node* p = L.get_head(); p != 0; p=p->next() )
    {
      cout<<p->get_data()<<endl;
    }
  }
  catch(domain_error& dr)
  {
    cout<<dr.what()<<endl;
  }  

  return 0;
}