127

I've worked with linked lists before extensively in Java, but I'm very new to C++. I was using this node class that was given to me in a project just fine

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

but I had one question that wasn't answered very well. Why is it necessary to use

Node *m_next;

to point to the next node in the list instead of

Node m_next;

I understand that it is better to use the pointer version; I'm not going to argue facts, but I don't know why it's better. I got a not so clear answer about how the pointer is better for memory allocation, and I was wondering if anyone here could help me understand that better.

22
  • 14
    @self Pardon me? Why wouldn't a language where everthing is a pointer have no linked lists? Commented Apr 9, 2015 at 16:21
  • 41
    It's important to note how C and C++ are distinct from Java in terms of object pointers vs references. Node m_next is not a reference to a node, it's storage for the entire Node itself.
    – Brian Cain
    Commented Apr 9, 2015 at 16:21
  • 41
    @self Java does have pointers you just don't explicitly use them.
    – m0meni
    Commented Apr 9, 2015 at 16:22
  • 27
    Turtles all the way down is not an option. The madness has to end somewhere.
    – WhozCraig
    Commented Apr 9, 2015 at 16:22
  • 26
    Please forget everything you know about Java. C++ and Java handle memory in fundamentally different ways. Go see this question for book recommendations pick one, and read it. You'll be doing us all a huge favor.
    – Rob K
    Commented Apr 9, 2015 at 18:37

11 Answers 11

229

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.

19
  • 26
    *Unless it's evaluated lazily. Infinite lists are possible, just not with strict evaluation. Commented Apr 9, 2015 at 20:07
  • 55
    @Carcigenicate it's not about evaluating/executing some function on the Node object - it's about the memory layout of every instance of Node, which must be determined at compile time, before any evaluation can occur.
    – Peteris
    Commented Apr 9, 2015 at 22:17
  • 6
    @DavidK It's logically impossible to do this. You need a pointer (well really an indirection) here - sure the language can hide it from you, but in the end, no way around that.
    – Voo
    Commented Apr 10, 2015 at 7:32
  • 2
    @David I'm confused. First you agree that it is logically impossible, but then you want to contemplate it? Remove anything of C or C++ - it's impossible in any language you could ever dream up as far as I can see. That structure is by definition an infinite recursion and without some level of indirection we cannot break that.
    – Voo
    Commented Apr 10, 2015 at 13:08
  • 13
    @benjamin I actually pointed out (because I knew otherwise someone would bring this up - well didn't help) that Haskell allocated the thunks at creation time and hence this works because those thunks give us the indirection we need. This is nothing but a pointer with extra data in disguise...
    – Voo
    Commented Apr 10, 2015 at 16:00
178

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

10
  • 2
    @SalmanA I already knew this. I just wanted to know why it wouldn't work without a pointer which is what the accepted answer explained much better.
    – m0meni
    Commented Apr 10, 2015 at 11:25
  • 3
    @AR7 They're both giving kind of the same explanation, just under two different approaches. If you declared it as a "regular" variable, then the first time a constructor were called, it would instantiate that to a new instance. But before it finishes instantiating it - before the the first one's constructor is finished - the member Node's own constructor would be called, which would instantiate another new instance...and you would get endless pseudo-recursion. It's not really so much a size issue in completely strict and literal terms, as it is a performance issue. Commented Apr 10, 2015 at 15:14
  • But all you're really wanting is just a way to point to whichever one's next in the list, not a Node that's actually inside the first Node. So you create a pointer, which is essentially how Java handles objects, as opposed to primitives. When you call a method or make a variable, Java doesn't store a copy of the object or even the object itself; it stores a reference to an object, which is essentially a pointer with a little bit of a kiddy glove wrapped around it. This is what both answers are essentially saying. Commented Apr 10, 2015 at 15:18
  • its not a size or speed issue - its an impossibility issue. The included Node object would include a Node object that would include a Node object... In fact it is impossible to compile it
    – pm100
    Commented Apr 10, 2015 at 15:21
  • 3
    @Panzercrisis I'm aware that they're both giving the same explanation. This approach, however, wasn't as helpful to me because it focused on what I already had an understanding of: how pointers work in C++ and how pointers are handled in Java. The accepted answer addressed specifically why not using a pointer would be impossible because the size can't be calculated. On the other hand, this one left it more vaguely as " a recursively defined structure." P.S your explanation that you just wrote explains it better than both :D.
    – m0meni
    Commented Apr 10, 2015 at 15:42
38

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.

2
  • 1
    To get something similar in Java would probably be "extends" if SuperNode extends Node, SuperNodes includes all Attributes of Node and has to reserve all the additional space. So in Java you cannot do "Node extends Node"
    – Falco
    Commented Apr 13, 2015 at 9:58
  • @Falco True, inheritance is a form of in-place inclusion of the base classes. However, since Java does not allow for multiple inheritance (unlike C++), you can only pull in an instance of a single other preexisting class via inheritance. That's why I wouldn't think of inheritance as a substitute for in-place member inclusion. Commented Apr 13, 2015 at 16:01
28

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.

5
  • 5
    Worse, no valid size exists: If k == sizeof(Node) holds and your type has data, it would also have to hold that sizeof(Node) = k + sizeof(Data) = sizeof(Node) + sizeof(Data) and then sizeof(Node) > sizeof(Node).
    – bitmask
    Commented Apr 9, 2015 at 16:27
  • 4
    @bitmask no valid size exists in the real numbers. If you allow transinfinites, aleph_0 works. (Just being overly pedantic :-))
    – k_g
    Commented Apr 11, 2015 at 6:02
  • 2
    @k_g Well, the C/C++ standard mandates that the return value of sizeof is an unsigned integral type, so there goes the hope of transfinite or even real sizes. (being even more pedantic! :p)
    – Thomas
    Commented Apr 11, 2015 at 12:59
  • @Thomas: One might even point out that there go even the Natural Numbers. (Going over the -pedantic top :p )
    – bitmask
    Commented Apr 12, 2015 at 18:02
  • 1
    In fact, Node is not even defined before the end of this snippet, so you cannot really use it inside. Allowing one to implicitly forward-declare pointers to an as of yet undeclared class is a little cheat that is allowed by the language in order to make such structures possible, without the need to explicitly cast pointers all the time. Commented Apr 13, 2015 at 3:45
13

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.

3
  • 4
    Worse, it would be logically impossible for an object to contain something of the same type. Commented Apr 9, 2015 at 16:20
  • Wouldn't there still technically be linking because it would be a node containing a node containing a node and so on?
    – m0meni
    Commented Apr 9, 2015 at 16:20
  • 9
    @AR7: No, containment means it's literally inside the object, not linked to it. Commented Apr 9, 2015 at 16:22
9

The approach that you describe is compatible not only with C++, but also with its (mostly) subset language C. Learning to develop a C-style linked-list is a good way to introduce yourself to low-level programming techniques (such as manual memory management), but it generally is not a best-practice for modern C++ development.

Below, I have implemented four variations on how to manage a list of items in C++.

  1. raw_pointer_demo uses the same approach as yours -- manual memory management required with the use of raw pointers. The use of C++ here is only for syntactic-sugar, and the approach used is otherwise compatible with the C language.
  2. In shared_pointer_demo the list management is still done manually, but the memory management is automatic (doesn't use raw pointers). This is very similar to what you have probably experienced with Java.
  3. std_list_demo uses the standard-library list container. This shows how much easier things get if you rely on existing libraries rather than rolling your own.
  4. std_vector_demo uses the standard-library vector container. This manages the list storage in a single contiguous memory allocation. In other words, there aren't pointers to individual elements. For certain rather extreme cases, this may become significantly inefficient. For typical cases, however, this is the recommended best practice for list management in C++.

Of note: Of all of these, only the raw_pointer_demo actually requires that the list be explicitly destroyed in order to avoid "leaking" memory. The other three methods would automatically destroy the list and its contents when the container goes out of scope (at the conclusion of the function). The point being: C++ is capable of being very "Java-like" in this regard -- but only if you choose to develop your program using the high-level tools at your disposal.


/*BINFMTCXX: -Wall -Werror -std=c++11
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <memory>
using std::cerr;

/** Brief   Create a list, show it, then destroy it */
void raw_pointer_demo()
{
    cerr << "\n" << "raw_pointer_demo()..." << "\n";

    struct Node
    {
        Node(int data, Node *next) : data(data), next(next) {}
        int data;
        Node *next;
    };

    Node * items = 0;
    items = new Node(1,items);
    items = new Node(7,items);
    items = new Node(3,items);
    items = new Node(9,items);

    for (Node *i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr << "\n";

    // Erase the entire list
    while (items) {
        Node *temp = items;
        items = items->next;
        delete temp;
    }
}

raw_pointer_demo()...
9, 3, 7, 1

/** Brief   Create a list, show it, then destroy it */
void shared_pointer_demo()
{
    cerr << "\n" << "shared_pointer_demo()..." << "\n";

    struct Node; // Forward declaration of 'Node' required for typedef
    typedef std::shared_ptr<Node> Node_reference;

    struct Node
    {
        Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {}
        int data;
        Node_reference next;
    };

    Node_reference items = 0;
    items.reset( new Node(1,items) );
    items.reset( new Node(7,items) );
    items.reset( new Node(3,items) );
    items.reset( new Node(9,items) );

    for (Node_reference i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr<<"\n";

    // Erase the entire list
    while (items)
        items = items->next;
}

shared_pointer_demo()...
9, 3, 7, 1

/** Brief   Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
    cerr << msg;
    bool first = true;
    for ( int i : container )
        cerr << (first?" ":", ") << i, first = false;
    cerr<<"\n";
}

/** Brief  Create a list, manipulate it, then destroy it */
void std_list_demo()
{
    cerr << "\n" << "std_list_demo()..." << "\n";

    // Initial list of integers
    std::list<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find( items.begin(), items.end(), 3), 8);
    show("B: ", items);

    // Sort the list
    items.sort();
    show( "C: ", items);

    // Erase '7'
    items.erase(std::find(items.begin(), items.end(), 7));
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}

std_list_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

/** brief  Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
    cerr << "\n" << "std_vector_demo()..." << "\n";

    // Initial list of integers
    std::vector<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find(items.begin(), items.end(), 3), 8);
    show( "B: ", items );

    // Sort the list
    sort(items.begin(), items.end());
    show("C: ", items);

    // Erase '7'
    items.erase( std::find( items.begin(), items.end(), 7 ) );
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}

std_vector_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

int main()
{
    raw_pointer_demo();
    shared_pointer_demo();
    std_list_demo();
    std_vector_demo();
}
2
  • The Node_reference declaration above addresses one of the most interesting language-level differences between Java and C++. In Java, declaring an object of type Node would implicitly use a reference to a separately allocated object. In C++, you have the choice of reference (pointer) vs. direct (stack) allocation -- so you have to handle the distinction explicitly. In most cases you would use direct allocation, although not for list elements. Commented Mar 21, 2017 at 14:54
  • Don't know why I didn't also recommend the possibility of a std::deque. Commented Apr 7, 2020 at 4:33
8

Overview

There are 2 ways to reference and allocate objects in C++, while in Java there is only one way.

In order to explain this, the following diagrams, show how objects are stored in memory.

1.1 C++ Items without pointers

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int          Code;
    char[50]     FirstName;
    char[50]     LastName;
    // "Address" IS NOT A pointer !!!
    AddressClass Address;
};

int main(...)
{
   CustomerClass MyCustomer();
     MyCustomer.Code = 1;
     strcpy(MyCustomer.FirstName, "John");
     strcpy(MyCustomer.LastName, "Doe");
     MyCustomer.Address.Code = 2;
     strcpy(MyCustomer.Address.Street, "Blue River");
     strcpy(MyCustomer.Address.Number, "2231 A");

   return 0;
} // int main (...)

.......................................
..+---------------------------------+..
..|          AddressClass           |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: Street            |..
..| [+] char[10]: Number            |..
..| [+] char[50]: POBox             |..
..| [+] char[50]: City              |..
..| [+] char[50]: State             |..
..| [+] char[50]: Country           |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..|          CustomerClass          |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: FirstName         |..
..| [+] char[50]: LastName          |..
..+---------------------------------+..
..| [+] AddressClass: Address       |..
..| +-----------------------------+ |..
..| | [+] int:      Code          | |..
..| | [+] char[50]: Street        | |..
..| | [+] char[10]: Number        | |..
..| | [+] char[50]: POBox         | |..
..| | [+] char[50]: City          | |..
..| | [+] char[50]: State         | |..
..| | [+] char[50]: Country       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

Warning: The C++ syntax used in this example, is similar to the syntax in Java. But, the memory allocation is different.

1.2 C++ Items using pointers

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int           Code;
    char[50]      FirstName;
    char[50]      LastName;
    // "Address" IS A pointer !!!
    AddressClass* Address;
};

.......................................
..+-----------------------------+......
..|        AddressClass         +<--+..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: Street        |...|..
..| [+] char[10]: Number        |...|..
..| [+] char[50]: POBox         |...|..
..| [+] char[50]: City          |...|..
..| [+] char[50]: State         |...|..
..| [+] char[50]: Country       |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|         CustomerClass       |...|..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: FirstName     |...|..
..| [+] char[50]: LastName      |...|..
..| [+] AddressClass*: Address  +---+..
..+-----------------------------+......
.......................................

int main(...)
{
   CustomerClass* MyCustomer = new CustomerClass();
     MyCustomer->Code = 1;
     strcpy(MyCustomer->FirstName, "John");
     strcpy(MyCustomer->LastName, "Doe");

     AddressClass* MyCustomer->Address = new AddressClass();
     MyCustomer->Address->Code = 2;
     strcpy(MyCustomer->Address->Street, "Blue River");
     strcpy(MyCustomer->Address->Number, "2231 A");

     free MyCustomer->Address();
     free MyCustomer();

   return 0;
} // int main (...)

If you check the difference between both ways, you'll see, that in the first technique, the address item is allocated within the customer, while the second way, you have to create each address explictly.

Warning: Java allocates objects in memory like this second technique, but, the syntax is like the first way, which may be confusing to newcomers to "C++".

Implementation

So your list example could be something similar to the following example.

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

.......................................
..+-----------------------------+......
..|            Node             |......
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................

Summary

Since a Linked List has a variable quantity of items, memory is allocated as is required, and, as is available.

UPDATE:

Also worth to mention, as @haccks commented in his post.

That sometimes, references or object pointers, indicate nested items (a.k.a. "U.M.L. Composition").

And sometimes, references or object pointers, indicates external items (a.k.a. "U.M.L. Aggregation").

But, nested items of the same class, cannot be applied with the "no-pointer" technique.

0
7

On a side note, if the very first member of a class or struct is the next pointer (so no virtual functions or any other feature of a class that would mean next isn't the first member of a class or struct), then you can use a "base" class or structure with just a next pointer, and use common code for basic linked list operations like append, insert before, retrieve from front, ... . This is because C / C++ guarantees that the address of the first member of a class or structure is the same as the address of the class or structure. The base node class or struct would only have a next pointer to be used by the basic linked list functions, then typecasting would be used as needed to convert between the base node type and the "derived" node types. Side note - in C++, if the base node class only has a next pointer, then I assume that derived classes can't have virtual functions.

0
6

Why is it better to use pointers in a linked list?

The reason is that when you create a Node object, compiler has to allocate memory for that object and for that the size of object is calculated.
Size of pointer to any type is known to compiler and therefore with self referential pointer size of object can be calculated.

If Node m_node is used instead then compiler has no idea about the size of Node and it will stuck in an infinite recursion of calculating sizeof(Node). Always remember: a class cannot contain a member of its own type.

0
5

Because this in C++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

is equivalent to this in Java

public static void main (..)
{
    MyClass myObjectReference = new MyClass();
}

where both of them create a new object of MyClass using the default constructor.

0

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

There is of course a trivial answer.

If they didn't link one node to the next by a pointer, they wouldn't be linked lists.

The existence of linked lists as a thing is because we want to be able to chain objects together. For example: we already have an object from somewhere. We now want to put that actual object (not a copy) at the end of a queue, for example. That is achieved by adding a link from the last element already on the queue to the entry we are adding. In machine terms, that's filling in a word with the address of the next element.

Not the answer you're looking for? Browse other questions tagged or ask your own question.