c++pointersstructtypedef

C++ code explanation: how pointers work on a struct of a Linked List

I can't understand what's happening on the beginning of this C++ code that would explain to me how to implement a stack using Dynamic Array. I'm sure the code is correct, because the program runs correctly (correct results), but I don't understand it!

struct Node {
    char Info;
    Node *Link;
};

typedef Node *Stack;

Let's see:

  1. there is a struct called Node, and it has Info and *Link as "fields", like fields on a form paper. So Node is the name of a "template" (struct) with empty "fields". Each time we use Node on this program, like, let's say, Node StackOverflow, it's like photocopying this form paper and filling it's fields;
  2. *Link is itself another Node! But how can a pointer ("*") part of a struct be another instance of the same struct? Pointers don't have "fields" like form papers! They can only have one address as value, so only one field, like any other variable. This code doesn't makes sense;
  3. Then *Stack is typedefined as a pointer ("*") that is a struct ("Node") that has a pointer inside ("*Link") that is really another struct ("Node *Link"). I don't understand anything anymore!!! HELP!
Solution

  • Let's start with the code.

    struct Node {
    char Info;
    Node *Link;
};

typedef Node * Stack;

    And you wrote this:

    there is a struct called Node, and it has Info and *Link as "fields", like fields on a form paper. So Node is the name of a "template" (struct) with empty "fields". Each time we use Node on this program, like, let's say, Node StackOverflow, it's like photocopying this form paper and filling it's fields;

    That's close. You don't have a * Link, you have a Link field, which is a pointer to another node. This is an important concept called a linked list. The first item points to the second one, and that one points to the third one, et cetera. (It can also be used for so many more things).

    So you can do something like this:

     Node myNode;
 myNode.Info = 'A';
 myNode.Link = nullptr;

    You now have a linked list with exactly one item, and it's Info is 'A'.

    You can then do this:

     Node * anotherNode = new Node();
 myNode.Link = anotherNode;
 anotherNode->Info = 'B';
 anotherNode->Link = nullptr;

    Now you have a linked list with two items, with values 'A' and 'B'.

    Link is itself another Node! But how can a pointer ("") part of a struct be another instance of the same struct? Pointers don't have "fields" like form papers! They can only have one address as value, so only one field, like any other variable. This code doesn't makes sense;

    No. The field is called Link and it is of type Node *. That is, it's a pointer to another node.

    Then Stack is typedefined as a pointer ("") that is a struct ("Node") that has a pointer inside ("*Link") that is really another struct ("Node *Link"). I don't understand anything anymore!!! HELP!

    This is the same confusion. The type is Stack and it is an alias for Node *. That is -- a Stack is a pointer to a Node object.

    So these two lines of code are exactly the same:

     Node * nodePtr1 = nullptr;
 Stack  nodePtr2 = nullptr;

    Both of them define a Node * that are initialized to nullptr.