Using composition or inheritance to enhance this linked list Problem Statement:


  A method called insertEnd() exists, but it runs in linear time, because every time it is called, it walks down the list to find the end.  Without changing the meaning of this method or any other, modify the representation of a SList and whatever methods are necessary to make insertEnd() run in constant time. Your SList class will need to continually maintain a record of the last (tail) SListNode in an SList, and all SList's methods will have to ensure that this record stays current.


SList class &amp; SListNode class are already provided in the assignment as shown below:

SListNode

/* SListNode.java */
class SListNode {
  Object item;
  SListNode next;


  /**
   *  SListNode() (with two parameters) constructs a list node referencing the
   *  item "obj", whose next list node is to be "next".
   */

  SListNode(Object obj, SListNode node) {
    item = obj;
    this.next = node;
  }

  /**
   *  SListNode() (with one parameter) constructs a list node referencing the
   *  item "obj".
   */

  SListNode(Object obj) {
    this(obj, null);
  }
}




SList

/* SList.java */

  public class SList {

  protected SListNode head;
  protected int size;

  /**
   *  SList() constructs an empty list.
   **/

  public SList() {
    size = 0;
    head = null;
  }

  /**
   *  insertFront() inserts item "obj" at the beginning of this list.
   *  @param obj the item to be inserted.
   **/

  public void insertFront(Object obj) {
    head = new SListNode(obj, head);
    size++;
  }

  /**
   *  insertEnd() inserts item "obj" at the end of this list.
   *  @param obj the item to be inserted.
   **/

  public void insertEnd(Object obj) {
    if (head == null) {
      head = new SListNode(obj);
    } else {
      SListNode node = head;
      while (node.next != null) {
        node = node.next;
      }
      node.next = new SListNode(obj);
    }
    size++;
  }
}




Below is the solution for the given problem:

TailList

/* TailList.java */

public class TailList extends SList{
    private SListNode tail;

    public TailList(){
        tail = null;
    }

    /**
     *  insertEnd() inserts item "obj" at the end of this list.
     *  @param obj the item to be inserted.
     **/

    public void insertEnd(Object obj) {
        if(this.size &gt; 0){
            SListNode node  = new SListNode(obj);
            this.tail.next = node;
            this.tail = node;
        }else{
            this.head = this.tail = new SListNode(obj);
        }
        this.size++;
    }

    /**
     *  insertFront() inserts item "obj" at the beginning of this list.
     *  @param obj the item to be inserted.
     **/

    public void insertFront(Object obj){
        super.insertFront(obj);
        if(size == 1){
            tail = head;
        }
    }
}


My question:

Does TailList class inheritance relation with SList implementation class looks fine(within same package)? How do I know whether SList class is specifically designed for inheritance, as mentioned below?


  It is safe to use inheritance within a package, where the subclass and the superclass implementations are under the control of the same programmers. It is also safe to use inheritance when extending classes specifically designed and documented for extension
  (Item 17). Inheriting from ordinary concrete classes across package boundaries,
  however, is dangerous. As a reminder, this book uses the word “inheritance” to mean implementation inheritance (when one class extends another). The problems discussed in this item do not apply to interface inheritance (when a class implements an interface or where one interface extends another).
Considering that…


You have full access to the source code of the original SList class
To make inheritance work, you had to edit SList.java to change head and size from private to protected access
The assignment asks you to "modify the representation of SList"
The resulting class performs the same task as the original code, adding no new functionality (just a large performance optimization for insertEnd() with a negligible cost to insertFront())


I see no reason to use either inheritance or composition.  Just edit SList.java directly to modify its implementation.  The resulting SList class should be fully substitutable with the original, just with better performance characteristics.