Understanding C++ Linked List Code: Node Structure and Pointers Explained

[bd411]

Homework Statement

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;

Homework Equations

None.

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?

 

[CompuChip]

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

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).

 

[rcgldr]

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;

 

[Mark44]

As far as I am aware, pointers are declared with the int* ptr method.

To declare a pointer you use syntax that looks like this:

[[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.

This is a pointer ptr of type int.

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.

However does this mean that next is a pointer of type Node?

No, the type is "pointer to Node."

But Node is simply the name of the structure?