tlinkedlist.java

这是一个matlab的java实现。里面有许多内容。请大家慢慢捉摸。

        } else {
            TLinkable prior = null, post = null;

            // looking at the size of the list, we decide whether
            // it's faster to reach `index' by traversing the
            // list from the front or the back.
            if (index > (_size >> 1)) { // insert in 2nd half
                // work from the tail
                int pos = _size -1;
                for (prior = _tail; pos > index; pos--) {
                    prior = prior.getPrevious();
                }
            } else {                // insert in 1st half
                // work from the head
                int pos = 0;
                for (prior = _head; pos < index; pos++) {
                    prior = prior.getNext();
                }
            }
            post = prior.getNext();
            // insert newlink
            newLink.setNext(post);
            newLink.setPrevious(prior);
            // adjust adjacent pointers
            post.setPrevious(newLink);
            prior.setNext(newLink);
        }
        _size++;
    }

    /**
     * Removes the specified element from the list.  Note that
     * it is the caller's responsibility to ensure that the
     * element does, in fact, belong to this list and not another
     * instance of TLinkedList.  
     *
     * @param o a TLinkable element already inserted in this list.
     * @return true if the element was a TLinkable and removed
     */
    public boolean remove(Object o) {
        if (o instanceof TLinkable) {
            TLinkable p, n;
            TLinkable link = (TLinkable)o;

            p = link.getPrevious();
            n = link.getNext();

            if (n == null && p == null) { // emptying the list
                _head = _tail = null;
            } else if (n == null) { // this is the tail
                // make previous the new tail
                link.setPrevious(null);
                p.setNext(null);
                _tail = p;
            } else if (p == null) { // this is the head
                // make next the new head
                link.setNext(null);
                n.setPrevious(null);
                _head = n;
            } else {            // somewhere in the middle
                p.setNext(n);
                n.setPrevious(p);
                link.setNext(null);
                link.setPrevious(null);
            }

            _size--;            // reduce size of list
            return true;
        } else {
            return false;
        }
    }

    /**
     * Inserts newElement into the list immediately before current.
     * All elements to the right of and including current are shifted
     * over.
     *
     * @param current a <code>TLinkable</code> value currently in the list.
     * @param newElement a <code>TLinkable</code> value to be added to
     * the list.
     */
    public void addBefore(TLinkable current, TLinkable newElement) {
        if (current == _head) {
            addFirst(newElement);
        } else if (current == null) {
            addLast(newElement);
        } else {
            TLinkable p = current.getPrevious();
            newElement.setNext(current);
            p.setNext(newElement);
            newElement.setPrevious(p);
            current.setPrevious(newElement);
            _size++;
        }
    }

    /**
     * A ListIterator that supports additions and deletions.
     *
     */
    protected final class IteratorImpl implements ListIterator {
        private int _nextIndex = 0;
        private TLinkable _next;
        private TLinkable _lastReturned;

        /**
         * Creates a new <code>Iterator</code> instance positioned at
         * <tt>index</tt>.
         *
         * @param position an <code>int</code> value
         */
        IteratorImpl(int position) {
            if (position < 0 || position > _size) {
                throw new IndexOutOfBoundsException();
            }
            
            _nextIndex = position;
            if (position == 0) {
                _next = _head;
            } else if (position == _size) {
                _next = null;
            } else if (position < (_size >> 1)) {
                int pos = 0;
                for (_next = _head; pos < position; pos++) {
                    _next = _next.getNext();
                }
            } else {
                int pos = _size - 1;
                for (_next = _tail; pos > position; pos--) {
                    _next = _next.getPrevious();
                }
            }
        }
        
        /**
         * Insert <tt>linkable</tt> at the current position of the iterator.
         * Calling next() after add() will return the added object.
         *
         * @param linkable an object of type TLinkable
         */
        public final void add(Object linkable) {
            _lastReturned = null;
            _nextIndex++;

            if (_size == 0) {
                TLinkedList.this.add(linkable);
            } else {
                TLinkedList.this.addBefore(_next, (TLinkable)linkable);
            }
        }

        /**
         * True if a call to next() will return an object.
         *
         * @return a <code>boolean</code> value
         */
        public final boolean hasNext() {
            return _nextIndex != _size;
        }

        /**
         * True if a call to previous() will return a value.
         *
         * @return a <code>boolean</code> value
         */
        public final boolean hasPrevious() {
            return _nextIndex != 0;
        }

        /**
         * Returns the value at the Iterator's index and advances the
         * iterator.
         *
         * @return an <code>Object</code> value
         * @exception NoSuchElementException if there is no next element
         */
        public final Object next() {
            if (_nextIndex == _size) {
                throw new NoSuchElementException();
            }

            _lastReturned = _next;
            _next = _next.getNext();
            _nextIndex++;
            return _lastReturned;
        }

        /**
         * returns the index of the next node in the list (the
         * one that would be returned by a call to next()).
         *
         * @return an <code>int</code> value
         */
        public final int nextIndex() {
            return _nextIndex;
        }

        /**
         * Returns the value before the Iterator's index and moves the
         * iterator back one index.
         *
         * @return an <code>Object</code> value
         * @exception NoSuchElementException if there is no previous element.
         */
        public final Object previous() {
            if (_nextIndex == 0) {
                throw new NoSuchElementException();
            }

            if (_nextIndex == _size) {
                _lastReturned = _next = _tail;
            } else {
                _lastReturned = _next = _next.getPrevious();
            }
            
            _nextIndex--;
            return _lastReturned;
        }

        /**
         * Returns the previous element's index.
         *
         * @return an <code>int</code> value
         */
        public final int previousIndex() {
            return _nextIndex - 1;
        }

        /**
         * Removes the current element in the list and shrinks its
         * size accordingly.
         *
         * @exception IllegalStateException neither next nor previous
         * have been invoked, or remove or add have been invoked after
         * the last invocation of next or previous.
         */
        public final void remove() {
            if (_lastReturned == null) {
                throw new IllegalStateException("must invoke next or previous before invoking remove");
            }

            if (_lastReturned != _next) {
                _nextIndex--;
            }
            _next = _lastReturned.getNext();
            TLinkedList.this.remove(_lastReturned);
            _lastReturned = null;
        }

        /**
         * Replaces the current element in the list with
         * <tt>linkable</tt>
         *
         * @param linkable an object of type TLinkable
         */
        public final void set(Object linkable) {
            if (_lastReturned == null) {
                throw new IllegalStateException();
            }
            TLinkable l = (TLinkable)linkable;

            // need to check both, since this could be the only
            // element in the list.
            if (_lastReturned == _head) {
                _head = l;
            }

            if (_lastReturned == _tail) {
                _tail = l;
            }

            swap(_lastReturned, l);
            _lastReturned = l;
        }

        /**
         * Replace from with to in the list.
         *
         * @param from a <code>TLinkable</code> value
         * @param to a <code>TLinkable</code> value
         */
        private void swap(TLinkable from, TLinkable to) {
            TLinkable p = from.getPrevious();
            TLinkable n = from.getNext();

            if (null != p) {
                to.setPrevious(p);
                p.setNext(to);
            }
            if (null != n) {
                to.setNext(n);
                n.setPrevious(to);
            }
            from.setNext(null);
            from.setPrevious(null);
        }
    }
} // TLinkedList