Simple Linked List Implementation Problem - C++

Question

Hi,

I'm a programming student in my first C++ class, and recently we covered linked lists, and we were given an assignment to implement a simple one. I have coded everything but my pop_back() function, which is supossed to return a pointer to the Node that needs to be deleted in Main(). No Node deletion is to be done in the actual function. So my question is:

Would you be willing to help point me in the right direction for my pop_back() function? Also, if you notice anything else that I'm doing wrong, let me know.

Also, this linked list is just to work with strings. In this case, a grocery list, so one string for the quantity of the item(1,2), and one string for the item type. (Milk, Eggs, etc.)

Below I've included my List & Node class implementations, so you can get an idea of what I've done so far.

Thanks!

Node.cpp

Node::Node(void)
{
    descrip = " ";
    quantity = " ";
    previous = NULL;
    next = NULL;
}
Node::Node(string q, string d)
{
    descrip = d;
    quantity = q;
    previous = NULL;
    next = NULL;
}
Node* Node::GetNext()
{
    return next;
}
Node* Node::GetPrevious()
{
    return previous;
}
void Node::SetNext(Node * setter)
{
    next = setter;
}
void Node::SetPrevious(Node * setter)
{
    previous = setter;
}

---

List.cpp

List::List(void)
{
   first = NULL;
   last = NULL;
   numNodes = 0;
}
Node* List::GetFirst()
{
    return first;
}
Node* List::GetLast()
{
    return last;
}
void List::SetFirst(Node* setter)
{
    first = setter;
}
void List::SetLast(Node* setter)
{
    last = setter;
}
int List::GetNumNodes()
{
    return numNodes;
}
void List::push_front(Node* item)
{
   if (first == NULL)
   {
       first = item;
       last = item;
   }
   else 
   {
       Node* pFirst = first;
       item->SetNext(pFirst);
       first = item;
       numNodes++;
   }
}
void List::push_back(Node * item)
{
    if (last == NULL)
    {
       first = item;
       last = item;
    }
    else 
    {
        last->SetNext(item);
        last = item;
        numNodes++;
    }
}
Node* List::pop_front()
{
    Node* temp = first;
    first = first->GetNext();
    if (first == NULL)
    {
        temp = first->GetNext();
        first = p;
    }
    if (first == NULL)
    {
        last = NULL;
    }
    if (numNodes > 0)
    {
        numNodes--;
    }
    return temp;
}
Node* List::pop_back() // this whole function may be wrong, this is just my attempt at it
{
    Node* temp;
    temp = first;

    while((temp->GetNext()) != NULL)
        // im stuck here

}

Answer 1

So if i understand this right you just want to run through you link list till you get to the last node in the link list and return the pointer to it? I'm pretty sure what you have there will do it except

Node* List::pop_back() // this whole function may be wrong, this is just my attempt at it  
{  
    Node* temp;  
    temp = first;  
    while(temp->GetNext() != NULL)  
    {  
        temp = temp->GetNext();  
    }  
    return temp;  
}

So if i read it right, there it will continually loop around until it gets to the node with none in the line behind it, then return it.

Answer 2

It would definitely have helped me if you also had posted your class declaration. I cannot guarantee that the below is correct but it makes sense to me

Node* List::pop_back()
{
  Node *temp = NULL;
  if(numNodes == 1) 
  {
    temp = first;
    // setting the list pointers to NULL
    first = NULL;
    // setting the list pointers to NULL 
    last = NULL; 
    //You should also probably remove the links from your node 
    //to the next and previous nodes but since you didn't specify 
    //this it is up to you
    numNodes--;
  }
  else if(numNodes > 1) //more than one element
  {
    //the pointer you want to return
    temp = last;
    //For clarity I am creating another variable here
    Node *newLast = temp->GetPrevious(); 
    //Setting the new last node to point at nothing so now temp 
    //is "disconnected from the list"
    newLast->next = NULL; 
    //the last pointer of the list is now pointing at the new last node
    last = newLast;         
//You should also probably remove the links from your node 
//to the next and previous nodes but since you didn't specify this it is up to you
        numNodes--; //decrement the counter
      }
      return temp;
    }

Answer 3

Some pointers:

0x1243bfa3
0x45afc56e
0xdeadbeef

Some more pointers:

1. You should prefer to initialize your class members in the initialization list, not in the constructor's body.

2. In C++, unlike C89, we declare and define a function with no parameters as void f();, not void f(void);.

3. In C++ we commonly reset pointers with 0, not NULL.

   See below for what I mean in code.

4. Good C++ code will try to take advantage of RAII. This implies avoiding primitive pointers for the most part. In this case plain old std::auto_ptr<> would make a perfectly sufficient substitute for the primitve Node* pointers. However, I do reckon part of the exercise here is pointer arithmetics, and so I just leave this as a side-note.

5. It would be useful for us if you'd attach the class declarations. I assumes all those accessors and mutators, GetFirst() and SetFirst() etc., are there because they are public. That's a bad idea. First, they expose the private pointers, which defeats the whole point of accessor. Second, they don't do anything special so they're just extra code -- which means extra room for bugs. This brings me to the next point.

6. Your mutators are incorrect. You blindly assign a new value to the private member pointer, without deleting what you had before. That's a memory leak.

7. Ever tried to pop_front() when the list is empty?

8. Finally, 8 being a round number it's time we get to the question at hand. pop_back(). My question to you is, why are you traversing the list all the way to the end if you so meticulously maintain a pointer to the last node of your list? Indeed, if you wouldn't bother with maintaining a pointer to the end of the list then you'd have to traverse all the way to the last node in order to pop it. And for that you were in the right direction. Except that ...

9. When you access members through pointers, as in first->GetNext(), always make sure first isn't a null pointer -- or else state in the function's documentation comment that you assume the pointer is not null.

These should get you started.

Points 1, 2 and 3 in code:

Node::Node()
: descrip(" "), quantity(" "), previous(0), next(0)
{
}

Answer 4

I like the previous posters answer, but one thing you might want to keep in mind is if you have an empty list. Then your first pointer will equal NULL and you would be trying to call NULL->GetNext() basically and Seg Fault. I think you can edit the above code slightly and still get have it work like this:

Node* List::pop_back() 
{  
    Node* temp;  
    temp = first;  
    while(temp != NULL && temp->GetNext() != NULL)  
    {  
        temp = temp->GetNext();  
    }  
    return temp;  
}

This will have the function return NULL if there is nothing in the list and still work properly.