Thread: From Doubly to Single linked list

Hi,

I've got a example code with doubly linked list with headAndTail and a Sentinel and have to implement a single linkedlist with a Sentinel. My assignment says that i have to pay close attention to methods: insert, delete, attachBefore, delete, getElement, and answer to question that if I need to build in getting backwards into iterator?

My teacher said that having this code it's easily to do that, but the problem is that i have no idea how to start, all my ideas so far are stupid and don't get my any closer to solution. So if someone of your could take a look at this code and give me some hints i would be appreciate

the code:

 
public class LinkedList2 extends AbstractList {
    private final Element _headAndTail = new Element(null); 
    private int _size;    
 
    public LinkedList2() 
      { clear();}
 
 
    public void insert(int index, Object value) throws IndexOutOfBoundsException {
        if(index<0 || index>_size) throw new IndexOutOfBoundsException();
        Element element = new Element(value);
        element.attachBefore(getElement(index));
        ++_size;
    }
 
    public Object delete(int index) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        Element element = getElement(index);
        element.detach();
        --_size;
        return element.getValue();
    }
    public boolean delete(Object value) {
        Element e = _headAndTail.getNext();
        while (e != _headAndTail && ! value.equals(e.getValue()))
               e = e.getNext();
        if (e != _headAndTail) {
                e.detach(); --_size; return true;
            }
        else return false;
    }
 
    public void add(Object value) 
    { insert(size(), value); }
 
    public boolean contains(Object value)
    { return indexOf(value) != -1; }
 
    public boolean isEmpty() 
    { return _size == 0; }
 
    public void clear() {
        _headAndTail.setPrevious(_headAndTail);
        _headAndTail.setNext(_headAndTail);
        _size = 0;
    }
 
    public Object set(int index, Object value) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        Element element = getElement(index);
        Object oldValue = element.getValue();
        element.setValue(value);
        return oldValue;
    }
 
    public Object get(int index) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        return getElement(index).getValue();
    }
 
    public Iterator iterator()
    {  return new ValueIterator(); }
 
    public int indexOf(Object value) {
        int index = 0;
        Element e = _headAndTail.getNext();
        while( e != _headAndTail && ! value.equals(e.getValue()))
            { e = e.getNext(); ++index; }
        return e!=_headAndTail ? index : -1;
    }
 
    public int size() {
        return _size;
    }
 
 
    private Element getElement(int index) 
     {return index< _size/2 ? getElementForwards(index) : getElementBackwards(index); }
 
 
    private Element getElementForwards(int index) {
        Element element = _headAndTail.getNext(); 
 
        for (int i = index; i > 0; --i)
            element = element.getNext();
        return element;
    }
 
    private Element getElementBackwards(int index) {
        Element element = _headAndTail;
        for (int i = _size - index; i > 0; --i) 
            element = element.getPrevious();
        return element;
    }
    private void checkOutOfBounds(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size())
            throw new IndexOutOfBoundsException();
    }
 
    private static final class Element {
        private Object _value;
        private Element _previous;
        private Element _next;
 
        public Element(Object value)
        { setValue(value); }
 
        public void setValue(Object value)
        { _value = value;  }
 
        public Object getValue()
        { return _value;   }
 
        public Element getPrevious() 
        { return _previous;}
 
        public void setPrevious(Element previous)
        { _previous = previous; }
 
        public Element getNext()
        { return _next; }
 
        public void setNext(Element next)
        { _next = next; }
 
 
        public void attachBefore(Element next) {
            Element previous = next.getPrevious();
            setNext(next);
            setPrevious(previous);
            next.setPrevious(this);
            previous.setNext(this);
        }
        public void detach() {
            _previous.setNext(_next);
            _next.setPrevious(_previous);
        }
    }    
 
 
    private final class ValueIterator implements Iterator {
        private Element _current = _headAndTail;
        public void first() 
        { _current = _headAndTail.getNext(); }
 
        public void last() 
        { _current = _headAndTail.getPrevious(); }
 
        public boolean isDone() 
        { return _current == _headAndTail; }
 
        public void next() 
        { _current = _current.getNext(); }
 
        public void previous() 
        { _current = _current.getPrevious(); }
 
        public Object current() throws IndexOutOfBoundsException {
            if (isDone())
                throw new IndexOutOfBoundsException();
            return _current.getValue();
        }
    }
}

Thanks in advance

OK, so listen what I've got so far. My idea was to just cut out the parts of code where it could call the previous element and where necessary modify the code so here are the changes

I've modified the _headAndTail variable to static

private final static Element _headAndTail = new Element(null);

Modified methods

    public void clear() {
        _headAndTail.setNext(_headAndTail);
        _size = 0;
    }
 
    private Element getElement(int index) 
     {
    	return getElementForwards(index);
     }
 
public void attachBefore(Element next) {
 
        	 Element e = _headAndTail.getNext();
        	while ((e != _headAndTail && ! _value.equals(e.getValue())) || (e.getNext() != next)) 
        		e = e.getNext();
 
            if (e != _headAndTail) {
            	_next = e.getNext();
                e.setNext(this);    
            } 
        }
 
        public void detach() {
        	Element e = _headAndTail.getNext();
        	while ((e != _headAndTail && ! _value.equals(e.getValue())) || (e.getNext() != _value)) 
        		e = e.getNext();
 
            if (e != _headAndTail) {
            	_next = e.getNext().getNext();
            } 
        }

I've removed method getElementsBackwards because it's never used; what's more i can remove the setPrevious method because it's never used and can't remove getPrevious because it's used by sentinel for returning the last element; and from ValueIterator i can't remove any method because all of them ale listed in implemented interface Iterator

My full code:

package lists;
import iterators.*;
 
public class LinkedList2 extends AbstractList {
    private final static Element _headAndTail = new Element(null);
    private int _size;    
 
    public LinkedList2() 
      { clear();}
 
 
    public void insert(int index, Object value) throws IndexOutOfBoundsException {
        if(index<0 || index>_size) throw new IndexOutOfBoundsException();
        Element element = new Element(value);
        element.attachBefore(getElement(index));
        ++_size;
    }
 
    public Object delete(int index) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        Element element = getElement(index);
        element.detach();
        --_size;
        return element.getValue();
    }
    public boolean delete(Object value) {
        Element e = _headAndTail.getNext();
        while (e != _headAndTail && ! value.equals(e.getValue()))
               e = e.getNext();
        if (e != _headAndTail) {
                e.detach(); --_size; return true;
            }
        else return false;
    }
 
    public void add(Object value) 
    { insert(size(), value); }
 
    public boolean contains(Object value)
    { return indexOf(value) != -1; }
 
    public boolean isEmpty() 
    { return _size == 0; }
 
    public void clear() {
        _headAndTail.setNext(_headAndTail);
        _size = 0;
    }
 
    public Object set(int index, Object value) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        Element element = getElement(index);
        Object oldValue = element.getValue();
        element.setValue(value);
        return oldValue;
    }
 
    public Object get(int index) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        return getElement(index).getValue();
    }
 
    public Iterator iterator()
    {  return new ValueIterator(); }
 
    public int indexOf(Object value) {
        int index = 0;
        Element e = _headAndTail.getNext();
        while( e != _headAndTail && ! value.equals(e.getValue()))
            { e = e.getNext(); ++index; }
        return e!=_headAndTail ? index : -1;
    }
 
    public int size() {
        return _size;
    }
 
    private Element getElement(int index) 
     {
    	return getElementForwards(index);
     }
 
    private Element getElementForwards(int index) {
        Element element = _headAndTail.getNext(); 
 
        for (int i = index; i > 0; --i)
            element = element.getNext();
        return element;
    }
 
 
 
    private void checkOutOfBounds(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size())
            throw new IndexOutOfBoundsException();
    }
 
    private static final class Element {
        private Object _value;
        private Element _previous;
        private Element _next;
 
 
        public Element(Object value)
        { setValue(value); }
 
        public void setValue(Object value)
        { _value = value;  }
 
        public Object getValue()
        { return _value;   }
 
        public Element getPrevious() 
        { return _previous;}
 
        public void setPrevious(Element previous)
        { _previous = previous; }
 
        public Element getNext()
        { return _next; }
 
        public void setNext(Element next)
        { _next = next; }
 
 
        public void attachBefore(Element next) {
 
        	 Element e = _headAndTail.getNext();
        	while ((e != _headAndTail && ! _value.equals(e.getValue())) || (e.getNext() != next)) 
        		e = e.getNext();
 
            if (e != _headAndTail) {
            	_next = e.getNext();
                e.setNext(this);    
            } 
        }
 
        public void detach() {
        	Element e = _headAndTail.getNext();
        	while ((e != _headAndTail && ! _value.equals(e.getValue())) || (e.getNext() != _value)) 
        		e = e.getNext();
 
            if (e != _headAndTail) {
            	_next = e.getNext().getNext();
            } 
        }
    }    
 
    private final class ValueIterator implements Iterator {
        private Element _current = _headAndTail;
        public void first() 
        { _current = _headAndTail.getNext(); }
 
        public void last() 
        { _current = _headAndTail.getPrevious(); }
 
        public boolean isDone() 
        { return _current == _headAndTail; }
 
        public void next() 
        { _current = _current.getNext(); }
 
        public void previous() 
        { _current = _current.getPrevious(); }
 
        public Object current() throws IndexOutOfBoundsException {
            if (isDone())
                throw new IndexOutOfBoundsException();
            return _current.getValue();
        }
    }
}

variable _previous is used only in sentinel

So now can i call this a single linkedlist? Is it good method or should I do something else?