java面试 - ArrayList LinkedList 区别 - 《测开架构师》

ArrayList 是基于数组实现的，LinkedList 是基于双向链表实现的
ArrayList 在新增和删除元素时，因为涉及到数组复制，所以效率比 LinkedList 低，而在遍历的时候，ArrayList 的效率要高于 LinkedList

共同点：

ArrayList、LinkedList 都实现了 List 接口
- 对应的List的方法都可以使用，只不过实现逻辑不同
- 都允许有重复元素、有先后放入次序
- 都可以位置（索引）访问

ArrayList 继承的是 AbstractList 抽象类
LinkedList 是一个继承自 AbstractSequentialList 的双向链表，因此它也可以被当作堆栈、队列或双端队列进行操作，
- AbstractSequentialList 继承 AbstractList 抽象类

底层数据结构不同

ArrayList 底层是基于数组实现的，对应成员变量声明都是一个 Object 类型的数组
- 默认初始化大小的容量是 10 default-capacity
- size 是数组里真正元素的个数
  - 不声明数组长度的时候，添加第一个元素，这时，数组长度elementData.length 为10，size为1
ArrayList的数据结构为数组

pulic class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; 
    private int size;
}

LinkedList 底层是一个个双向链表的Node结点
一个 Node 结点包含 3 个部分：
- 元素内容 item
- 前引用 prev
- 后引用 next
LinkedList的数据结构为队列，先进先出

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

构造方法不同

都可以构造一个包含指定集合元素的列表
ArrayList 有有参构造和无参构造
- 如果业务上已知数组长度，声明 ArrayList 的时候就声明大小
- 这样内存空间不会有浪费

比如想要数组大小是7，已经知道数组长度，<br />    如果声明ArrayList的时候不声明大小，<br />    那么默认在内存中ArrayList占用的空间是10个的大小空间，<br />    这样对应有3个大小的空间其实是被浪费掉的，<br />    所以这个时候我们就要用数组长度参数的构造方法去声明，来节约内存占用空间

LinkedList 只有无参

添加元素不同

ArrayList

ArrayList 如果构造的时候不声明集合大小，添加元素时默认初始化10个空间大小；
添加元素的时候如果内存空间不够，则需要进行扩容，ArrayList 使用的是动态扩容，每次扩容1.5倍

数组声明为dataArr，存放在堆中，具体的数据是在栈中，dataArr指向栈里面引用。

动态扩容的时候在栈中新生成一份内存空间，dataArr进行一个重新指向就可以了，以前引用的直接java垃圾回收。

对于我们来说看到的还是dataArr，只不过对应的dataArr指向了新的引用空间。

老的内存空间就干掉了，数组对应的物理地址引用，指向了新的内存空间。

直接添加元素

add(E e)

add(e, elementData, size);

add(E e, Object[] elementData, int s)

 if (s == elementData.length)
       elementData = grow();

指定位置添加元素

add(int index, E element)

if ((s = size) == (elementData = this.elementData).length)
   elementData = grow();

由上可见，都是 数组内元素个数 和 数组长度 进行对比，如果相等，则进行动态扩容
动态扩容，就是从原有数组拷贝到新扩容后的数组

elementData = Arrays.copyOf(elementData,
                         newCapacity(minCapacity));

扩容倍数为原有数组长度的1.5

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

新增元素也有两种情况，一种是直接将元素添加到队尾，一种是将元素插入到指定位置。

LinkedList

增加元素的方式有三种：

链表头部插入值；
尾部插入值；
中间某个元素前插入值。

尾部插入值

add(E e)

linkLast(e);

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;

1.最后一个结点 last 放在临时变量 l
2.根据添加的元素生成新 Node 结点 (l, e, null)
3. last 结点更新为刚刚新生成的 Node 结点
4.如果原集合尾结点为 null ,那头结点 first 为新结点
5.否则新结点赋值给原集合尾结点的 next

指定位置添加

add(int index, E element)

 if (index == size)
     linkLast(element);
 else
     linkBefore(element, node(index));

linkBefore(element, node(index));
- node(index)

   Node<E> node(int index) {
       if (index < (size >> 1)) {
           Node<E> x = first;
           for (int i = 0; i < index; i++)
               x = x.next;
           return x;
       } else {
           Node<E> x = last;
           for (int i = size - 1; i > index; i--)
               x = x.prev;
           return x;
       }
   }

linkBefore

   final Node<E> pred = succ.prev;
   final Node<E> newNode = new Node<>(pred, e, succ);
   succ.prev = newNode;
   if (pred == null)
       first = newNode;
   else
       pred.next = newNode;

如果指定位置是集合长度，直接最后追加
如果不是，则进行指定位置添加 linkBefore
添加前调用 node() 方法查找指定位置上的元素
node(index) 里面遍历 LinkedList 。
如果下标index是前半段，则从头开始遍历；
如果下标index是后半段，则从尾开始遍历。
所以，插入的位置index 越靠近中间位置，遍历花费的时间越多。
找到指定位置元素（succ），开始执行linkBefore
将 succ 的前一个节点（prev）存放到临时变量 pred 中
生成新的 Node 节点（newNode）
将 succ 的前一个节点变更为 newNode
若 pred 为 null，说明插入的是队头，所以 first 为新节点；
否则将 pred 的后一个节点变更为 newNode。

当两者的起始长度一样

如果是从集合的头部新增元素，ArrayList 花费的时间应该比 LinkedList 多，因为需要对头部以后的元素进行复制。

class d{
    public static void addFromHeaderArrayListTest(int num) {
        ArrayList<String> list = new ArrayList<String>(num);
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            list.add(0, i + "gaigai");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList从集合头部位置新增元素花费的时间" + (timeEnd - timeStart));
    }
    public static void addFromHeaderLinkedListTest(int num) {
        LinkedList<String> list = new LinkedList<String>();
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            list.addFirst(i + "gaigai");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("LinkedList从集合头部位置新增元素花费的时间" + (timeEnd - timeStart));
    }
}

如果是从集合的中间位置新增元素，ArrayList 花费的时间搞不好要比 LinkedList 少，因为 LinkedList 需要遍历。

class d{
  public static void addFromMidArrayListTest(int num) {
      ArrayList<String> list = new ArrayList<String>(num);//不计算动态扩容
//        LinkedList<String> list = new LinkedList<String>();
      int i = 0;
      long timeStart = System.currentTimeMillis();
      while (i < num) {
          int temp = list.size();
          list.add(temp / 2, i + "gaigai");
          i++;
      }
      long timeEnd = System.currentTimeMillis();
      System.out.println(list);
      System.out.println("ArrayList从集合中间位置新增元素花费的时间" + (timeEnd - timeStart));
  }
}

如果是从集合的尾部新增元素，ArrayList 花费的时间应该比 LinkedList 少，因为数组是一段连续的内存空间，也不需要复制数组；而链表需要创建新的对象，前后引用也要重新排列。

class d{
    public static void addFromTailArrayListTest(int num) {
        ArrayList<String> list = new ArrayList<String>(num);
//        LinkedList<String> list = new LinkedList<String>();
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            list.add(i + "gaigai");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList从集合尾部位置新增元素花费的时间" + (timeEnd - timeStart));
    }
}

总结：

ArrayList 在添加元素的时候如果不涉及到扩容，性能在两种情况下（中间位置新增元素、尾部新增元素）比 LinkedList 好很多，只有头部新增元素的时候比 LinkedList 差，因为数组复制的原因。

获取不同

根据下标获取元素

get(int index)

ArrayList

快速随机访问是什么意思呢？
- 就是说不需要遍历，就可以通过下标（索引）直接访问到内存地址
return elementData(index);
直接返回数组元素

   E elementData(int index) {
       return (E) elementData[index];
   }

ArrayList 实现了 RandomAccess 接口，RandomAccess是一个标记接口：
- 内部是空的，标记“实现了这个接口的类支持快速（通常是固定时间）随机访问”。快速随机访问是什么意思呢？就是说不需要遍历，就可以通过下标（索引）直接访问到内存地址。

LinkedList

return node(index).item;
调用 node(int) 方法，{需要集合分前后半段遍历了}

   Node<E> node(int index) {
       if (index < (size >> 1)) {
           Node<E> x = first;
           for (int i = 0; i < index; i++)
               x = x.next;
           return x;
       } else {
           Node<E> x = last;
           for (int i = size - 1; i > index; i--)
               x = x.prev;
           return x;
       }
   }

根据元素获取下标

indexOf(Object o)

ArrayList

return indexOfRange(o, 0, size);
返回最小的索引，没有返回-1
如果是null，则返回null的下标

   int indexOfRange(Object o, int start, int end) {
       Object[] es = elementData;
       if (o == null) {
           for (int i = start; i < end; i++) {
               if (es[i] == null) {
                   return i;
               }
           }
       } else {
           for (int i = start; i < end; i++) {
               if (o.equals(es[i])) {
                   return i;
               }
           }
       }
       return -1;
   }

LinkedList

需要遍历整个链表，和 ArrayList 的 indexOf() 类似


    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;

遍历不同

对集合遍历，通常有两种做法，
- 一种是使用 for 循环，
- 一种是使用迭代器（Iterator）

for (int i=0, n=list.size(); i < n; i  )
    list.get(i);
for (Iterator i=list.iterator(); i.hasNext(); )
       i.next();

LinkedList

get():在 get 的时候性能会非常差，因为每一次外层的 for 循环，都要执行一次 node(int) 方法进行前后半段的遍历
iterator():
- 执行 list.iterator()
  - 1.执行的是 AbstractSequentialList 的 iterator()
  - 2.再调用 AbstractList 类的 listIterator()
  - 3.再调用 LinkedList 类的 listIterator(int) 方法
    - 返回的是 LinkedList 类的内部私有类 ListItr 对象
- 执行 ListItr 的构造方法时调用了一次 node(int) 方法，返回第一个节点

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

之后，迭代器就执行 hasNext() 判断有没有下一个，执行 next()方法下一个节点

ArrayList

get():ArrayList 是由数组实现的，所以根据索引找元素 (get) 非常的快，一步到位
iterator():

总结

for 循环遍历的时候，ArrayList 花费的时间远小于 LinkedList；迭代器遍历的时候，两者性能差不多。