List - Data Structure

List - Single Link List and Double Link List

package com.datastructure.general;

/**
 * Created by santosh on 3/4/15.
 */
public interface Collection<E> {
   public void put(E element);
   public E get(E element);
   public boolean contains(E element);
   public int indexOf(E element);
   public boolean delete(E element);
   public int size();
   public Iterator<E> getIterator();
}



public interface List<E> extends Collection<E> {
    public E getFirst();
    public E getLast();
}




public abstract class AbstractList<E> implements List<E> {
    protected int size=0;
    @Override
    public int indexOf(E element) {
        int index = -1;
        boolean found = false;
        Iterator<E> iterator = getIterator();
        while (iterator.hasNext()){
            ++index;
            E existingElement = iterator.getNext();
            if(existingElement.equals(element)){
                found = true;
                break;
            }
        }
        if(found) return index;
        return -1;
    }

    @Override
    public boolean contains(E element) {
        return get(element)!=null;
    }

    @Override
    public int size() {
        return this.size;
    }


    @Override
    public E get(E element) {
        Iterator<E> iterator = getIterator();
        while (iterator.hasNext()){
            E elementFound = iterator.getNext();
            if(elementFound.equals(element)){
                return elementFound;
            }
        }
        return null;
    }
}

==================Single Linked List===============



 package com.datastructure.general;

/**
 * Created by santosh on 7/4/15.
 */
public class SingleLinkedList<E> extends AbstractList<E> {
    private Link currentLink;

    @Override
    public E getFirst() {
        return null;
    }

    @Override
    public E getLast() {
        return null;
    }

    private static class Link{
        private Object data;
        private Link previousLink;

        public Object getData() {
            return data;
        }

        public void setData(Object data) {
            this.data = data;
        }

        public Link getPreviousLink() {
            return previousLink;
        }

        public void setPreviousLink(Link previousLink) {
            this.previousLink = previousLink;
        }
    }

    @Override
    public void put(E element) {

        if(this.currentLink==null){
            this.currentLink = new Link();
            this.currentLink.setData(element);
        } else {
            Link newLink = new Link();
            newLink.setPreviousLink(this.currentLink);
            newLink.setData(element);
            this.currentLink = newLink;
        }
        ++size;
    }

    private boolean deleteCurrent(E element){
        boolean isDeleted = false;
        if(this.currentLink.getData().equals(element)){
            this.currentLink = this.currentLink.getPreviousLink();
            isDeleted = true;
        }
        return isDeleted;
    }

    private boolean deleteFirst(E element){
        boolean isDeleted = false;
        Link lastButOne = null;
        Link indexLink = this.currentLink;
        while (indexLink.getPreviousLink()!=null){
            lastButOne = indexLink;
            indexLink = indexLink.getPreviousLink();
        }

        if(indexLink.getData().equals(element)){
           lastButOne.setPreviousLink(null);
           isDeleted = true;
        }
        return isDeleted;
    }
    @Override
    public boolean delete(E element) {
        if(deleteCurrent(element)){--size; return true;}
        if(deleteFirst(element)) {--size; return  true;}
        boolean isDeleted = false;
        Link foundLink = null;
        Link previousLink = null;
        Link priorIteration = null;
        Link indexLink = this.currentLink;
        while (indexLink.getPreviousLink()!=null){
             if(element.equals(indexLink.getData())){
                foundLink = indexLink;
                previousLink = foundLink.getPreviousLink();
                break;
            }
            priorIteration = indexLink;
            indexLink = indexLink.getPreviousLink();
        }

        if(previousLink!=null && foundLink!=null && priorIteration!=null){
         priorIteration.setPreviousLink(previousLink);
         --size;
         isDeleted = true;
        }
        return isDeleted;
    }


    @Override
    public Iterator<E> getIterator() {
        return new LinkedListIterator(this.currentLink);
    }

    private static class LinkedListIterator<E> implements Iterator<E>{
        private Link currentLink;

        private LinkedListIterator(Link currentLink) {
            this.currentLink = currentLink;
        }

        @Override
        public boolean hasNext() {
            return this.currentLink!=null;
        }

        @Override
        public E getNext() {
            Link currentLink = this.currentLink;
            this.currentLink = this.currentLink.getPreviousLink();
            return (E)currentLink.getData();
        }
    }
}

 ================= Double Linked List====================
package com.datastructure.general;

/**
 * Created by santosh on 8/4/15.
 */
public class DoubleLinkedList<E> extends AbstractList<E>  {
    private Node currentNode;
    private Node firstNode;

    public Node getCurrentNode() {
        return currentNode;
    }

    public void setCurrentNode(Node currentNode) {
        this.currentNode = currentNode;
    }

    @Override
    public E getFirst() {
        E first = null;
        if(firstNode!=null){
            first =(E)firstNode.getData();
        }
        return first;
    }

    @Override
    public E getLast() {
        E last = null;
        if(currentNode!=null){
            last =(E)currentNode.getData();
        }
        return last;
    }

    private static class Node{
       private Object data;
       private Node nextNode;
       private Node previousNode;

        public Object getData() {
            return data;
        }

        public void setData(Object data) {
            this.data = data;
        }

        public Node getNextNode() {
            return nextNode;
        }

        public void setNextNode(Node nextNode) {
            this.nextNode = nextNode;
        }

        public Node getPreviousNode() {
            return previousNode;
        }

        public void setPreviousNode(Node previousNode) {
            this.previousNode = previousNode;
        }
    }

    @Override
    public void put(E element) {
        if(currentNode==null){
            currentNode = new Node();
            currentNode.setData(element);
            currentNode.setNextNode(null);
            currentNode.setPreviousNode(null);
            firstNode = currentNode;
        } else {
            Node newNode = new Node();
            newNode.setData(element);
            newNode.setPreviousNode(currentNode);
            currentNode.setNextNode(newNode);
            currentNode = newNode;
        }
        ++size;
    }



    @Override
    public boolean contains(E element) {
        return false;
    }

    @Override
    public boolean delete(E element) {
        return false;
    }


    @Override
    public int size() {
        return 0;
    }

    @Override
    public Iterator<E> getIterator() {
        return new DoubleLinkedListIterator<E>(this.firstNode);
    }

    private class DoubleLinkedListIterator<E> implements Iterator<E>{
        private Node toStartNode;
        private boolean isLast;
        private DoubleLinkedListIterator(Node toStartNode) {
            this.toStartNode = toStartNode;
        }

        @Override
        public boolean hasNext() {
            boolean hasNext = false;
            if(toStartNode!=null){
                Node nextNode = toStartNode.getNextNode();
                if(nextNode!=null){
                    hasNext = true;
                } else {
                    hasNext = isLast;
                    isLast = false;
                }
            }

            return hasNext;
        }

        @Override
        public E getNext() {
            Node node = toStartNode;
            toStartNode = toStartNode.getNextNode();
            if(toStartNode != null && toStartNode.getNextNode()==null){
                isLast = true;
            }
            return (E) node.getData();
        }
    }
}