Why do linked lists use pointers instead of storing nodes inside of nodes
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.
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.
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).