This is my pop_back() for my linked list and from what I can see it should work but doesn't remove the last node from the list. The requirement is to remove the node from the list without deleting the actual node. In other words, I suppose to assign the last node to a new pointer and set the pointer that pointed to it to NULL and return the new pointer back to the driver program. Can anyone help me out with where I went wrong here? I've tried multiple ways to program this and this is my recent attempt at getting it to work with no success so far.
Like vlad said, it would be helpful to see how much information you keep about your list. For example, is it singly linked? I'll assume it is for now. That means all you really seem to have is a head node and a count of the number of nodes in your list.
Node* List::pop_back()
{
if( numberOfNodes == 0 )
{
//list is empty, return null
}
elseif( numberOfNodes == 1 )
{
//list has a single node, which is the head
//save the head pointer in a temporary variable
//decrement the counter of how many nodes you have in the list
//set the head pointer equal to null
//return the temporary variable holding the old head pointer
}
else
{
//the list has at least 2 nodes
//define two nodes: lastNode and secondToLast
//set lastNode = head
//loop until lastNode points to the last node in the list
//make sure you keep secondToLast updated as you update lastNode
//set secondToLast's 'next' pointer to null
//decrement the counter of how many nodes you have in the list
//return lastNode
}
}
//list class
class List
{
private:
Node* firstNode;
Node* lastNode;
int numberOfNodes;
public:
// Default Constructor
// Purpose: Set variables to default values
// Parameters: None
// Returns: None
List();
// Get First Node
// Purpose: Get first node in list
// Parameters: method is constant
// Returns: ptr to firstNode
Node* getFirstNode() const;
// Get Last Node
// Purpose: Get last node in list
// Parameters: method is constant
// Returns: ptr to lastNode
Node* getLastNode() const;
// Get Number of Node
// Purpose: Get number of nodes in list
// Parameters: method is constant
// Returns: number of nodes as int value
int getNumberOfNodes() const;
// Push Front
// Purpose: Push node to the front
// Parameters: Node ptr
// Returns: None
void push_front(Node*);
// Pop Front
// Purpose: Remove front node from list
// Parameters: None
// Returns: Node ptr
Node* pop_front();
// Push Back
// Purpose: Push Node onto back of the list
// Parameters: Node ptr
// Returns: None
void push_back(Node*);
// Pop Back
// Purpose: Remove back node from list
// Parameters: None
// Returns: Node ptr
Node* pop_back();
};
If it is a single linked list then you can not effectively remove the last node, The problem is that the last node has no any information about its previous node, So that to remove the last node you have to traverse all the list from the first node.
Node* List::pop_back()
{
Node* saveLast = nullptr;
Node* secondToLast = firstNode;
Node* newlast = nullptr;
if( numberOfNodes == 0 )
{
returnnullptr;
}
elseif(numberOfNodes == 1)
{
//list has a single node, which is the head
//save the head pointer in a temporary variable
//decrement the counter of how many nodes you have in the list
//set the head pointer equal to null
//return the temporary variable holding the old head pointer
saveLast = lastNode;
lastNode->getNextNode();
numberOfNodes--;
return saveLast;
}
else
{
while(secondToLast != lastNode)
{
secondToLast = secondToLast->getNextNode();
newlast = secondToLast;
}
saveLast = lastNode;
newlast->setNextNode(NULL);
return saveLast;
}
}
Ok I've got it looping through the entire list and but once secondToLast = lastNode it exits as it should but newLast also ends up equaling lastNode instead of the node before the last node.
I'm sorry if I confused you, but I didn't know what you named your variables ahead of time. Also, knowing you have a pointer to the last node makes things a little easier. Take a look at this:
Node* List::pop_back()
{
//save off the last node, even if it is null, because that's what we return
Node* returnNode = lastNode;
if(numberOfNodes == 0)
{
//do nothing here, we will return nullptr at the bottom
}
elseif(numberOfNodes == 1)
{
--numberOfNodes;
firstNode = lastNode = nullptr;
}
else
{
//the list has at least 2 nodes
//define a temporary node that will serve as the second-to-last node
Node* penultimateNode;
//start from the beginning of the list
penultimateNode = firstNode;
//loop until penultimateNode points to the second-to-last node in the list
while(penultimateNode->getNext() != lastNode) penultimateNode = penultimateNode->getNext();
//set penultimateNode's 'next' pointer to null, since it is the new lastNode
penultimateNode->setNext(nullptr);
lastNode = penultimateNode;
//decrement the counter of how many nodes you have in the list
--numberOfNodes;
}
return returnNode;
}
Thanks man. I got it worked out and now it's off to the extra credit stuff. Delete Constructor, Copy Constructor, and assignment operator overload function.
