Java集合--List源码

源码

上一篇,我们介绍ArrayList和LinkedList的内容,对于这两个类的源码只列举其中的一部分,本篇就来完整的阐述下!!!

希望能让你对这两个类,有一个更完整的理解!

ArrayList

完整源码:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    //实现Serializable接口,生成的序列版本号:
    private static final long serialVersionUID = 8683452581122892189L;

    //ArrayList初始容量大小:在无参构造中不使用了
    private static final int DEFAULT_CAPACITY = 10;

    //空数组对象:初始化中默认赋值给elementData
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //ArrayList中实际存储元素的数组:
    private transient Object[] elementData;

    //集合实际存储元素长度:
    private int size;

    //ArrayList有参构造:容量大小
    public ArrayList(int initialCapacity) {
        //即父类构造:protected AbstractList() {}空方法
        super();
        //如果传递的初始容量小于0 ,抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        //初始化数据:创建Object数组
        this.elementData = new Object[initialCapacity];
    }

    //ArrayList无参构造:
    public ArrayList() {
        //即父类构造:protected AbstractList() {}空方法
        super();
        //初始化数组:空数组,容量为0
        this.elementData = EMPTY_ELEMENTDATA;
    }

    //ArrayList有参构造:Java集合
    public ArrayList(Collection<? extends E> c) {
        //将集合转换为数组:
        elementData = c.toArray();
        //设置数组的长度:
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

    //将ArrayList的数组大小,变更为实际元素大小:
    public void trimToSize() {
        //操作数+1
        modCount++;
        //如果集合内元素的个数,小于数组的长度,那么将数组中空余元素删除
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    //ArrayList集合内元素的个数:
    public int size() {
        return size;
    }

    //判断ArrayList集合元素是否为空:
    public boolean isEmpty() {
        return size == 0;
    }

    //判断ArrayList集合包含某个元素:
    public boolean contains(Object o) {
        //判断对象o在ArrayList中存在的角标位置
        return indexOf(o) >= 0;
    }

    //判断对象o在ArrayList中存在的角标位置:
    public int indexOf(Object o) {
        //如果o==null:
        if (o == null) {
            //遍历集合,判断哪个元素等于null,则返回对应角标
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            //同理:
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果不存在,则返回-1
        return -1;
    }

    //判断对象o在ArrayList中出现的最后一个位置:
    public int lastIndexOf(Object o) {
        //如果o==null:
        if (o == null) {
            //从集合最后一个元素开始遍历:
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            //同理:
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果不存在,则返回-1
        return -1;
    }

    //返回此ArrayList实例的 克隆对象:
    public Object clone() {
        try {
            java.util.ArrayList<E> v = (java.util.ArrayList<E>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    //将ArrayList里面的元素赋值到一个数组中去 生成Object数组:
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    //将ArrayList里面的元素赋值到一个数组中去,专成对应类型的数组:
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    //获取数组index位置的元素:
    E elementData(int index) {
        return (E) elementData[index];
    }

    //获取index位置的元素
    public E get(int index) {
        //检查index是否合法:
        rangeCheck(index);
        //获取元素:
        return elementData(index);
    }

    //设置index位置的元素值了element,返回该位置的之前的值
    public E set(int index, E element) {
        //检查index是否合法:
        rangeCheck(index);
        //获取该index原来的元素:
        E oldValue = elementData(index);
        //替换成新的元素:
        elementData[index] = element;
        //返回旧的元素:
        return oldValue;
    }

    //添加元素e
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    //在ArrayList的index位置,添加元素element
    public void add(int index, E element) {
        //判断index角标的合法性:
        rangeCheckForAdd(index);
        //判断是否需要扩容:传入当前元素大小+1
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

    //得到最小扩容量
    private void ensureCapacityInternal(int minCapacity) {
        //如果此时ArrayList是空数组,则将最小扩容大小设置为10:
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //判断是否需要扩容:
        ensureExplicitCapacity(minCapacity);
    }

    //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        //操作数+1
        modCount++;
        //判断最小扩容容量-数组大小是否大于0:
        if (minCapacity - elementData.length > 0)
            //扩容:
            grow(minCapacity);
    }

    //ArrayList最大容量:
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //帮助ArrayList动态扩容的核心方法:
    private void grow(int minCapacity) {
        //获取现有数组大小:
        int oldCapacity = elementData.length;
        //位运算,得带新的数组容量大小,为原有的1.5倍:
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新扩容的大小依旧小于传入的容量值,那么将传入的值设为新容器大小:
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;

        //如果新容器大小,大于ArrayList最大长度:
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //计算出最大容量值:
            newCapacity = hugeCapacity(minCapacity);
        //数组复制:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //计算ArrayList最大容量:
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        //如果新的容量大于MAX_ARRAY_SIZE。将会调用hugeCapacity将int的最大值赋给newCapacity:
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    //在ArrayList的移除index位置的元素
    public E remove(int index) {
        //检查角标是否合法:不合法抛异常
        rangeCheck(index);
        //操作数+1:
        modCount++;
        //获取当前角标的value:
        E oldValue = elementData(index);
        //获取需要删除元素 到最后一个元素的长度,也就是删除元素后,后续元素移动的个数;
        int numMoved = size - index - 1;
        //如果移动元素个数大于0 ,也就是说删除的不是最后一个元素:
        if (numMoved > 0)
            // 将elementData数组index+1位置开始拷贝到elementData从index开始的空间
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        //size减1,并将最后一个元素置为null
        elementData[--size] = null;
        //返回被删除的元素:
        return oldValue;
    }

    //在ArrayList的移除对象为O的元素,不返回被删除的元素:
    public boolean remove(Object o) {
        //如果o==null,则遍历集合,判断哪个元素为null:
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    //快速删除,和前面的remove(index)一样的逻辑
                    fastRemove(index);
                    return true;
                }
        } else {
            //同理:
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    //快速删除:
    private void fastRemove(int index) {
        //操作数+1
        modCount++;
        //获取需要删除元素 到最后一个元素的长度,也就是删除元素后,后续元素移动的个数;
        int numMoved = size - index - 1;
        //如果移动元素个数大于0 ,也就是说删除的不是最后一个元素:
        if (numMoved > 0)
            // 将elementData数组index+1位置开始拷贝到elementData从index开始的空间
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        //size减1,并将最后一个元素置为null
        elementData[--size] = null;
    }

    //设置全部元素为null值,并设置size为0。
    public void clear() {
        modCount++;
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

    //序列化写入:
    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
        int expectedModCount = modCount;
        s.defaultWriteObject();
        s.writeInt(size);
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    // 序列化读取:
    private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        s.defaultReadObject();
        s.readInt();
        if (size > 0) {
            ensureCapacityInternal(size);
            Object[] a = elementData;
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

    //检查角标是否合法:不合法抛异常
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    //返回一个Iterator对象,Itr为ArrayList的一个内部类,其实现了Iterator<E>接口
    public Iterator<E> iterator() {
        return new java.util.ArrayList.Itr();
    }

    //其中的Itr是实现了Iterator接口,同时重写了里面的hasNext(),next(),remove()等方法;
    private class Itr implements Iterator<E> {
        int cursor; //类似游标,指向迭代器下一个值的位置
        int lastRet = -1; //迭代器最后一次取出的元素的位置。
        int expectedModCount = modCount;//Itr初始化时候ArrayList的modCount的值。
        //modCount用于记录ArrayList内发生结构性改变的次数,
        // 而Itr每次进行next或remove的时候都会去检查expectedModCount值是否还和现在的modCount值,
        // 从而保证了迭代器和ArrayList内数据的一致性。

        //利用游标,与size之前的比较,判断迭代器是否还有下一个元素
        public boolean hasNext() {
            return cursor != size;
        }

        //迭代器获取下一个元素:
        public E next() {
            //检查modCount是否改变:
            checkForComodification();

            int i = cursor;

            //游标不会大于等于集合的长度:
            if (i >= size)
                throw new NoSuchElementException();

            Object[] elementData = java.util.ArrayList.this.elementData;
            //游标不会大于集合中数组的长度:
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            //游标+1
            cursor = i + 1;
            //取出元素:
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            //检查modCount是否改变:防止并发操作集合
            checkForComodification();
            try {
                //删除这个元素:
                java.util.ArrayList.this.remove(lastRet);
                //删除后,重置游标,和当前指向元素的角标 lastRet
                cursor = lastRet;
                lastRet = -1;
                //重置expectedModCount:
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        //并发检查:在Itr初始化时,将modCount赋值给了expectedModCount
        //如果后续modCount还有变化,则抛出异常,所以在迭代器迭代过程中,不能调List增删操作;
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

LinkedList

完整源码:

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    //LinkedList的元素个数:
    transient int size = 0;

    //LinkedList的头结点:Node内部类
    transient java.util.LinkedList.Node<E> first;

    //LinkedList尾结点:Node内部类
    transient java.util.LinkedList.Node<E> last;

    //空实现:
    public LinkedList() {
    }

    //调用添加方法:
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    //LinkedList添加首结点 first:
    public void addFirst(E e) {
        linkFirst(e);
    }
    //first节点插入新元素:addFirst()调用
    private void linkFirst(E e) {
        //头结点:
        final java.util.LinkedList.Node<E> f = first;
        //创建一个新节点,并指向头结点f:
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(null, e, f);
        //将新节点赋值给头几点:
        first = newNode;
        //如果头节点为null,则是第一个元素插入,将新节点也设置为尾结点;
        if (f == null)
            last = newNode;
        else
            //将之前的头结点的前指针指向新的结点:
            f.prev = newNode;
        //长度+1
        size++;
        //操作数+1
        modCount++;
    }

    //添加元素:添加到最后一个结点;
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    //添加最后一个结点 last:
    public void addLast(E e) {
        linkLast(e);
    }

    //last节点插入新元素:addLast()调用
    void linkLast(E e) {
        //将尾结点赋值个体L:
        final java.util.LinkedList.Node<E> l = last;
        //创建新的结点,将新节点的前指针指向l:
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(l, e, null);
        //新节点置为尾结点:
        last = newNode;
        //如果尾结点l为null:则是空集合新插入
        if (l == null)
            //头结点也置为 新节点:
            first = newNode;
        else
            //l节点的后指针指向新节点:
            l.next = newNode;
        //长度+1
        size++;
        //操作数+1
        modCount++;
    }

    //向对应角标添加元素:
    public void add(int index, E element) {
        //检查传入的角标 是否正确:
        checkPositionIndex(index);
        //如果插入角标==集合长度,则插入到集合的最后面:
        if (index == size)
            linkLast(element);
        else
            //插入到对应角标的位置:获取此角标下的元素先
            linkBefore(element, node(index));
    }
    //在succ前插入 新元素e:
    void linkBefore(E e, java.util.LinkedList.Node<E> succ) {
        //获取被插入元素succ的前指针元素:
        final java.util.LinkedList.Node<E> pred = succ.prev;
        //创建新增元素节点,前指针 和 后指针分别指向对应元素:
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ);
        succ.prev = newNode;
        //succ的前指针元素可能为null,为null的话说明succ是头结点,则把新建立的结点置为头结点:
        if (pred == null)
            first = newNode;
        else
            //succ前指针不为null,则将前指针的结点的后指针指向新节点:
            pred.next = newNode;
        //长度+1
        size++;
        //操作数+1
        modCount++;
    }
    //移除首个结点:如果集合还没有元素则报错
    public E removeFirst() {
        final java.util.LinkedList.Node<E> f = first;
        //首节点为null,则抛出异常;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    //删除LinkedList的头结点:removeFirst()方法调用
    private E unlinkFirst(java.util.LinkedList.Node<E> f) {
        //f为头结点:获取头结点元素E
        final E element = f.item;
        //获取头结点的尾指针结点:
        final java.util.LinkedList.Node<E> next = f.next;
        //将头结点元素置为null:
        f.item = null;
        //头结点尾指针置为null:
        f.next = null;
        //将头结点的尾指针指向的结点next置为first
        first = next;
        //尾指针指向结点next为null的话,就将尾结点也置为null(LinkedList中只有一个元素时出现)
        if (next == null)
            last = null;
        else
            //将尾指针指向结点next的 前指针置为null;
            next.prev = null;
        // 长度减1
        size--;
        //操作数+1
        modCount++;
        //返回被删除的元素:
        return element;
    }

    //移除最后一个结点:如果集合还没有元素则报错
    public E removeLast() {
        //获取最后一个结点:
        final java.util.LinkedList.Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        //删除尾结点:
        return unlinkLast(l);
    }
    //删除LinkedList的尾结点:removeLast()方法调用
    private E unlinkLast(java.util.LinkedList.Node<E> l) {
        final E element = l.item;
        final java.util.LinkedList.Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    //删除LinkedList中的元素,可以删除为null的元素,逐个遍历LinkedList的元素;
    //重复元素只删除第一个:
    public boolean remove(Object o) {
        //如果删除元素为null:
        if (o == null) {
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            //如果删除元素不为null:
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    //移除LinkedList结点:remove()方法中调用
    E unlink(java.util.LinkedList.Node<E> x) {
        //获取被删除结点的元素E:
        final E element = x.item;
        //获取被删除元素的后指针结点:
        final java.util.LinkedList.Node<E> next = x.next;
        //获取被删除元素的前指针结点:
        final java.util.LinkedList.Node<E> prev = x.prev;

        //被删除结点的 前结点为null的话:
        if (prev == null) {
            //将后指针指向的结点置为头结点
            first = next;
        } else {
            //前置结点的  尾结点指向被删除的next结点;
            prev.next = next;
            //被删除结点前指针置为null:
            x.prev = null;
        }
        //对尾结点同样处理:
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

    //得到首个结点:集合没有元素报错
    public E getFirst() {
        //获取first结点:
        final java.util.LinkedList.Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    //得到最后一个结点:集合没有元素报错
    public E getLast() {
        //获取last结点:
        final java.util.LinkedList.Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    //判断obj 是否存在:
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
    //LinkedList长度:
    public int size() {
        return size;
    }

    //添加集合:从最后size所在的index开始:
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    //LinkedList添加集合:
    public boolean addAll(int index, Collection<? extends E> c) {
        //检查角标是否正确:
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        java.util.LinkedList.Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) {
            E e = (E) o;
            java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

    //清空LinkedList:
    public void clear() {
        //遍历LinedList集合:
        for (java.util.LinkedList.Node<E> x = first; x != null; ) {
            //将每个结点的前指针 尾指针  元素都置为null:
            java.util.LinkedList.Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        //头尾结点 都置为null:
        first = last = null;
        //长度置为0
        size = 0;
        //操作数+1:
        modCount++;
    }

    //获取相应角标的元素:
    public E get(int index) {
        //检查角标是否正确:
        checkElementIndex(index);
        //获取角标所属结点的 元素值:
        return node(index).item;
    }

    //设置对应角标的元素:
    public E set(int index, E element) {
        checkElementIndex(index);
        java.util.LinkedList.Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    //删除对应角标的元素:
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    //获取对应角标所属于的结点:
    java.util.LinkedList.Node<E> node(int index) {
        //位运算:如果位置索引小于列表长度的一半,从前面开始遍历;否则,从后面开始遍历;
        if (index < (size >> 1)) {
            java.util.LinkedList.Node<E> x = first;
            //从头结点开始遍历:遍历的长度就是index的长度,获取对应的index的元素
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //从集合尾结点遍历:
            java.util.LinkedList.Node<E> x = last;
            //同样道理:
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    // 左移相当于*2,只是要注意边界问题。如char a = 65; a<<1 按照*2来算为130;
    // 但有符号char的取值范围-128~127,已经越界,多超出了3个数值,
    // 所以从-128算起的第三个数值-126才是a<<1的正确结果。
    //而右移相当于除以2,只是要注意移位比较多的时候结果会趋近去一个非常小的数,如上面结果中的-1,0。

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    //判断传入的index是否正确:
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    //检查传入的角标 是否正确:
    private void checkPositionIndex(int index) {
        //必须大于0 ,并且不能大于当前size:
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (java.util.LinkedList.Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (java.util.LinkedList.Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

    //获取第一个元素,不存在则抛异常
    public E element() {
        return getFirst();
    }

    //出队,获取第一个元素,不出队列,只是获取
    // 队列先进先出;不存在不抛异常,返回null
    public E peek() {
        //获取头结点:
        final java.util.LinkedList.Node<E> f = first;
        //存在获取头结点元素,不存在返回null
        return (f == null) ? null : f.item;
    }

    //出队,并移除第一个元素;不存在不抛异常。
    public E poll() {
        final java.util.LinkedList.Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    //出队(删除第一个结点),如果不存在会抛出异常而不是返回null,存在的话会返回值并移除这个元素(节点)
    public E remove() {
        return removeFirst();
    }

    //入队(插入最后一个结点)从最后一个元素
    public boolean offer(E e) {
        return add(e);
    }

    //入队(插入头结点),始终返回true
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    //入队(插入尾结点),始终返回true
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    //出队(从前端),获得第一个元素,不存在会返回null,不会删除元素(节点)
    public E peekFirst() {
        final java.util.LinkedList.Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    //出队(从后端),获得最后一个元素,不存在会返回null,不会删除元素(节点)
    public E peekLast() {
        final java.util.LinkedList.Node<E> l = last;
        return (l == null) ? null : l.item;
    }

    //出队(从前端),获得第一个元素,不存在会返回null,会删除元素(节点)
    public E pollFirst() {
        final java.util.LinkedList.Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    //出队(从后端),获得最后一个元素,不存在会返回null,会删除元素(节点)
    public E pollLast() {
        final java.util.LinkedList.Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

    //入栈,从前面添加  栈 后进先出
    public void push(E e) {
        addFirst(e);
    }

    //出栈,返回栈顶元素,从前面移除(会删除)
    public E pop() {
        return removeFirst();
    }

    //节点的数据结构,包含前后节点的引用和当前节点
    private static class Node<E> {
        //结点元素:
        E item;
        //结点后指针
        java.util.LinkedList.Node<E> next;
        //结点前指针
        java.util.LinkedList.Node<E> prev;

        Node(java.util.LinkedList.Node<E> prev, E element, java.util.LinkedList.Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
        
    //迭代器:
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new java.util.LinkedList.ListItr(index);
    }
    private class ListItr implements ListIterator<E> {
        private java.util.LinkedList.Node<E> lastReturned = null;
        private java.util.LinkedList.Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            java.util.LinkedList.Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
   
    private java.util.LinkedList<E> superClone() {
        try {
            return (java.util.LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    public Object clone() {
        java.util.LinkedList<E> clone = superClone();
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);
        return clone;
    }

    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

    private static final long serialVersionUID = 876323262645176354L;

    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
        s.defaultWriteObject();

        s.writeInt(size);

        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();

        int size = s.readInt();

        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

1802
来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

3696
来自专栏Java后端技术

一道面试题引发的思考

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

710
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

2924
来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

1451
来自专栏前端说吧

JS - 二叉树算法实现与遍历 (更新中...)

4148
来自专栏JavaEdge

二叉树的常用算法递归2 非递归3 小结4 实战coding5序列化和反序列化判断一棵二叉树是否是平衡二叉树判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

5729
来自专栏拭心的安卓进阶之路

Java 集合深入理解(12):古老的 Vector

今天刮台风,躲屋里看看 Vector ! 都说 Vector 是线程安全的 ArrayList,今天来根据源码看看是不是这么相...

2887
来自专栏用户2442861的专栏

List、Set、Map、数组之间各种转换

刚学Java不久的时候,接到一个电面,然后问了一些java的知识,比如说Java的编码,Unicode等,但是最让我蛋疼的是怎么吗map转为set,那个时候对...

3222
来自专栏desperate633

ArrayList实现原理分析(Java源码剖析)ArrayList使用的存储的数据结构ArrayList的初始化ArrayList是如何动态增长ArrayList如何实现元素的移除ArrayList

ArrayList是我们经常使用的一个数据结构,我们通常把其用作一个可变长度的动态数组使用,大部分时候,可以替代数组的作用,我们不用事先设定ArrayList的...

1413

扫码关注云+社区

领取腾讯云代金券