对于ArrayList和LinkedList的理解

以下开始对于ArrayList和LinkedList的理解,主要从以下几点分析:


1、从继承结构上分析

        从继承结构来看,ArrayList和LinkedList都是Collecttion顶级接口下的List接口的具体实现类。ArrayList继承自AbstractList抽象类,AbstractList抽象类又继承自AbstractCollection抽象类,AbstractCollection抽象类实现了Collection接口;对于LinkedList它继承自AbstractSequentialList抽象类,AbstractSequentialList抽象类又继承自AbstractList的抽象类,AbstractList有继承自AbstractCollection抽象类,最终实现Collection接口。
        

2、从底层数据结构分析(包括扩容机制、优缺点、应用场景)

        ArrayList简介它是一个动态数组,底层的数据结构是一个数组
        ArrayList特点对于ArrayList数组来说,它的查找效率很高,会根据数组下标索引查找对应的数值,时间复杂度是O(1),但是对于添加和删除元素来说,性能不好时间复杂度是O(n)。
        ArrayList底层原理
    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

        会发现它的默认容量是 10

        分析构造函数:(无参构造函数)
        public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
        直接使用默认的容量10,来进行初始化。
        那数据具体是存在哪里呢?
transient Object[] elementData; // non-private to simplify nested class access
        会发现它在底层维持了一个叫做:Object[]数组的 elementData数组。
        分析有参构造函数:(还有一个参数--容量)
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
        现在就开始分析,它在添加一个元素的时候是干了什么事情:
        public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
        在添加一个元素的时候,干了两件事:第一,对容量进行管理;第二,添加元素向数组。
    // 对容量进行管理
        private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
        // 对容量进行计算
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
        // 判断是不是要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
        // 进行扩容 , 每次扩容 1.5 倍
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }  
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        这里表明ArrayList在扩容的时候,当前的容量如果大于MAX_ARRAY_SIZE就将容量设置为Integer.MAX_VALUE,反之的话,容量设置为MAX_ARRAY_SIZE。
        ArrayList应用场景:ArrayList更加适合查找多修改少的场景。
        
        LinkedList的简介:LinkedList是一个双向链表,存储数据的时候在链表中存储。
        LinkedList的特点:LinkedList在添加元素和删除元素的时候的性能要比ArrayList要好很多,它的时间复杂度是O(1),但是在查找的时候,对于链表的头和尾除外的结点,是需要一个个遍历查    找的,时间复杂度是O(n)。
        LinkedList的底层源码
    public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
        会发现源码,它里面有first结点,也有last结点,分别代表头结点和尾结点。在整个的设计中,会发现他是一个双向链表的结构。
        分析它的添加一个元素的源码:
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
        会发现,它调用了一个尾插法的方法,值得说的是,在源码中,他设计了两个方法进行添加值,一个是头插法一个是尾插法。
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
        它和ArrayList不同的是ArrayList是有自己的扩容机制的,并且每次的扩容都是以1.5倍的方式实现扩容,但是LinkedList是不需要扩容的,因为,链表需要扩容吗?显然不需要,只要你的内存多,理论上可以是无限。
        LinkedList的应用场景:LinkedList更加适合频繁的对元素进行增删,但是对查找少的场景。

全部评论

相关推荐

11-08 10:39
门头沟学院 C++
点赞 评论 收藏
分享
10-14 10:56
已编辑
长沙学院 嵌入式软件开发
痴心的00后拿到了ssp:hr面挂了,无所谓了反正不去😃
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务