Why C++ uses pointer for next node in linked list, but langauges like C# or Java use just the name of the class Node?

Question

Most of the linked list implementations in C++ are like this, a pointer reference will be used as the type for the "next" node

class Node {
public:
    int data;
    Node* next;
}

But for languages like C#, Java and Python, why pointer is is not directly used? I could see only this kind of implementation:

// C#
class Node {
    int data;
    Node next;
}

// Java
class Node {
    int data;
    Node next;
}

What is the underlying difference? Ofcourse Java doesn't support pointers, but what about c#?

Answer 1

CPP"s Node* is equivalent to java's Node, and I'm pretty sure C#'s Node as well. In java, all primitives are the direct value. The primitives are int, long, short, byte, char, double, float, and boolean. These are passed directly, by value: If you call a method passing 5, 5 is pushed onto the stack. If the method you invoke changes their value, the caller can't tell.

But aside from that hardcoded list of primitives, all other types are called references which is just java-ese for pointers - except in java, you can't do pointer arithmatic. at all. You can't ask for 'the memory location 5 higher than where-ever this object lives', like you can do in C.

Here's a trivial example:

class Example {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("Hello!");
        System.out.println(list);
        example1(list);
        System.out.println(list);
        example2(list);
        System.out.println(list);
    }

    static void example1(List<String> in) {
        list.add("World!");
    }

    static void example2(List<String> in) {
        in = new ArrayList<String>();
        in.add("Bye!");
    }
}

This will print:

[Hello!]
[Hello!, World!]
[Hello!, World!]

example1 never changes the variable (The reference), it merely 'dereferences it' (follows the pointer), thus the changes you make are observed in the caller.

But example2 has no effect on main's list variable: It reassigns the variable (makes a new object and then updates its reference to point at this new object). example1's list doesn't change; its pointer doesn't change.

It's like treasure maps: Everybody has a copy of the treasure map, but not of the treasure. in.add is like: "Follow the map, open the treasure chest, put a new item in". in = new ArrayList is: "Make a new treasure chest, bury it in the sand, wipe out this treasure map, and now write the location of this newly buried treasure chest on it". If I have a copy of your map, if you follow your copy and add to the treasure then I'll see that if I later follow my map. But if you make an entirely new map, then whatever you do to the treasure at your new location is never going to be noticed by me.

This matches C++'s behaviour.... at least, for Node*. Not for Node.

Answer 2

What is the underlying difference?

Probably none at all. At the machine-code level, each node contains the address of the next node in the chain.

The question is, rather, about how languages represent objects in source code. Is a variable declaration written as Foo bar (for example) going to be an actual instance of the type Foo or is it going to be a way to get at (handle, pointer, reference) the actual instance. If it's the actual instance, your language probably also needs some syntax to describe not-the-instance but way-to-get-at-the-instance. Perhaps more than one way (Foo*, Foo& in C++).

The possibility of different approaches is one reason why we have different programming languages.

Answer 3

In C++ variables (objects) can be passed by three ways:

• by value
• by pointer
• by reference

(all of them are in reality passed by value, but very specific one)

In e.g. Java, objects are always passed by reference, while primitives by value. There are no pointers or explicit references in Java.

In C++ when you stop needing an object, you need to use delete to remove it. In Java, you just need to replace variable or just don't use it - GB will remove it for you.

Answer 4

After reading the posted answers and other stackoverflow stuffs related to references and pointers like this one C++ references Vs C# references

This is what Makes more sense to me,

• C# References are Managed references. But in C++ there is no such manged environment hence we need to allocate and carefully de-allocate the memory. In C# this will be manged automatically by GC. So it is recommended to use references where ever possible rather than directly using pointers.

• Similar to C++ Pointers, C# can also hold nulls. C++ pointers hold address of a memory location, C# References holds the address of another object in the memory.

• In C# we can use pointers only under unsafe scope, and in java there is no such pointer concepts.

Taking all this into account we can use references rather than pointers for programming languages that execute in a managed environment.

Feel free to edit if this answer can be further improved!