1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C++ Linked List Question

  1. Feb 11, 2013 #1
    1. The problem statement, all variables and given/known data
    Hello, just having a bit of trouble understanding this bit of code:

    typedef int Item;

    struct Node {
    Item data;
    Node* next;
    };

    typedef Node* NodePtr

    NodePtr hdlist = NULL;


    2. Relevant equations

    None.

    3. The attempt at a solution

    I understand that typedef is used to assign alternative names to existing types. So Item is now (int). Node is the name of the structure and inside the structure we have Item data = int data basically. What I'm not sure about is Node* next.

    As far as I am aware, pointers are declared with the int* ptr method. This is a pointer ptr of type int. However does this mean that next is a pointer of type Node? But Node is simply the name of the structure?
     
  2. jcsd
  3. Feb 11, 2013 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Yes, so every Node has a pointer to a(nother) Node. This will be the next item in the list, like this:
    ll2.gif

    What you do is you keep a pointer to the first node in the list, which is called the head. The first item in the list is head->data. From there you can skip to head->next, which is the second node in the list, and the ->next of that is the third node, etc. until you eventually reach the end of the list which has it's next pointer pointing to nothing (null).

    There are also variations where every Node has two pointers, one to the next item in the list and one to the previous one, which allows you to go through it in two directions; and computer scientists can probably tell you more complicated ones which have their various advantages (for example for easily searching sorted lists, etc).
     
    Last edited: Feb 11, 2013
  4. Feb 11, 2013 #3

    rcgldr

    User Avatar
    Homework Helper

    Here is a "C" example with the next pointer at the start of the structure. This allows different structures with a next pointer at the beginning to share common code for handling lists of structures. This first example also uses the old "microsoft" "C" style for the typedef syntax. I left out the int item typedef, since I wanted to focus on the structure typedef:

    typedef struct _NODE { // underscore used on struct name
    struct _NODE* next;
    int data;
    }NODE, *NODEPTR; // no underscore on typedef names

    NODEPTR hdlist = NULL;

    Here is a "C++" example that uses inherited class:

    class Node{ // base node class
    public:
    Node * next;
    Node(){next = NULL;}
    };

    class NodeInt : public Node{ // inherited node class with int
    public:
    int value;
    NodeInt(int v) : value(v) {next = NULL;};
    };

    NodeInt * hdlist = NULL;
     
    Last edited: Feb 11, 2013
  5. Feb 11, 2013 #4

    Mark44

    Staff: Mentor

    To declare a pointer you use syntax that looks like this:
    Code (Text):

    [[I]type[/I]] * ptr;
     
    In the above, type is some data type, such as int, float, char, or some user-defined type, such as Node in your code.
    No it's not. The declaration int * ptr; says that ptr is a variable whose type is "pointer to int." The value that is stored in a pointer is the address of the thing it points to.


    No, the type is "pointer to Node."
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: C++ Linked List Question
Loading...