Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Linked list help

This topic is 5928 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
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 :-)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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;
}
}
};

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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);
# }
# }
# };

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!