java ArrayList和LinkedList的区别 java中ArrayList和LinkedList的区别介绍

时间:2021-01-16 萌萌萌桃子人气:0

ArrayList和LinkedList都实现了List接口，有以下的不同点：

1、ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。
2、相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
3、LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

ArrayList扩容：

总的来说就是分两步：

1、扩容

把原来的数组复制到另一个内存空间更大的数组中

2、添加元素

把新元素添加到扩容以后的数组中
无参构造：

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_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);
  }
}

在无参构造中，我们看到了在用无参构造来创建对象的时候其实就是创建了一个空数组，长度为0
在有参构造中，传入的参数是正整数就按照传入的参数来确定创建数组的大小，否则异常
接下来我们来看扩容，扩容的方法就是 add(E e)

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

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

int newCapacity = oldCapacity + (oldCapacity >> 1);
oldCapacity >> 1 右移运算符原来长度的一半再加上原长度也就是每次扩容是原来的1.5倍
之前的所有都是确定新数组的长度，确定之后就是把老数组copy到新数组中，这样数组的扩容就结束了
以上的一切都是ArrayList扩容的第一步，第二步就没啥说的了，就是把需要添加的元素添加到数组的最后一位

加载全部内容