Search code examples
c++data-structuresclionc++-templates

Is there a way in c++ to create a single Node class for different data structures such as a sparse matrix, doubly linked list, etc

I am currently working on a project which requires me to create data structures by hand in C++.

I would like to know, if it is possible to create a template for this type of scenario, in which I can define all types of pointers, that is, next, previous, below and above?

I'm trying to implement the following data structures: sparse matrix, doubly linked list, priority queue and a doubly circular linked list. I think I might be doing extra work for no reason when I create the nodes that correspond to each data structure.

Maybe something like a variable amount of arguments would work? If so, which guide can I refer to when implementing the search functions, etc?

image

image

Solution

  • Here is a solution that I sometimes use:

    struct Singly_List_Node
{
    Singly_List_Node * p_next;
};

struct Doubly_List_Node : public Singly_List_Node
{
    Doubly_List_Node * p_previous;
}

    If you want, let's say a tree data structure, then your node can inherit from one of the above nodes. These are just foundations, you'll have to fill in the methods for linking instances.

    Edit 1: Data in the nodes

    If you like to have an all-in-one node, you could use a template (stencil). The template version allows you to specify the data type in the node. But, if you are going that route, you may want to use std::list instead.