Circular Dependency Issue LinkedList

Question

Introduction to the problem: I'm making a program to track flight paths of airports using linked lists. For example if the data set is

(Austin - Dallas, Dallas - Houston)

and you try to find a flight

(Austin - Houston) 

it will calculate that you need to take the flightpath:

(Austin - Dallas - Houston)

The way my solution works (if I can figure out how to do this) is that I have an outer linked list composed of OuterNode's which each contain an inner linked list of flights. The inner linked list is composed of InnerNode's which contain pointers to the outer nodes (aka the flight destination). In theory it would make a lot of things easier to iterate through without having to keep copying over data through strings. In my header too many of my things require each other and can’t have the implementation in the right order. (this is all in the header of the innerlist class)

struct OuterNode {
    InnerList flights;
    int name;
    OuterNode* next;
};

struct InnerNode {
    OuterNode* dest;
    int price;
    InnerNode* next;
};
class InnerList
{
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

So basically:

OuterNode – needs InnerList (no definition yet)

InnerNode – needs OuterNode

InnerList – needs InnerNode

And currently the error is that InnerList doesn’t exist when OuterNode needs to make one. How can I fix this so that everything finds what it needs? Is there some creative use of templates or something that I could use to fix this?

Answer 1

"Is there some creative use of templates or something that I could use to fix this?"

No need for templates usage, you can simply restructure your code a bit, and introduce a forward declaration for struct InnerNode;

struct InnerNode;  // << forward declaration 

// Declare class InnerList first
class InnerList {
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

struct OuterNode {
    InnerList flights;
    int name;
    OuterNode* next;
};

// Finally declare InnerNode completely
struct InnerNode {
    OuterNode* dest;
    int price;
    InnerNode* next;
};

LIVE DEMO

---

PLEASE NOTE:

Instead of making your own linked list structure, you also might consider using a std::list<InnerNode*> flights; or even a std::vector<InnerNode*> flights; member in your OuterNode struct.
Though these solutions need to handle the instances of InnerNode's properly, by means of memory management, std::list<std::shared_ptr<InnerNode>> or std::vector<std::shared_ptr<InnerNode>> looks like the right way to go.

Answer 2

You need to use forward declarations.

When the compiler only needs to know that a type exists, but doesn't need to know anything about it's definition (as is the case when you declare a pointer), you can use a forward declaration to to tell the compiler 'a type with this name exists':

class InnerNode;
class InnerList
{
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

This will compile, because InnerList doesn't need to know anything about InnerNode; it just needs to know that a type named InnerNode exists.

If you have an actual instance of a type in your class, as is the case with OuterNode, a forward declaration won't work. The class has to know how much storage to allocate for the type, so it requires the full definition.

You can use forward declarations to make InnerList and InnerNode compile, but you'll need to move OuterNode's definition to be after InnerList, as it relies on it being defined.