Why do linked lists use pointers instead of storing nodes inside of nodes

Solution 1:

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.

Solution 2:

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

Solution 3:

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.

Solution 4:

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.

Solution 5:

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.