3
\$\begingroup\$

As per the definition given in lecture, ADT is,

enter image description here

With reference to this definition, I would like to call SList class an ADT following 6 invariants:

  1. Multiple users of SList class should be consistent in usage with same SList instance. For example multiple users may insert items in same shopping list.
  2. No runtime exceptions while using SList class when list is empty.
  3. SList size member variable is always correct.
  4. SList is never circularly linked list.
  5. SList never returns SListNode, instead it return only an item.
  6. Methods of the SlistNode class can be modified in future without any affect to SList class users. I guess this is nothing but encapsulation.

The below two classes will be part of a package and be used by classes from other packages:

class SListNode{
    Object item;
    SListNode next;
    public SListNode(){
        this.item = null;
        this.next = null;
    }
    public SListNode(Object item, SListNode next){
        this.item = item;
        this.next = next;
    }
    public SListNode(Object item){
        this(item,null);
    }
    public void insertAfter(Object item){
        this.next = new SListNode(item,this.next);
    }
    public SListNode nth(int position){
        if(position ==1){
            return this;
        }else if((position < 1) || (this.next == null)){ /* error checking */
            return null;
        }else{
            SListNode tempNode = this.next.nth(position-1);
            return tempNode;
        }
    }

}

public class SList {
    private SListNode head; // First node in list.
    private int size; // Number of items in list.
    public SList() { // Here’s how to represent an empty list.
        head = null;
        size = 0;
    }
    public void insertFront(Object item) {
        head = new SListNode(item, head);
        size++;
    }
    public void insertEnd(Object item){
        SListNode lastNode = this.head;
        while(lastNode.next != null){
            lastNode = lastNode.next;
        }
        lastNode.next = new SListNode(item,lastNode.next);
        size++;
    }
    public void insertAt(Object item, int position){
        if (position == 1){
            insertFront(item);
            size++;
        }else if(position < 1){
            System.exit(1);
        }else{
            SListNode currentNode = this.head.nth(position);
            if(currentNode != null){
                currentNode.insertAfter(item);
                size++;
            }else{
                System.exit(1); //position value exceeds 
            }
        }
    }
    public Object nth(int position){
        if(position < 1){
            return null;
        }else{
            SListNode tempNode = this.head.nth(position);
            if(tempNode != null){
                return tempNode.item;
            }
            else{
                return null; 
            }
        }
    }

    public boolean isEmpty(){
        return (size==0);
    }
}

My question: With reference to SList class as shown above, Can you please confirm if my interpretation of definition of ADT is correct? If the interpretation is wrong, What code changes would you like to see, to call SList as an ADT?

Note: I am yet to learn exception-handling, interfaces, inheritance, polymorphism and composition in class.

\$\endgroup\$
  • \$\begingroup\$ -1: Various bugs were found, leading me to believe that you failed to adequately try to confirm that your code works as intended. \$\endgroup\$ – Pimgd Sep 16 '14 at 12:00
  • 1
    \$\begingroup\$ Reading your last note, it seems I'm a bit overly harsh (removed downvote). I recommend getting a full understanding of the language and its features first though, because any comments we make will go over your head (such as throwing exceptions and providing proper API methods) \$\endgroup\$ – Pimgd Sep 16 '14 at 12:07
  • \$\begingroup\$ @Pimgd I like how you support your downvotes by leaving comments, but maybe sometimes before downvoting someone's question or answer it's better to point out a mistake? It just could be that it's not done on purpose. And when you make sure the mistake is intentional you can go ahead and downvote... \$\endgroup\$ – zafarkhaja Sep 16 '14 at 12:24
  • \$\begingroup\$ @zafarkhaja I believe that a simple for loop would have found the bug. for(int i = 0; i < 10; i++){ slist.insertAt(i, i); } fails, because slist is 1-indexed. Start i at 1, it still fails. I believe there has been 0 testing, which for me would invalidate the premise "To the best of my knowledge, does this code work?". Only later did I realize that the asker in question (haha) is still learning. I then lowered my expectations and standards a bit and took on a different tone. \$\endgroup\$ – Pimgd Sep 16 '14 at 12:27
  • \$\begingroup\$ @Pimgd Apologise for lowering your expectations and standards a bit. \$\endgroup\$ – overexchange Sep 17 '14 at 5:47
8
\$\begingroup\$

Bug:

public void insertEnd(Object item){
    SListNode lastNode = this.head;
    while(lastNode.next != null){
        lastNode = lastNode.next;
    }
    lastNode.next = new SListNode(item,lastNode.next);
    size++;
}

Make a new list, add to end. this.head is null, so lastNode.next is a NullPointerException.

Bug:

public void insertAt(Object item, int position){
    if (position == 1){
        insertFront(item);
        size++;
    }else if(position < 1){
        System.exit(1);
    }else{
        SListNode currentNode = this.head.nth(position);
        if(currentNode != null){
            currentNode.insertAfter(item);
            size++;
        }else{
            System.exit(1); //position value exceeds 
        }
    }
}

Make new list, insertAt("hello", 1), insertAt("world", 2). The application shuts down.

Please test your code before putting it up for review. You'll get higher grades too, especially if you show your tests to your professor or whoever is teaching you.

\$\endgroup\$
  • \$\begingroup\$ Why not close the question if there's bugs instead of answering? \$\endgroup\$ – IEatBagels Sep 16 '14 at 12:16
  • 1
    \$\begingroup\$ @TopinFrassi As per the help center, "To the best of my knowledge, does the code work?" is the criteria we use. From the question, I determine the asker is not a very experienced programmer. He's still learning. I don't think the question was that bad, it just shows a lack of testing, which he might not have learned yet. Also, correctness in corner-cases is on-topic. To slam the door in the face of one that actively seeks help in a good way whilst showing at least some effort from himself... that's something I wouldn't do. \$\endgroup\$ – Pimgd Sep 16 '14 at 12:17
  • \$\begingroup\$ I didn't mean to ask it in a way that the question had to be closed, I was just wondering what was the best to do. Thanks for the info! \$\endgroup\$ – IEatBagels Sep 16 '14 at 12:36
  • \$\begingroup\$ Made changes and tested, which should have been done before asking such queries. Main intention of this query is to confirm the compliance of six points that is mentioned in the query. Emphasis is on designing Abstraction and providing Encapsulation as mentioned in the query. \$\endgroup\$ – overexchange Sep 17 '14 at 5:51
8
\$\begingroup\$

Review:

public void insertAt(Object item, int position){
    if (position == 1){
        insertFront(item);
        size++;
    }else if(position < 1){
        System.exit(1);
    }else{
        SListNode currentNode = this.head.nth(position);
        if(currentNode != null){
            currentNode.insertAfter(item);
            size++;
        }else{
            System.exit(1); //position value exceeds 
        }
    }
}

Don't use System.exit(1). It forcibly shuts down the application. Nobody likes that, because there's nothing they can do at that point. Plus, from the user perspective, they hit "new item" and POOF the whole application is gone. No error message, no possibility for display of instructions (program contains bug! Please look on your desktop and email this file to us!)...


A good list (for shopping list) allows me to check if something is already on there (contains) and allows me to cross items off my list when I have them (removeAt, remove(object)).


Your comments need to be a bit better.

System.exit(1); //position value exceeds 

Exceeds what? Comments should be clear and precise. Comments should detail the why as well. Any interesting differences in the working of your code compared to similar code (how does your SList differ from java.util.List?) could also be valid comments. I'd add a comment to your class stating that it's 1-indexed; that is, you start counting at 1.

\$\endgroup\$
  • \$\begingroup\$ I made this a separate answer because the bugs should stand out more on their own, rather than being part of some larger review. \$\endgroup\$ – Pimgd Sep 16 '14 at 12:23
  • \$\begingroup\$ Good point for System.exit(). It should almost never be use in a normal class. It's such a drastic way of closing the application, no time to close connections or resources. It's rarely a good decision. \$\endgroup\$ – Marc-Andre Sep 16 '14 at 15:36
  • \$\begingroup\$ Am a new learner at link online. \$\endgroup\$ – overexchange Sep 17 '14 at 5:55
2
\$\begingroup\$

The code is slightly convoluted, and there is some fat to be trimmed.

For example, you have list-traversing code in SListNode.nth() (working recursively) and SList.insertEnd() (using an iterative loop). You also have node-insertion logic in both SListNode.insertAfter(), SList.insertFront(), and SList.insertEnd(). Splitting up your code like that makes it harder to follow. I recommend making your SListNode just a "dumb" structure:

class SListNode {
    Object item;
    SListNode next;

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

… so that you can centralize all of the intelligence in the SList class. You only need one SListNode constructor.

SList.insertEnd(Object item) can just call insertAt(item, size + 1);

SList.insertAt() and SList.nth() should perform the bounds checking up front. Here's how I would write .insertAt():

/**
 * Inserts item in the list.  Position 1 puts the new item at the head.
 * Inserting an item at position (size + 1) appends it to the end.
 */
public void insertAt(Object item, int position) {
    if (position < 1 || position > size + 1) {
        // TODO: Error handling
        return;
    } else if (position == 1) {
        insertFront(item);
    } else {
        SListNode prev = this.head;
        for (int i = 2; i < position; i++) {
            prev = prev.next;
        }
        prev.next = new SListNode(item, prev.next);
        size++;
    }   
}

The SList constructor is actually the same as what Java provides by default, so you could omit it.

\$\endgroup\$
  • \$\begingroup\$ you are right, i can consolidate all intelligence in SList, but i think methods added up in SListNode() because i thought of writing in recursive logic(for practice). Am i correct? If i would write iteratively, I would only need a constructor from SListNode. Modified insertEnd() of SList logic into recursive which required adding insertEnd() in SListNode as well. So, that means taking recusive approach actually complicating the code flow, right? \$\endgroup\$ – overexchange Sep 19 '14 at 9:16
  • \$\begingroup\$ i did not get this point: I'm not sure what you mean by "Abstract Data Type". All I see is a linked list. \$\endgroup\$ – overexchange Sep 19 '14 at 9:20
  • \$\begingroup\$ i will take back this statement: " i think methods added up in SListNode() because i thought of writing in recursive logic(for practice). Am i correct? " \$\endgroup\$ – overexchange Sep 19 '14 at 10:15
  • \$\begingroup\$ Recursion is usually avoided in Java due to concerns about performance and stack size limits. However, in programming exercises (which this clearly is — you would never write your own linked list in production code), it's perfectly fine. It would still be better to keep the SListNode class dumb, though. You could reformulate SList.insertAt() using recursion instead. \$\endgroup\$ – 200_success Sep 19 '14 at 14:52
  • \$\begingroup\$ You failed to meet criteria 2 and 3, as Pimgd noted, due to careless bugs. Otherwise, you're on the right track. \$\endgroup\$ – 200_success Sep 19 '14 at 15:00

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.