4
\$\begingroup\$

This is what my class hierarchy looks like. I have an abstract superclass, AbstractLinkedMyList, that contains common operations for both sorted and unsorted linked list.

Here's the declaration for it and the method I have a question about:

public abstract class AbstractLinkedMyList<Type> implements MyList<Type> {
    protected ListNode<Type> front; 
     protected ListNode<Type> back;


public void insertAtIndex(int index, Type value) {
        checkOkToInsertAtIndex(index);
        if (size == 0) {
            ListNode<Type> newNode = new ListNode<Type>(value);
             front = back = newNode;
         }
        else {
            if (index == 0) {
                   ListNode<Type> newNode = new ListNode<Type>(value, front);
             front = newNode;
            }
           else {
                  ListNode<Type> current = nodeAt(index - 1);
                  ListNode<Type> newNode = new ListNode<Type>(value, current.next);
                 current.next = newNode;
                 if (index == size) {
                     back = newNode;
                 }
            }       
       }
   size++;
    }
     protected ListNode<Type> nodeAt(int index) {
         ListNode<Type> current = front;
         for (int i = 1; i <= index; i++) {
                current = current.next;
          }
         return current;
    } 
  protected static class ListNode<Type> {
        public Type data;
        public ListNode<Type> next;  
        public ListNode(Type data) {
             this(data, null);
        }
        public ListNode(Type data, ListNode<Type> next) {
             this.data = data;
             this.next = next;
        }
     }
    ..... 
}

Here is my declaration for the sorted linked list:

public class LinkedListSorted<E extends Comparable<E>> extends AbstractLinkedMyList<E>

My question is about the insertAtIndex method. I chose to put the insertAtIndex method in the abstract superclass because this would be how you insert something at an index, no matter what the subclass is (sorted vs unsorted). I realized that in the sorted linked list class, I will have to extend this method to impose restrictions(to not break sorted property of the list).

This is my insertAtIndex method (what I have so far) in the sorted linked list:

public class LinkedListSorted<E extends Comparable<E>> extends AbstractLinkedMyList<E>
@Override
public void insertAtIndex(int index, E value) {
    if(index == 0 && front != null && value.compareTo(front.data) > 0) {
        throwSortException();
    } 
    if(index == size && value.compareTo(back.data) < 0) {
        throwSortException();
    } 
    if(index > 0 && index < size) {
        ListNode<E> before = nodeAt(index - 1);
        if(value.compareTo(before.data) < 0 || value.compareTo(before.next.data) > 0) {
            throwSortException();
        }
    }
    super.insertAtIndex(index, value);
}

My logic here is here are all the cases where you cannot insert (would break the sorted property of the list). If you can make it past all these cases, I will allow insertAtIndex, whose implementation is in the abstract superclass (explained is this decision above).

Would this be good code design? One drawback I saw right away was that my check logic involved a lot of iteration. You would need to this iteration again if you actually wanted to insert. But then if you put the insert logic in the check case, you would be rewriting code (not taking advantage of code reuse). How would you weight the two? Is what I have acceptable?

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

No, it would not be good design. That method signature says "you can insert an element at any point in the list" and then the body says "but only if it's the place I want you to put it." This is why the Collections API doesn't have a sorted list, but rather allows lists to be sorted. Sorted and Unsorted lists share some contract, but insertion is fundamentally different for them. Unless your assignment requires it, I would not put them in the same inheritance hierarchy, and I'd be leery of putting them under the same interface (contract) unless it didn't include addition of elements.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.