ArrayList和LinkedList的区别

文章目录

• • ArrayList和linkedList的区别
  • • ArrayList
    • linkedList
    • 区别
    • • 1.底层数据结构
      • 2.插入和删除是否受元素位置的影响
      • 3.是否支持高效随机访问
      • 4.内存空间占用
    • ArrayList和linkedList源码对比
    • • 1.底层数据结构
      • 2.插入元素到列表末端
      • 3.增加元素到列表任意位置
      • 4.删除任意位置元素
      • 5.获取数据
    • 遍历
    • linkedList可以使用索引方式去访问吗？
    • 其他

ArrayList和linkedList的区别 ArrayList

ArrayList：基于动态数组，连续的内存存储，适合下标访问（随机访问），扩容机制：因为数组长度固定，超出数组长度存数据时需要新建数组，然后将老数组的数据拷贝到新数组，如果不是尾部插入法还会涉及到元素的移动，使用尾插法并指定初始容量可以极大提升性能，甚至超过linkedList(因为它需要创建大量的node对象)。
 

linkedList

linkedList：基于双向链表，可以存储在分散的内存中，适合做数据插入及删除操作，不适合查询，因为需要逐一遍历。遍历linkedList必须使用iterator（迭代器）而不能使用for循环，因为for循环体内通过get(i)取得某一元素时都需要对list重新进行遍历，性能消耗极大。也不能使用indexOf返回元素索引，并利用其进行遍历，使用indexOf对list进行遍历，当结果为空时会遍历整个列表。（1.7之前是循环链表，1.8后是双向链表）
 

区别 1.底层数据结构

ArrayList：动态数组

linkedList：双向链表

2.插入和删除是否受元素位置的影响

ArrayList：如果不是尾插法，插入和删除的时间复杂度受元素位置的影响；

linkedList：插入和删除的时间复杂度不受元素位置的影响。

3.是否支持高效随机访问

linkedList不支持高效的随机元素访问，而ArrayList支持高效随机访问。

4.内存空间占用

ArrayList空间占用体现在list列表结尾会预留一定的容量空间；

linkedList空间消耗体现在每一个元素要保存前后节点的引用（node对象）。

 

ArrayList和linkedList源码对比 1.底层数据结构

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
{
	private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
}

public class linkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node first;
    transient Node last;
}

 

2.插入元素到列表末端

ArrayList尾部添加数据的时间复杂度O(1)

//ArrayList
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//扩容（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);
}

linkedList尾部添加数据的时间复杂度O(1)

//linkedList
public boolean add(E e) {
    linkLast(e);
    return true;
}

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++;
}

 

3.增加元素到列表任意位置

//ArrayList
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

每次插入操作，都会进行一次数组复制。而当增加元素到 list 尾端的时候是不存在的，大量的数组重组操作会导致系统性能低下，并且插入元素在 list 中的位置越是靠前，数组重组的开销也越大。时间复杂度O(n-i)。

 

//linkedList
public void add(int index, E element) {
    checkPositionIndex(index);

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

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++;
}

void linkBefore(E e, Node succ) {
    // assert succ != null;
    final Node pred = succ.prev;
    final Node newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

linkedList在尾端插入数据与在任意位置插入数据是一样的，都没有元素的移动。

 

4.删除任意位置元素

//ArrayList
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);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

在ArrayList的每一次删除元素操作后，都要进行数组的重组，并且删除的位置越靠前，数组重组时的开销越大。

 

//linkedList
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

Node node(int index) {
    // assert isElementIndex(index);

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

在linkedList的实现中，首先要通过循环找到要删除的元素。如果要删除的位置处于 List 的前半段，则从前往后找；若其位置处于后半段，则从后往前找。因此无论要删除较为靠前或者靠后的元素都是非常高效的；但要移除 List 中间的元素却几乎要遍历完半个List，在List拥有大量元素的情况下，效率比较低。
 

5.获取数据

//ArrayList
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

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

直接通过下标获取数据，高效随机访问

 

//linkedList
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node node(int index) {
    // assert isElementIndex(index);

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

需要通过循环找到对应的位置，然后获取数据，随机访问效率低
 

遍历

为什么ArrayList基本都用for循环遍历，不用Iterator迭代器遍历，而linkedlink都用Iterator遍历，极少用for循环遍历？

ArrayList实现了RandomAccess（随机访问）的接口，标志性接口。

Collections类
    
public static 
    int binarySearch(List> list, T key) {
        if (list instanceof RandomAccess || list.size() 
 
 
linkedList可以使用索引方式去访问吗？ 
不能，因为ArrayList的索引是标识出来的，而linkedList的索引是隐式的。
 
其他 
一个评论区看到的
 
 
 
• ArrayList 与 linkedList 区别
 共同点
 • 都是 AbstractList 的子类
 • 都实现了 Cloneable 跟 Serializable 接口 代表 可以使用克隆以及序列化
 • 都保证了数据的顺序读写
 • 都可以存Null值 / 重复的数据
 • 都是通过索引获取元素
 • 都是线程不安全的集合 都可以通过 Collections.synchronizedList(List?) 创建一个线程安全的集合
 不同点
 • ArrayList
 • 实现了 RandomAccess 接口 提供了快速定位资源位置的功能 (其实也就是 使用for循环效率高 )
 • size() | isEmpty() | get() | set() | iterator() | 时间复杂度为O (1)
 • add 添加操作时间复杂度平均为 O(n)
 • 占用空间小 不需要额外空间维护链表结构
 • 适合 根据索引查询多的场景
 • linkedList
 • 实现了Queue | Deque 接口 可以当做双向队列,栈来使用
 • 头尾添加数据时间复杂度为 O(1) 其他位置插入复杂度为O(n)
 • 获取头尾数据时间复杂度为O(1) 其他位置最差时间复杂度为O(n)
 • 删除数据时间复杂度为O(1)
 • 需要额外空间维护链表结构 以保证顺序读写的正确性
 • 适合做 删除操作多的场景