Does this textbook linked list involve a "recursive constructor"?

Question

This is a snippet from a linked list class from a textbook implementation:

public class ListItem
{
  Object   item;                  
  ListItem next;                  

  public ListItem(Object item) 
  {
    this.item = item;             
    next      = null;                  
  }
}

It looks like recursion--class ListItem has instance variable also named ListItem. Is it proper to call this recursion?

Here's how I once defined a linked list in Pascal. I see a hint of what you might call recursion (pNodeType, a.k.a. ^NodeType), but it doesn't feel like what's above in the Java snippet :

type
    **pNodeType** = ^NodeType ;  

    NodeType = record        
      name : string ;        
      next : **pNodeType** ;  // conceptually, change the type to **^NodeType**
    end ;

So I guess since Java lacks pointers and objects are references, I'm looking at the same thing after all. Right?

And so if I wanted a doubly-linked list (backward, too), I'd add an instance variable like so

ListItem prev;

and add a line of code to the constructor like so

prev = null;

and exercise the same amount of care that made the forward linkage work.

Right?

And finally if I wanted a generic linked list, I'd just change the snippet like so and change all occurrences of "Object" to "E" in the methods):

public class ListItem<E> {

  E item;                    
  ListItem next;                     

  public ListItem(E item) {
    this.item = item;                              
    next = null;                                   
  }
}

Right?

I can't see any recursion - the constructor doesn't call itself. And there's nothing wrong with having an instance of the same type - it would be pretty hard to implement a Linked List otherwise! — James Bassett, Oct 03 '13 at 23:26
Recursion is purely a runtime concept. See [this answer](http://stackoverflow.com/a/1949502/18157) — Jim Garrison, Oct 03 '13 at 23:37
You are right, despite the strange comments of others. Lists are recursive data structures, there is recursion at the data type level, and this leads to recursive algorithms (even if they are implemented using recursion degenerated into loops). That being said, constructors as such are not recursive functions. — Ingo, Oct 03 '13 at 23:39
Exactly, @Ingo. Denotational semantics has to use a fixed point operator to model a type like this one. — Judge Mental, Oct 04 '13 at 00:55

Bohemian · Answer 1 · 2013-10-03T23:44:20.087

1

There is no recursion.

While you declare a field of the same type as the class, you don't instantiate an instance.

Had your constructor included initialization:

next = new ListItem(null);

Or the declaration included initialization:

ListItem next = new ListItem(null);

There would be recursion

Regarding the generic question, you need to type the field too:

public class ListItem<E> {

  E item;                    
  ListItem<E> next;  // Added generic parameter                

  public ListItem(E item) {
    this.item = item;                              
  }
}

Note that you don't need to code:

next = null;  // redundant

Because the default initialized value is null already.

edited Oct 03 '13 at 23:44

answered Oct 03 '13 at 23:37

Bohemian

412,405
93
575
722

I didn't downvote, but I don't see any recursion in your code either. – Jim Garrison Oct 03 '13 at 23:44
@jim huh? Isn't my example recursive? (Make sure you refresh ) – Bohemian Oct 03 '13 at 23:49
Downvote, because you said "there is no recursion". There is recursion in every case when you reference the name of the very thing you are just defining, be it a function or a data type or something completely different. (It is not as if recursion is a recent invention of the computer age, you know ....) – Ingo Oct 04 '13 at 00:37
@lngo there is no recursion during *construction*, which is what this question is about, because there is no instantiation of own class during construction. Just declaring a field of own class is not recursion. – Bohemian Oct 04 '13 at 01:31
I just looked up "recursion" in a dictionary: Recursion: see Recursion – DSlomer64 Oct 05 '13 at 01:56
(Bohemian:) With or without the (as in ListItem) my (now-doubly-)linked list seems to work correctly. Is some case lurking that will force me to have it? Or is it just cleaner/better practice? (I won't pretend that I understand just now.) – DSlomer64 Oct 05 '13 at 02:03
Without typing the list, you'll need casting to return the value from the node. Google "raw types" - there can be quite a difference, but in your case it may be restricted to casting – Bohemian Oct 05 '13 at 03:05

Does this textbook linked list involve a "recursive constructor"?

1 Answers1