Using composition or inheritance to enhance this linked list

Question

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 & 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 > 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).

• 200_success: As I interpret the problem statement, you're free to just edit the code of SList directly.
• overexchange: @200_success As per the assignment, head & size are private. I guess, same package mean a single programmer would have control over existing classes. Thank you for rephrasing my question title.
• overexchange: Shall i make private SListNode tail; as protected SListNode tail;?

Answer 1

Considering that...

1. You have full access to the source code of the original SList class
2. To make inheritance work, you had to edit SList.java to change head and size from private to protected access
3. The assignment asks you to "modify the representation of SList"
4. 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.

• overexchange: Ok. With current problem statement, To enhance the insertEnd() performance, we came up with new subclass TailList. But there would be new problems given in future to embed in same class TailList which can't be forecasted right now. So, considering that, Would i not think about how TailList would be presented? Another point is, When we introduce subclass, the invariants that parent class enforces should also be enforced by sub class.
• 200_success: For all practical purposes, having a TailList class can do no good. All it does is introduce a slightly incompatible data representation — if you happen to have existing SLists in a program, you can't cast it to TailList. I don't see where the exercise asks you to use inheritance, and if it did, it would be a silly exercise of little educational value.
• overexchange: yes, you are right, we do not require new subclass, if we add tail as member to SList, it does not add any performance degradation in Slist class.
• overexchange: ya, inheritance concept is being introduced with this wrong example, which is surprising. lecturelink
• overexchange: one important question, if SList is owned by different team(different package) within the same organization where they used protected fields for head & size. How would i approach to resolve this performance problem of insertEnd() to use SList in my package?