How to get a sublist without using the sublist method in java

Question

This is what I have right now:

public ArrayList subList(int fromIndex, int toIndex){
      ArrayList a = new ArrayList();
      for (int i=fromIndex;i<toIndex;i++) {
          a.add(stuff[i]); //stuff is a array of strings
      }
    return list;
  }

But is it possible to return the sublist without creating a new array? I am restrict from using any methods from the Array/ArrayList class.

Answer 1

I assume you have to return the standard ArrayList, and not your own version of ArrayList, and I assume that 'stuff' is an array, not a list.

First off, get bonus points for making the ArrayList have the initial size of the array (toIndex - fromIndex). For more bonus points, make sure that the to and from indecies actually exist in 'stuff' otherwise you get a nice crash.

ArrayList uses an internal array for its storage and you can't change that so you have no choice but to create a copy.

EDIT You could make things interested and much more complex but it'll impress someone... Do it by creating your own ArrayList class implementing List. Get it to use that original array. Pretty unstable since if that array is modified somewhere else externally, you're in trouble, but it could be fun.

Answer 2

To avoid creating a new list for storage, you would have to pass in a reference to the original list, keep the sublist, and then delete the remaining items from from the list, but this would leave the list missing those other items.

If that isn't your goal you will have to create a new list at some point to hold the sublist.

Answer 3

There's three sensible things you could return. An array, a List, or an Iterator. If my assumption that you're supposed to re-implement subList was correct, then there's no way around creating the new ArrayList.

Answer 4

A sublist is "a new list", so you'll have to create something to represent the sublist of the array. This can either be a new array or a list. You chose an ArrayList which looks good to me. You're not creating a new array (directly), so I don't actually get that point of your question. (If you want to avoid creating a new array indirectly through ArrayList, choose another List implementation, LinkedListfor example)

If you're looking for slight improvements:

• Consider passing the source array as a method parameter. Now stuff[] is a static field.
• Consider initializing the new ArrayList with the size of the sublist (toList-fromList+1)
• Consider using generics (only if you already now this concept). So the return type would be ArrayList<String>

Answer 5

If you want have the same behaviour as the Java subList method you need to retain a pointer to the original list and use an offset and length to index into the original list.

Heres a start showing the implementation of the get method.

public class SubList extends AbstractList {
    private final List original;
    private final int from;
    private final int to;
    public SubList(List original, int from, int to) {
        this.original = original;
        this.from = from;
        this.to = to;
    }

    public Object get(int i) {
        if (i < 0 || i > to - from) {
            throw new IllegalArguementException();
        }

        return original.get(from + i);
    }
}

public static List subList(List original, int from, int to) {
    return new SubList(original, from, to);
}