5
\$\begingroup\$

I have provided a simple implementation of a linked list using my own super classes and interface. The implementation is for adding, deleting obtaining the size of thew list. I have not yet provided the iterator in the current code as it's not in the scope for now.

SimpleList.java

package com.learn.linkedlist;

import com.learn.linkedlist.exceptions.IllegalPositionArgException;

public interface SimpleList<E> {

    /**add the node at the end of the list
     * 
     * @param node
     * @return true if successfully added and list has changed due to addition
     */
    public abstract boolean add(E node);

    /**add the first occurrence of the node 
     * 
     * @param node
     * @return true if deletion is successful, in case the node is not present then return false
     */
    public abstract boolean delete(E node);

    /**add a node at the specified position
     * 
     * @param position
     * @param node
     * @return
     * @throws IllegalPositionArgException in case the position < 0 or position >  size of      the list
     */
    public abstract boolean add(int position,E node)throws IllegalPositionArgException;

    /**delete the node at the specified position
     * 
     * @param position
     * @return
     * @throws IllegalPositionArgException in case the position < 0 or position >=  size of the list
     */
    public abstract boolean deleteAt(int position) throws IllegalPositionArgException;

    /**get the node the specified position
     * 
     * @param position
     * @return node at the position
     * @throws IllegalPositionArgException in case the position < 0 or position >=  size of the list
     */
    public abstract E get(int position) throws IllegalPositionArgException;

    /**
     * 
     * @return the number of nodes in the list
     */
    public abstract int size();

}

SimpleAbstractLinkedList.java

package com.learn.linkedlist;

public abstract class SimpleAbstractLinkedList<E> implements SimpleList<E>{
    protected SimpleNode<E> rootElement;
    protected int size;
    protected static class SimpleNode<T> {
        protected T nodeData;
        protected SimpleNode<T> nextNode;
        protected SimpleNode<T> preNode;

        public SimpleNode(T nodeData, SimpleNode<T> preNode, SimpleNode<T> nextNode) {
            this.nodeData = nodeData;
            this.preNode = preNode;
            this.nextNode = nextNode;
        }

        @Override
        public int hashCode() {
            return ((nodeData == null) ? 0 : nodeData.hashCode());
        }

        @Override
        public boolean equals(Object obj) {
            boolean isEqual = false;
            if(obj instanceof SimpleNode){
                if(((SimpleNode<?>) obj).nodeData == nodeData){
                    isEqual = true;
                }else{
                    if(nodeData != null ){
                        if(nodeData.equals(((SimpleNode<?>) obj).nodeData)){
                            isEqual = true;
                        }
                    }
                }
            }
            return isEqual;
        }
    }
}

SimpleLinkedListImp1.java

package com.learn.linkedlist;

import com.learn.linkedlist.exceptions.IllegalPositionArgException;

public class SimpleLinkedListImp1<E> extends SimpleAbstractLinkedList<E>{
    @Override
    public boolean add(E data) {
        SimpleNode<E> newNode = new SimpleNode<E>(data, null, null);
        SimpleNode<E> iteratingNode = rootElement;
        if(iteratingNode != null){
            while(iteratingNode.nextNode!=null){
                iteratingNode = iteratingNode.nextNode;
            }
        }
        addNode(newNode,iteratingNode);
        return true;
    }

    @Override
    public boolean delete(E data) {
        SimpleNode<E> newNode = new SimpleNode<E>(data, null, null);
        boolean isDeleted = false;
        if(rootElement.equals(newNode)){
            deleteNode(rootElement);
            rootElement=rootElement.nextNode;
            isDeleted = true;
        }
        else{
            SimpleNode<E> iteratingNode = rootElement.nextNode;
            while(iteratingNode!=null){
                if(iteratingNode.equals(newNode)){
                    deleteNode(iteratingNode);
                    isDeleted = true;
                    break;
                }
                iteratingNode = iteratingNode.nextNode;
            }
        }
        return isDeleted;
    }

    @Override
    public boolean add(int position, E data) throws IllegalPositionArgException {
        SimpleNode<E> newNode = new SimpleNode<E>(data, null, null);
        SimpleNode<E> iteratingNode = rootElement;
        int count = 0;
        if(position<0 || position>size()){
            throw new IllegalPositionArgException();
        }
        if(position==size()){
            add(data);
        }else{
            if(position == 0){
                addNode(newNode,null);
            }else{
                while(iteratingNode.nextNode!=null){
                    if(position == count+1){
                        break;
                    }
                    iteratingNode= iteratingNode.nextNode;
                    count++;
                }
                addNode(newNode,iteratingNode);
            }
        }
        return true;
    }

    @Override
    public boolean deleteAt(int position) throws IllegalPositionArgException {
        if(position < 0 || position >= size()){
            throw new IllegalPositionArgException();
        }
        SimpleNode<E> iteratingNode = rootElement;
        int count = 0;
        while(iteratingNode!= null){
            if(count==position){
                deleteNode(iteratingNode);
                break;
            }
            iteratingNode= iteratingNode.nextNode;
            count ++;
        }
        return true;
    }


    @Override
    public E get(int position) throws  IllegalPositionArgException  {
        SimpleNode<E> node = rootElement;
        int count = 0;
        if(position<0 || position>=size()){  //size runs in a loop , @TODO make list size immutable and store size in an class level variable 
            throw new IllegalPositionArgException();// this is as per java contract
        }
        while(node != null){
            if(position == count){
                break;
            }
            node = node.nextNode;
            count ++;
        }
        return node.nodeData;
    }

    @Override
    public int size()  {
        return size;
    }
    private void deleteNode(SimpleNode<E> node){
        if(node.nextNode !=null){
            node.nextNode.preNode = node.preNode;
        }
        if(node.preNode != null){
            node.preNode.nextNode = node.nextNode;
        }
        node.preNode = null;
        node.nextNode = null;
        size--;
    }
    private void addNode(SimpleNode<E> newNode,SimpleNode<E> parentNode){
        if(parentNode == null){
            if(rootElement == null){
                rootElement = newNode;
            }else{
                rootElement.preNode = newNode;
                newNode.nextNode = rootElement;
                rootElement = newNode;
            }
        }else{
            SimpleNode<E> parentNext = parentNode.nextNode;
            parentNode.nextNode= newNode;
            newNode.preNode = parentNode;
            newNode.nextNode = parentNext;
            if(parentNext != null){
                parentNext.preNode = newNode;
            }
        }
        size++;
    }
}

IllegalPositionArgException.java

package com.learn.linkedlist.exceptions;

public class IllegalPositionArgException extends Exception{

}
\$\endgroup\$
  • \$\begingroup\$ @KidDiamond Just treat it as a request for a general review. \$\endgroup\$ – 200_success Aug 31 '14 at 8:15
  • \$\begingroup\$ Is it Imp1 (one) or Impl (L) ? It should be Impl (L). \$\endgroup\$ – bhathiya-perera Aug 31 '14 at 12:39
  • \$\begingroup\$ yes it should be impl but its 1 for the one of the implementations done. may be I need to give a better name to the implementations \$\endgroup\$ – Krishna Kumar Aug 31 '14 at 15:40
  • \$\begingroup\$ My biggest doubt! How are able to affect the field with the help of iteratingNode in add method? \$\endgroup\$ – MystryMafia Jun 19 '17 at 15:41
5
\$\begingroup\$

SimpleList<E>

First, let's look at the JavaDoc. It's good that you are including this information. However, the docs are not always in sync with the actual method signature, or that method's supposed meaning. The delete(E node) method is documented to “add the first occurrence of the node”. Say what? Similarly, there are boolean return values, but the @return part of the JavaDoc does not always explain what this return value means.

Only the methods in that interface, but not the interface itself have JavaDocs. Consider explaining what that interface is supposed to signify. That would also be a good place to document whether implementations of SimpleList<E> are supposed to handle null values.

Now, let's have a look at all the methods in that interface:

public abstract boolean add(E node);
public abstract boolean delete(E node);
public abstract boolean add(int position,E node)throws IllegalPositionArgException;
public abstract boolean deleteAt(int position) throws IllegalPositionArgException;
public abstract E get(int position) throws IllegalPositionArgException;
public abstract int size();

I don't know why add returns a boolean value. There is no way that adding an element to a list will not result in the list being changed, so this should always return true. As such, the return value contains no information whatsoever, and should be removed. The java.util.Collection<E> interface does contain a boolean add(E) operation because adding an element to a Set might not change the Set if that Set already contains an equal element. But unless you want to update your SimpleList<E> interface to actually implement java.util.Collection<E>, there is no need for such cargo-culting.

It is slightly confusing that you are using an add overload to insert an element at a given position, but that you did not use an overload for a delete at a certain position. I suggest you change deleteAt(int position) to delete(int position), and possibly rename delete to remove while we're at it. However you rename deleteAt, you should change it to return the removed element – a boolean return value is unnecessary, because you will always perform a deletion as long as the index is inside that list's bounds. However, returning the removed element is sometimes useful, and does not impose additional cost – otherwise, a client wishing to access the deleted element would first have to get it, which will traverse the list twice.

Considering that you are implementing a (doubly) linked List abstract data type, I am missing a few operations in this interface:

  • Accessing the first and last element. Adding elements at the beginning and the end. Removing the first and last element. Suggested methods:

    public E getFirst()
    public E getLast()
    public E removeFirst()
    public E removeLast()
    public void addFirst(E value)
    public void addLast(E value)
    

    Note that the getX and removeX methods should throw an error if size() == 0.

  • Replacing the element at a certain position. Suggested method:

    public E set(int pos, E newValue)
    
  • Using the list as an java.lang.Iterable<E>.

  • Joining lists, and adding mutiple values. This could be done with a method like

    public void addAll(Iterable<E> values)
    public void addAll(int pos, Iterable<E> values)
    
  • A simple boolean isEmpty() accessor can also be helpful in many circumstances.

  • A boolean contains(E value) and int index(E value) method to search the list. Currently, this would have to be performed manually, although delete(E value) can be used as a destructive contains.

An interface should try to strike a good balance between usefulness and minimalism. While all the methods I just suggested can be implemented in terms of the methods your interface already contained, doing so would be unnecessarily inefficient (e.g. E set(int pos, E newValue) could be implemented as E oldValue = get(pos); deleteAt(pos); add(pos, newValue); return oldValue, which would traverse the list three times, whereas a built-in version can do with only one traversal).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ thanks for the review, I certainly missed few things which I will implement and edit as per your valuable review. Regarding the overridden methods for delete and add, I guess I should rename add method inserting the data at a position to addAt rather than renaming deleteAt as if user wishes to create Integer type list then delete taking int as param will b confusing so 'at' seams better. \$\endgroup\$ – Krishna Kumar Aug 31 '14 at 10:19
  • \$\begingroup\$ One thing about your critique on delete... given the case you have a SimpleList<Integer> which overload will get called with: list.delete(1)?? \$\endgroup\$ – Vogel612 Aug 31 '14 at 22:24
  • 2
    \$\begingroup\$ @Vogel612 The implicit int → Integer conversion in Java is merely a convenience; it does not get in the way of overloading. When choosing between delete(int) and delete(Integer), calling with an int will resolve to delete(int). See ideone.com/baiffS for an example. \$\endgroup\$ – amon Aug 31 '14 at 22:29

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.