获取arraylist的长度_ArrayList和LinkedList你确定能答清楚吗

ArrayList和LinkedList区别

这道题可以简要回答：

1：ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2：对于随机访问get和set，ArrayList 优于LinkedList，因为LinkedList要移动指针。

3：对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

对于两者区别后面解读。

删除添加读取等操作的时间复杂度

ArrayList 是线性表(数组)

get() ：直接读取第几个下标，复杂度 O(1)

add(E) ：添加元素，直接在后面添加，复杂度O(1)

add(index, E) ：添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O(n)

remove()：删除元素，后面的元素需要逐个移动，复杂度O(n)

LinkedList 是链表

get() ：获取第几个元素，依次遍历，复杂度O(n)

add(E) ：添加到末尾，复杂度O(1)

add(index, E) ：添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)

remove() ：删除元素，直接指针指向操作，复杂度O(1)

两者的优缺点

ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：

1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList不支持高效的随机元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

源码分析

ArrayList

底层是基于动态数组，根据下表随机访问数组元素的效率高，向数组尾部添加元素的效率高；但是，删除数组中的数据以及向数组中间添加数据效率低，因为需要移动数组。例如最坏的情况是删除第一个数组元素，则需要将第2至第n个数组元素各向前移动一位。而之所以称为动态数组，是因为Arraylist在数组元素超过其容量大，Arraylist可以进行扩容(针对JDK1.8 数组扩容后的容量是扩容前的1.5倍)。

Arraylist源码中最大的数组容量是Integer.MAX_VALUE-8，对于空出的8位，目前解释是 ：

①存储Headerwords

②避免一些机器内存溢出，减少出错几率，所以少分配

③最大还是能支持到Integer.MAX_VALUE(当Integer.MAX_VALUE-8依旧无法满足需求时)

初始默认容量10，扩容因子0.5。这里说的10是第一次扩容时，如果没有指定大小，在第一次调用add才会被触发。

由构造方法可知，ArrayList的本质就是一个数组。

public ArrayList(int initialCapacity) {        if (initialCapacity > 0) {            this.elementData = new Object[initialCapacity];…… 省略

‍ add 方法会先检查是否越界，再决定是否扩容，本质就是先创建一个扩容后长度的数组，再通过 System.arraycopy 方法复制原属组数据。所以，对于数组元素的删除，还是相当于 通过 System.arraycopy 来集体将要删除数据后的数据往前移。

public E remove(int index) {    rangeCheck(index);    modCount++;    E oldValue = elementData(index);    int numMoved = size - index - 1;    if (numMoved > 0)        System.arraycopy(elementData, index+1, elementData, index,                         numMoved);//其实还是用arrayCopy挪来挪去 /*  arraycopy(Object src, int srcPos, Object dest, int destPos, int length)参数解释:　　Object src : 原数组   int srcPos : 从元数据的起始位置开始　　Object dest : 目标数组　　int destPos : 目标数组的开始起始位置　　int length  : 要copy的数组的长度　　*/    elementData[--size] = null; // clear to let GC do its work    return oldValue;}

LinkedList

LinkedList 初始长度为0，本质就是一个链表，由一个个节点组成，会记录一个头节点和一个尾节点。get任意元素复杂度为 o(n) ，取first和last元素都是o(1)复杂度，因为已经保存好了。

 private static class Node {        E item;        Node next;        Node prev;        Node(Node prev, E element, Node next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }

所以对于链表的的操作大家都明白了吧，这属于数据结构基础知识，不做赘述。

add方法

void linkLast(E e) {    final Node l = last;    final Node newNode = new Node<>(l, e, null);    last = newNode;    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}

remove方法

E unlink(Node x) {    // assert x != null;    final E element = x.item;    final Node next = x.next;    final Node prev = x.prev;    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }    x.item = null;    size--;    modCount++;    return element;}

◆ ◆ ◆ ◆ ◆

关注并后台回复 “面试” 或者 “视频”，

即可免费获取最新2019BAT

大厂面试题和大数据微服务视频

您的分享和支持是我更新的动力

·END·

后端开发技术