java LinkedList学习心得

Question

java算法

Answer 1

public class MyLinkedList<T> extends AbstractSequentialList<T> implements
        Collection<T> {    private LinkList list = new LinkList();    private int size;    public int size() {
        return size;
    }    public boolean isEmpty() {
        return list.head.next == list.head;
    }    public boolean add(T e) {
        list.addAfter(e, list.getFirst().previous);
        return true;
    }    public String toString() {
        return list.toString();
    }
    /**
     * 
     * @author sheyong
     *
     */
    class LinkList {
        LinkNode<T> head = new LinkNode<T>(null, null, null);// 头节点        public LinkList() {
            head.next = head;
            head.previous = head;
            // 首尾相连
        }
        
        /**
         *  返回头节点
         * @Author : sheyong
         */
        public LinkNode<T> getFirst() {
            return head;
        }
        
        /**
         *  返回最后一个节点
         * @Author : sheyong
         */
        public LinkNode<T> getLast() {
            LinkNode<T> node = head.previous;// 返回最后一个节点
            if (node == head) {
                return null;
            }
            return node;
        }
        
        /**
         *  将节点添加到头节点后
         * @Author : sheyong
         */
        public LinkNode<T> addFirst(T element) {
            return addAfter(element, head);
        }        public LinkNode<T> addAfter(T e, LinkNode<T> node) {
            LinkNode<T> newNode = new LinkNode<T>(node.next, node, e);
            newNode.previous.next = newNode;
            newNode.next.previous = newNode;
            size++;
            return newNode;        }
        
        /**
         *  将节点添加到头节点后
         * @Author : sheyong
         */
        public LinkNode<T> addLast(T e) {
            return addAfter(e, head.previous);
        }
        
        /*
         * @see java.lang.Object#toString()
         */
        public String toString() {
            String tempStr = "[" + head.next;
            LinkNode<T> temp = head.next;
            while ((temp = temp.next) != head) {
                tempStr += " " + temp;
            }
            return tempStr + "]";
        }    }
    /**
     * 
     * @author sheyong
     *
     * @param <T>
     */
    class LinkNode<T> {
        public LinkNode(LinkNode<T> next, LinkNode<T> previous, T obj) {
            this.next = next;
            this.previous = previous;
            this.obj = obj;
        }        private LinkNode<T> next;//下一个节点        private LinkNode<T> previous;//上一个节点
        private T obj;
        /**
         * 删除节点
         */
        public void remove() {
            next.previous = previous;//前与后相连
            previous.next = next;//后与前相连
            
        }
        /**
         * 修改节点
         */
        public void set(T t) {
            LinkNode<T> link = new LinkNode<T>(next, previous, t);//新对象
            next.previous = link;//改变next
            previous.next = link;//改变previous
        }
        
        public String toString() {
            return obj.toString();
        }
    }    /**
     * 
     * @author sheyong
     * 
     * @param <T>
     */
    public ListIterator<T> listIterator(int index) {
        return this.new MyLinkedListIterator(index);
    }    private class MyLinkedListIterator implements ListIterator<T> {
        private LinkNode<T> current = (LinkNode<T>) list.getFirst();// 当前对象
        private int nextIndex;// 下一个索引        public MyLinkedListIterator(int index) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("index:" + index + " ?");
            if (index > size >> 1) {
                for (nextIndex = size; nextIndex > index; nextIndex--) {
                    current = current.previous;
                }
            } else {
                for (nextIndex = 0; nextIndex < index; nextIndex++) {
                    current = current.next;
                }
            }
        }        public boolean hasNext() {
            return nextIndex != size;
        }        public T next() {
            if (nextIndex == size)
                throw new IndexOutOfBoundsException("越界");
            current = current.next;
            nextIndex++;
            return current.obj;
        }        public boolean hasPrevious() {
            return nextIndex != 0;
        }        public T previous() {
            if (nextIndex == 0)
                throw new IndexOutOfBoundsException("越界");
            current = current.next;
            nextIndex--;
            return current.obj;
        }        public int nextIndex() {
            return nextIndex;
        }        public int previousIndex() {
            return nextIndex - 1;
        }        public void remove() {
            current.remove();
            size--;
            nextIndex--;
        }        public void set(T e) {
            current.set(e);
        }        public void add(T e) {
            MyLinkedList.this.list.addLast(e);
            size++;
        }    }
}