Linked list help
Author
I need to delete the last node in a list, but can''t seem to manage it,any suggestions would greatly appriciated. Thanks.
It would be very unefficient for a large list to get the last element and delete it by processing the whole list.
You should use circular list in order to handle directly the last element. It''s a bit more difficult to manage than classic list but I don''t see anything else for the moment. To do so you have to add a pointer called prec in each node (contrary to next) that point to the preceding element.
Try this & give me feedback :-)
You should use circular list in order to handle directly the last element. It''s a bit more difficult to manage than classic list but I don''t see anything else for the moment. To do so you have to add a pointer called prec in each node (contrary to next) that point to the preceding element.
Try this & give me feedback :-)
Author
preceding-previous all the same to me i just appriciate any help given. I didnt want to admit this but its homework. I have been give a huge amount of code in which i have to add missing bits, not change existing. The existing node only contains the ''data'' and ''next'' most of the tasks were making recursive functions as opposed to iteritive. But the one i can not get working is deleting the last node.
One way is to walk through the list until you reach the end node, but you keep a pointer to the previous node, ie:-
NODE *Prev,*Curr;
Prev = Curr = FirstNode;
While( Curr->Next )
{
Prev = Curr;
Curr = Curr->Next;
}
Curr is now the last node, and Prev is the node before the last node. (also works if only one node in list)
First->...Prev->Curr->NULL
if(Prev)Prev->Next = NULL;
if(Curr)Delete Curr.
NODE *Prev,*Curr;
Prev = Curr = FirstNode;
While( Curr->Next )
{
Prev = Curr;
Curr = Curr->Next;
}
Curr is now the last node, and Prev is the node before the last node. (also works if only one node in list)
First->...Prev->Curr->NULL
if(Prev)Prev->Next = NULL;
if(Curr)Delete Curr.
Something like this?
class List;
class Node;
class Node
{
friend class List;
Node * _next;
};
class List
{
Node * _first;
Node * deleteLastNode(Node * node, Node * deletedNode)
{
if(node->_next == NULL)
{
deletedNode = node;
return NULL;
}
else
{
node->_next = deleteLastNode(node->_next, deleletedNode);
return this;
}
}
public:
// Remove last node from the list and return it
Node * deleteLast()
{
if(_first == NULL)
return NULL;
else
{
Node * deletedNode;
deleteLastNode(_first, deletedNode);
return deletedNode;
}
}
};
class List;
class Node;
class Node
{
friend class List;
Node * _next;
};
class List
{
Node * _first;
Node * deleteLastNode(Node * node, Node * deletedNode)
{
if(node->_next == NULL)
{
deletedNode = node;
return NULL;
}
else
{
node->_next = deleteLastNode(node->_next, deleletedNode);
return this;
}
}
public:
// Remove last node from the list and return it
Node * deleteLast()
{
if(_first == NULL)
return NULL;
else
{
Node * deletedNode;
deleteLastNode(_first, deletedNode);
return deletedNode;
}
}
};
Whenever I make a list template, I usually have 2 private pointers, one to the head of the list and one to the tail of the list, and each node maintains a pointer to both the previous node and the next node.
Just easier that way for me.
"Doomed to crumble, unless we grow, and strengthen our communication" - Maynard James Keenan, Tool
Just easier that way for me.
"Doomed to crumble, unless we grow, and strengthen our communication" - Maynard James Keenan, Tool
Sorry:
# class List;
# class Node;
#
# class Node
# {
# friend class List;
#
# Node * _next;
# };
#
# class List
# {
# Node * _first;
#
# Node * deleteLastNode(Node * node)
# {
# if(node->_next->_next == NULL)
# {
# Node * deletedNode = node->_next;
# node->_next = NULL;
# return deletedNode;
# }
# else
# {
# return deleteLastNode(node->_next)
# }
# }
# public:
# // Remove last node from the list and return it
# Node * deleteLast()
# {
# if(_first == NULL)
# return NULL;
# else if(_first->_next == NULL)
# {
# Node * deletedNode = _first;
# _first = NULL;
# return deletedNode;
# }
# else
# {
# return deleteLastNode(_first);
# }
# }
# };
# class List;
# class Node;
#
# class Node
# {
# friend class List;
#
# Node * _next;
# };
#
# class List
# {
# Node * _first;
#
# Node * deleteLastNode(Node * node)
# {
# if(node->_next->_next == NULL)
# {
# Node * deletedNode = node->_next;
# node->_next = NULL;
# return deletedNode;
# }
# else
# {
# return deleteLastNode(node->_next)
# }
# }
# public:
# // Remove last node from the list and return it
# Node * deleteLast()
# {
# if(_first == NULL)
# return NULL;
# else if(_first->_next == NULL)
# {
# Node * deletedNode = _first;
# _first = NULL;
# return deletedNode;
# }
# else
# {
# return deleteLastNode(_first);
# }
# }
# };
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
