-2

I just saw an implementation of a linked list in Java (http://www.danielacton.com/Data-Structures/Linked-List/Java/), and here's what a node looked like: 

      private class ListNode {
         private Object data;
         private ListNode next;
      }

What the heck is that????

The size of a ListNode must be infinity bytes, if you think about the logic here. Shouldn't the ListNode hold the address of another ListNode?

user3443528
  • 47
  • 3
  • 8
    All Java variables other than primitives are reference variables. This means they act a bit like C/C++ pointers, except that they don't need to be explicitly dereferenced. Here, one `ListNode` contains a _reference_ to another. A reference variable can also be null, just like a C/C++ pointer. – Dawood ibn Kareem Mar 24 '14 at 21:49
  • If there is no next node, just say that next is null. – nimsson Mar 24 '14 at 21:50
  • 1
    Please improve your question title. It should summarize your actual question, not your frustrations. The better your question title and tags, the better your chances of attracting experts knowledgeable in the subject of your question. – Hovercraft Full Of Eels Mar 24 '14 at 21:51
  • What if I need to iterate through the elements of an array and do something with them???? Do I have to make calls to arr[0], arr[1], etc.??? That's inefficient. – user3443528 Mar 24 '14 at 21:52
  • 1
    Oh, but @Hovercraft, he/she has already attracted _you_ here! – Dawood ibn Kareem Mar 24 '14 at 21:54
  • 1
    Consider going through a Java language tutorial before asking questions like this. You're not "thinking about the logic" here -- there's no logic that says these are stack variables. You're just looking at a different language where this code means something different than it does in C++. – Ismail Badawi Mar 24 '14 at 21:54
  • @user3443528 not at all... `for (final X element: thearray)` – fge Mar 24 '14 at 21:55
  • Objects in Java work somewhat like references in C++. They hold the address of the object, not its contents. – David Conrad Mar 24 '14 at 21:55
  • @DavidWallace: and I'm not even an expert in "What the heck is this" questions. – Hovercraft Full Of Eels Mar 24 '14 at 21:57
  • 1
    Maybe we need a `heck` tag, @HovercraftFullOfEels. – David Conrad Mar 24 '14 at 21:58

3 Answers3

1

That's one of the confusing things about going from C++ to Java. In Java,

private ListNode next;

declares a reference variable, most closely compared to a ListNode& reference in C++. This is one way of creating a linked list in Java - have a node store the data and the reference to the next item.

Note that in Java, the default value (if uninitialized) of next would be null.

For this to take blow up the way you think, it would have to be:

private ListNode next = new ListNode();

which would eventually result in a StackOverflowError.

rgettman
  • 176,041
  • 30
  • 275
  • 357
  • "most closely compared to a ListNode& reference" <-- uh NO! After that, people will imagine that Java can do pass by reference! – fge Mar 24 '14 at 21:52
  • 1
    All analogies are wrong; some analogies are useful. – David Conrad Mar 24 '14 at 21:57
  • @fge My analogy to a C++ reference certainly isn't perfect, and that's one discrepancy in it. But it's certainly not a C++ pointer, on which an explicit dereference is necessary to get the actual object, and on which pointer arithmetic can be done. Neither of those can be done in Java. I think my analogy is "useful enough", and we can always include the obligatory link to [Is Java “pass-by-reference”?](http://stackoverflow.com/questions/40480/is-java-pass-by-reference) when necessary. – rgettman Mar 24 '14 at 22:03
0

The default value of the variable ListNode next; is null, meaning it does not actually point to a ListNode Object until you assign one to the variable. So no - there is no infinite loop.

KyleM
  • 4,445
  • 9
  • 46
  • 78
0

When you:

X whatever;

where X is a class, whatever is a reference, not a full object. This is unlike C and C++ where you can have full structs on the stack.

Although this is not technically exact, you can see them as C/C++ pointers. Except that you use dot for "indirections".

fge
  • 119,121
  • 33
  • 254
  • 329