C++ linked list based tree structure. Sanely copy nodes between lists.
- by krunk
edit
Clafification: The intention is not to remove the node from the original list. But to create an identical node (data and children wise) to the original and insert that into the new list. In other words, a "move" does not imply a "remove" from the original.
endedit
The requirements:
Each Node in the list must contain a reference to its previous sibling
Each Node in the list must contain a reference to its next sibling
Each Node may have a list of child nodes
Each child Node must have a reference to its parent node
Basically what we have is a tree structure of arbitrary depth and length. Something like:
-root(NULL)
--Node1
----ChildNode1
------ChildOfChild
--------AnotherChild
----ChildNode2
--Node2
----ChildNode1
------ChildOfChild
----ChildNode2
------ChildOfChild
--Node3
----ChildNode1
----ChildNode2
Given any individual node, you need to be able to either traverse its siblings. the children, or up the tree to the root node.
A Node ends up looking something like this:
class Node
{
Node* previoius;
Node* next;
Node* child;
Node* parent;
}
I have a container class that stores these and provides STL iterators. It performs your typical linked list accessors. So insertAfter looks like:
void insertAfter(Node* after, Node* newNode)
{
Node* next = after->next;
after->next = newNode;
newNode->previous = after;
next->previous = newNode;
newNode->next = next;
newNode->parent = after->parent;
}
That's the setup, now for the question. How would one move a node (and its children etc) to another list without leaving the previous list dangling?
For example, if Node* myNode exists in ListOne and I want to append it to listTwo.
Using pointers, listOne is left with a hole in its list since the next and previous pointers are changed. One solution is pass by value of the appended Node. So our insertAfter method would become:
void insertAfter(Node* after, Node newNode);
This seems like an awkward syntax. Another option is doing the copying internally, so you'd have:
void insertAfter(Node* after, const Node* newNode)
{
Node *new_node = new Node(*newNode);
Node* next = after->next;
after->next = new_node;
new_node->previous = after;
next->previous = new_node;
new_node->next = next;
new_node->parent = after->parent;
}
Finally, you might create a moveNode method for moving and prevent raw insertion or appending of a node that already has been assigned siblings and parents.
// default pointer value is 0 in constructor and a operator bool(..)
// is defined for the Node
bool isInList(const Node* node) const
{
return (node->previous || node->next || node->parent);
}
// then in insertAfter and friends
if(isInList(newNode)
// throw some error and bail
I thought I'd toss this out there and see what folks came up with.
