Implementing sequence abstraction

Below is the code that implements sequence abstraction using type abstraction Sequence (in Java):

```
/**
*
* @author mohet01
*
* @param
*/
public class Sequence{

/**
* Abstract data type constitutes constructor and selector functions
* written below under representation that hold below invariant:
* If a recursive list s is constructed from a first element f and a recursive list r, then
* • first(s) returns f, and
* • rest(s) returns r, which is a recursive list.
*/

/ Representation - start /

//private static Sequence emptyList = null;
private T item;
private Sequence restOfTheList;

/**
* Constructor
* @param first
* @param rest
*/
public Sequence(T first, Sequence rest){
this.item = first;
this.restOfTheList = rest;
}

/**
* Selector function
* @param list
* @return
*/
private T first(){
return this.item;
}

/**
* Selector function
* @param list
* @return
*/
private Sequence rest(){
return this.restOfTheList;
}

/ Representation - end /

/ User interface - starts /
/ These methods MUST take help of constructor or selector./

/**
* length of the list
* @return
*/

public final int length(){
return this.lengthOfTheList(0);
}

private final int lengthOfTheList(int length){
if(this.rest() == null){
return length + 1;
}else{
return this.rest().lengthOfTheList(length + 1);
}
}

/**
* Get an item from the given position.
* @param position
* @return
*/
public final T getItem(int position){
if(position == 1){
return this.first();
}else{
return this.rest().getItem(position - 1);
}
}

/**
* Create a new sequence after deletion of an item at given position
* @param

Minor bug

/**
 * Get an item from the given position.
 * @param position
 * @return
 */
public final T getItem(int position){
    if(position == 1){
        return this.first();
    }else{
        return this.rest().getItem(position - 1);
    }
}

You need to do a lower-bound check here, namely since your Sequence is a 1-index based implementation, you need to make sure position >= 1. Passing 0 here will result in NullPointerException eventually.

Length checks

Deriving the Sequence length can probably be better expressed as:

return 1 + (rest() == null ? 0 : rest().length());

It's easier to literally express this as "length of sequence is myself and what follows behind", instead of relying on a helper method...

Unit tests

Please create more unit tests to test the expected behavior for unexpected positions, e.g. 0, negative values, far greater than length(), etc.

Performance


Above code is not measured/intend to write space/time efficient code.

Ok... but still, the performance is really bad... inserting and calculating the length of a Sequence is nowhere near instantaneous.

Other comments

IMO, your implementation depends heavily on knowing the exact positions or length of a Sequence at any time, it will facilitate the usage if you have wrapper methods to add to the front, the back, or even just a constructor that accepts only a seed value. Also, do consider implementing the Iterable interface, so that users of Sequence can iterate through them.

StackExchange Code Review Q#84745, answer score: 5