I have learnt different variants of list data model like Dlist, SList and recurs

Question

I have learnt different variants of list data model like Dlist, SList and recursivenodetype-list.

But I could not understand/visualise this datamodel as mentioned below in C++ syntax, with an observation that there is no data item in XGNode. I have never been through such approach of designing a list node class.

class XGNode
{
    private:
        friend class XGList;
        XGNode* next ;
        XGNode* prev ;
        XGList* listp;
    public:    
        XGNode ( void )
        {
           next = prev = this ;
           listp = 0;
        }
        void add ( XGNode* predecessor, XGList *parent )
        {

           // This rem() command allows us to simply add a XGNode to another
           // list without having to remove it from the list it was prev. on.

           rem() ;

           if (!parent)
           {
              listp = predecessor->listp;
           }
           else
           {
               listp = parent;
           }

           prev = predecessor ;
           next = prev -> next ;
           prev -> next = next -> prev = this ;

           if ( 0 != listp )
           {
                listp->count++;
            }

         } // XGNode :: add()

}
In the above code, What does it mean for every node to have a pointer of type XGList, where listp points to instance of below class.

class XGList
{
    private:
        friend class XGNode;
        XGNode* head ;
        XGNode* dummy ;
        XGNode* tail ;
        long count;
    public:
        XGList ( void ): dummy( NULL), count( 0 )
        {
           head = (XGNode*) &dummy ;
           tail = (XGNode*) this ;
        }
}
Now, How these two classes XGNode and XGList are being inherited?

If I consider LAN network technology, there are two classes XLanNode and XLanList that inherit as shown below:

class XLanNode : public XGNode
{

    public:

        XLanNode();
        ~XLanNode();

        XLanNode *get_next ( void ) const
        {
            return (( XLanNode * ) XGNode::get_next());
        }

        XLanNode *get_prev ( void ) const
        {
            return (( XLanNode * )XGNode::get_prev());
        }

        XLanNode *rem ( void )
        {
             return (( XLanNode *) XGNode::rem());
        }
    private:

        XModelHandle lan_model_handle;
        XIPAddrRanges ip_ranges;
        Xlong total_number_of_ips;
};
class XLanList : public XGList
{
    private:
        XModelHandle rootContainer;

    public:

        XLanList();
        ~XLanList();

        //////////////////////////////////////////
        // Overloaded XGNode methods to prevent
        // casting within code.
        //////////////////////////////////////////
        void add_head ( XLanNode *node )
        {
            XGList::add_head ((XGNode *) node);
        }

        void add_tail ( XLanNode *node )
        {
            XGList::add_tail ((XGNode *) node );
        }

        XLanNode *get_head ( void ) const
        {
            return ((XLanNode *) XGList::get_head());
        }

        XLanNode *get_tail ( void ) const
        {
            return (( XLanNode * )XGList::get_tail());
        }

        XLanNode *rem_head ( void )
        {
            return (( XLanNode * )XGList::rem_head());
        }

        XLanNode *rem_tail ( void )
        {
            return (( XLanNode * )XGList::rem_tail());
        }

        XLanNode *get_node ( XTulong i ) const
        {
            return (( XLanNode * )XGList::get_node((int)i));
        }

        const XLanNode *get_node ( const XModelHandle & mh ) const;
};
My goal is to understand this data model formed by XGNode and XGList and implement derived classes like LAN technology in Java.

You can get other methods of above two classes XGNode and XGList here

My question:

How to visualise this data model formed by XGNode and XGList where every node is pointing to a list? Where does predecessor and parent point to in add(,) method of class XGNode?

Explanation / Answer

How to visualise this data model where every node is pointing to a list? Is their a standard approach to visualise any data model, with the given data members and methods of a class?

It is a doubly-linked list. The fact that each node "knows" the list is more of an implementation detail than it is a matter of the data model architecture.

Possible advantages of this approach: if your list exposes it's nodes to client code, then client code could (presumably) work dirrectly on nodes, instead of the list (a lower level interface than normal iterators, and probably an unsafe interface).

One more thing:

XGNode* head ;
XGNode* dummy ; // pointer
XGNode* tail ;
long count;
public:
XGList ( void ): dummy( NULL), count( 0 )
{
head = (XGNode*) &dummy ; // pointer to pointer is (unsafely) cast to a pointer
// and the result is assigned to head
This is an invalid use case (the commented lines), only accepted by the compiler due to the C-style cast (and a textbook example on why C-style casts are to be avoided in C++).

To the degree that you will use head before assigning it another value, this is undefined behavior.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.