C++ linked list based tree structure. Sanely move nodes between lists.
- by krunk
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.
