Simple Java List Question

Question

I am supposed to create an iterative method stretch that takes a positive number n as a parameter and returns a new ListItem beginning a list in which each of the numbers in the original list is repeated n times. For example, if the original list is ( 6 7 6 9 ) and the parameter value is 2, then the new list returned is ( 6 6 7 7 6 6 9 9 ).

I already have a listitem constructor that has the value at that node and the reference to the next:

   ListItem(int number, ListItem next) {
        this.number = number;
        this.next   = next;
}

My code looks like this:

    public ListItem stretch(int n) {
  //make an array of list items that is n times bigger than the original one.
     ListItem[] newList = new ListItem[this.length() * n];

 //Then loop through the old list one value at a time. At each value do a second loop n times to stretch

     int index = 0;
     int counter = 0;
     for(int i = 0; i < this.length(); i++){
         while(counter++ < n){
             newList[index++] = this[i];*************************
     }
     return newList;****************
 }

}

There are two problem points, at which I starred the lines. I am supposed to return a listitem, but NewList is an array. ANd I'm not sure what is wrong with the first starred line.

Any help/guidance would be appreciated.

Answer 1

Homework?

It looks like you are supposed to be building a linked list but you are instead building an array of ListItems. An Array of ListItems isn't bad, but you need to make each ListItem's next value point to the next item in the list.

Then the last line of your function will return the first item in the list.

Answer 2

The first starred line is most certainly wrong, but that is not your problem if you think about it: you are not asked to return an array in the first place.

The problem on how to return a ListItem should solve itself if you consider what your input really looks like: take a sheet of paper, and draw it, and you'll see why returning a single list item is enough, and what do on the ListItem to get each item doubled.

Answer 3

The problem with the first line is that since this isn't an array, you can't subscript it ([i]). I cannot help you with that problem without more details about your ListItem class. Are you making a linked list?

For the return, you probably want to return the first item in the array. If so, change it to return newList[0]. If you want to return the array, change the function to return the array, like this: public ListItem[] stretch(.

Answer 4

The best way to approach this problem is to draw some pictures. Then try to break the problem into sub-problems. Let's start with the simple case: a list of length 2:

ListItem two = new ListItem(1, ListItem(2, null));

Here's one picture

two = ( number == 1
      ( next   == ( number == 2
                  ( next   == null

Here's another picture:

+---+  +---+    The "/" here is the "null" above, which terminates the list.
| 1 |->| 2 |-/  
+---+  +---+    

Think of it this way: a list consists of a first ListItem, which points to the rest of the list via "next". The empty list, then is null and the "next" of the last ListItem is always empty. (null).

Now what's really going on when we're asked to "stretch" a list? Say, by 2?

Well, the empty list is easy, it doesn't change. But it's also irrelevant since null.stretch() will end badly in the language you're using. The list of length 1 then is our simplest practical case:

we have:

we have       we want

+---+         +---+   +---+
| 1 |-/       | 1 |-->| 1 |-/
+----         +---+   +---+

Ok, that's not so hard. We already have a list of length one. All we need to do hang it off the next of a new ListItem and we'll have a list of length two. Clearly we need the ability to add something to an existing list. Adding it to the front is easiest, so we'll define a little helper for that:

ListItem addItemToFront(int number) {
    return new ListItem(number, this);
}

Ok, now let's code that up and call it stretchFirstItemByOne:

ListItem stretchFirstItemByOne() {           
    return this.addItemToFront(this.number); 
}

You'll see me use this.something() a lot in these examples, though it isn't necessary. I'm just trying to be clear that these are method calls on the current object (this).

But, supposing we want to stretch by some larger n? You've already tried -- somewhat haplessly -- to use a for loop above. You could do that. But I'm going to do it differently.

ListItem stretchFirstItem(n) {
    if (n == 1)      // stretching to length 1 means nothing
        return this; // to do. just return this.
    else {
        // well, if we stretch our item to length n-1 first
        // then all we have to do is stretch it by one and
        // we're done.
        return this.stretchFirstItem(n-1).stretchFirstItemByOne(); 
    }
}

Stop and think about that one. Rewrite it as a for loop if you're having trouble.

That's all very nice, you might say, but it only handles lists of length one. How true, how true.

Suppose you had a list of length 3 and you wanted to stretch it by 2.

  +---+  +---+  +---+
( | 1 |->| 2 |->| 3 |-/ ).stretch(2)
  +---+  +---+  +---+

Tough? Well, we can get started at least. We know how to handle things if the list has only one item:

ListItem stretch(int n) {
    ListItem restOfList = this.next;
    if (restOfList == null) { // this list has length one
        return this.stretchFirstItem(n);
    } else {
        // if we had the rest of the list stretched, then we could
        // add this.number to the front of this stretched list, stretch
        // that first item and then we'd be done.
    }
}

Hey, but isn't stretch supposed to do that for us, you know, stretch whole lists? Couldn't we use that to stretch the rest of the list so we can do the easy bit and stretch the first item? But we haven't even finished writing stretch yet -- I mean -- it doesn't work. It couldn't be that easy, could it? Could it?

ListItem stretch(int n) {
    ListItem restOfList = this.next;
    if (restOfList == null) { // this list has length one
        return this.stretchFirstItem(n);
    } else {
        return restOfList     //-------------------------
           .magic(...)        // Left as an exercise for
           .moreMagic(...)    // the reader.
           .zyzzy(...);       //-------------------------
    }
}