Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: From Doubly to Single linked list

  1. #1
    Junior Member
    Join Date
    May 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question 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


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: From Doubly to Single linked list

    all my ideas so far are stupid and don't get my any closer to solution
    I doubt both of these conclusions. It helps to show what you've tried and where you are stuck - break the problem down and work on each individual portion necessary (build from the ground up if necessary)

  3. #3
    Junior Member
    Join Date
    May 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: From Doubly to Single linked list

    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?

Similar Threads

  1. Help with a doubly linked circular list
    By TeamRival in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 3rd, 2011, 10:59 PM
  2. Generic Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 23
    Last Post: October 23rd, 2010, 03:13 PM
  3. Sorted Doubly linked List
    By student in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 15th, 2010, 09:52 PM
  4. [SOLVED] Update on Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 11th, 2010, 07:19 PM
  5. ClassCastException in Double Linked List toString
    By Rastabot in forum Collections and Generics
    Replies: 2
    Last Post: April 24th, 2009, 11:48 AM