3.5 MyLinkedList 实现

3.5 MyLinkedList 类的实现

MyLinkedList 将用双链表实现，并且还需要保留该表两端的引用。这将需要三个类

MyLinkedList 类，包含到两端的链、表的大小以及一些方法。
Node 类一个私有的嵌套类。一个节点包含数据以及到前一个节点的链和到下一个节点的链。
LinkedListIterator 类，是一个私有类，并实现接口 Iterator。提供 next、hasNext 和 remove 的实现。

实现中会在链表的头尾增加额外的标记节点，前端的头结点和末端的尾节点。如果不使用头结点，那么对第 1 个结点的处理就会变成特殊情况，比如删除时要访问被删除节点之前的一个节点。

public class MyLinkedList<E> implements Iterable<E> {

    private int theSize;

    private int modCount = 0;

    private Node<E> beginMarker;

    private Node<E> endMarker;

//希望Node类只能被MyLinkedList访问且，Node没有用到外部类的方法和属性，因此设置为静态内部类

    private static class Node<E> {

        public E data;//public 访问属性也不会破坏封装，因为Node在MyLinkedList中是private的

        public Node<E> prev;

        public Node<E> next;

        public Node(E data, Node<E> prev, Node<E> next) {

            this.data = data;

            this.prev = prev;

            this.next = next;

        }

    }

    private void doClear() {

        this.beginMarker = new Node<E>(null, null, null);

        this.endMarker = new Node<E>(null, beginMarker, null);

        beginMarker.next = endMarker;

        theSize = 0;

        modCount++;

    }

    public MyLinkedList() {

        doClear();

    }

    public void clear() {

        doClear();

    }

    public int size() {

        return theSize;

    }

    public boolean isEmpty() {

        return theSize == 0;

    }

    public boolean add(E e) {

        add(theSize, e);

        return true;

    }

    public void add(int idx, E e) {

        addBefore(getNode(idx, 0, theSize), e);

    }

    public E get(int idx) {

        return getNode(idx).data;

    }

    public E set(int idx, E newVal) {

        Node<E> p = getNode(idx);

        E oldVal = p.data;

        p.data = newVal;

        return oldVal;

    }

    public E remove(int idx) {

        return remove(getNode(idx));

    }

    private void addBefore(Node<E> p, E e) {

        Node<E> newNode = new Node<>(e, p.prev, p);

        newNode.prev.next = newNode;

        p.prev = newNode;

        theSize++;

        modCount++;

    }

    private E remove(Node<E> p) {

        p.next.prev = p.prev;

        p.prev.next = p.next;

        theSize--;

        modCount++;

        return p.data;

    }

    private Node<E> getNode(int idx) {

        return getNode(idx, 0, theSize - 1);

    }

    private Node<E> getNode(int idx, int lower, int upper) {

        Node<E> p;

        if (idx < lower || idx > upper) {

            throw new IndexOutOfBoundsException();

        }

        if (idx < theSize / 2) {

            p = beginMarker.next;

            for (int i = 0; i < idx; i++) {

                p = p.next;

            }

        } else {

            p = endMarker;

            for (int i = theSize; i > idx; i--) {

                p = p.prev;

            }

        }

        return p;

    }

    public Iterator<E> iterator() {

        return new LinkedListIterator();

    }

    private class LinkedListIterator implements Iterator<E>{

        private Node<E> current = beginMarker.next;

        private int expectedModCount = modCount;

        private boolean okToRemove = false;

        public boolean hasNext() {

            return current != endMarker;

        }

        public E next() {

            if (modCount != expectedModCount){//避免在使用迭代器时，被迭代器之外的方法修改了List

                throw new ConcurrentModificationException();

            }

            if(!hasNext()){

                throw new NoSuchElementException();

            }

            E nextItem = current.data;

            current = current.next;

            okToRemove = true;

            return nextItem;

        }

        public void remove(){

            if (modCount != expectedModCount){

                throw new ConcurrentModificationException();

            }

            if (!okToRemove){

                throw new IllegalStateException();

            }

            MyLinkedList.this.remove(current.prev);

            expectedModCount++;

            okToRemove = false;

        }

    }

}

巴特西

3.5 MyLinkedList 实现

3.5 MyLinkedList 类的实现

最新文章

热门文章