Menu
The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list. A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.
Unlike arrays where the elements can be search by index, linked list require iteration. This means that if you want to get the data on the tenth node, the head pointer can be used to get to the first node, the pointer on the first node can be used to get to the second node, and so forth until the tenth node is reached.
node *next ensures that you've a variable next which is a pointer to the node . int *next would mean that next would point to an integer and not the node , won't give you the linked list, which is what you seem to be looking for.
A node is called a self-referential object, since it contains a pointer to a variable that refers to a variable of the same type. For example, a struct Node that contains an int data field and a pointer to another node can be defined as follows. Memory must be allocated for one node and assigned to head as follows.
It's not just better, it's the only possible way.
If you stored a Node object inside itself, what would sizeof(Node) be? It would be sizeof(int) + sizeof(Node), which would be equal to sizeof(int) + (sizeof(int) + sizeof(Node)), which would be equal to sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node))), etc. to infinity.
An object like that can't exist. It's impossible.
In Java
Node m_node
stores a pointer to another node. You don't have a choice about it. In C++
Node *m_node
means the same thing. The difference is that in C++ you can actually store the object as opposed to a pointer to it. That's why you have to say you want a pointer. In C++:
Node m_node
means store the node right here (and that clearly can't work for a list - you end up with a recursively defined structure).
C++ is not Java. When you write
Node m_next;
in Java, that is the same as writing
Node* m_next;
in C++. In Java, the pointer is implicit, in C++ it is explicit. If you write
Node m_next;
in C++, you put an instance of Node right there inside the object that you are defining. It is always there and cannot be omitted, it cannot be allocated with new and it cannot be removed. This effect is impossible to achieve in Java, and it is totally different from what Java does with the same syntax.
You use a pointer, otherwise your code:
class Node
{
//etc
Node m_next; //non-pointer
};
…would not compile, as the compiler cannot compute the size of Node. This is because it depends on itself — which means the compiler cannot decide how much memory it would consume.
The latter (Node m_next) would have to contain the node. It wouldn't point to it. And there would then be no linking of elements.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With