ArrayList与LinkedList增删改查真的是像结论一样吗
我们知道一般八股文中定义的
ArrayList
1. 有序
2. 底层是数组结构存储.
3. 查改快
4. 通过尾插法来保证有序, 指定下标也是后续元素挪移
5. 线程不安全
LinkedList
- 有序
- 底层是链表
- 增删快
- 通过尾插法来保证有序, 指定下标也是改变头尾节点指向
- 线程不安全
那么事实真的完全如定义所说吗?
先说结论: 视情况而定,具体看末尾总结下面看看具体的实现
增
如上定义所说, LinkedList比ArrayList增快
尾插法:
-
ArrayList添加新元素默认尾插, 首先判断是否需要扩容, 其次则是直接在n下标赋值
/** * 新增 * 很简单, 第一步判断是否需要扩容, 第二步直接赋值尾结点 */ public boolean add(E e) { // 判断是否需要进行扩容 ensureCapacityInternal(size + 1); // 赋值 elementData[size++] = e; return true; } -
LinkedList尾插, 因为LinkedList保存了头尾节点的原因, 所以尾结点直接修改指向
/** * 新增尾结点 * 由方法可知, 尾结点在类中是有存储的 */ 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++; }
头插法:
-
ArraList如果想指定位置插入, 需要使用
add(int index, E element)方法.如下所示:/** * 新增指定下标的元素 */ public void add(int index, E element) { //查看当前下标是否在当前数组的长度范围内, 超过会抛出异常的 rangeCheckForAdd(index); //判断是否需要进行扩容 ensureCapacityInternal(size + 1); //复制数组.但是注意会空出来index下标的元素, 扩容后的数组index下标后会后移 System.arraycopy(elementData, index, elementData, index + 1, size - index); //赋值指定下标的元素. elementData[index] = element; size++; } -
LinkedList在头结点插入同尾结点一样,都是有保存
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++; }
中插法:
-
同头插一样, ArraList如果想指定位置插入, 需要使用
add(int index, E element)方法. -
而LinkedList中插法如下:
/** * 指定结点插入元素 */ public void add(int index, E element) { //判断结点是否有效 checkPositionIndex(index); //如果是结尾, 用尾插法 if (index == size) linkLast(element); //要么就挪移了 else linkBefore(element, node(index)); } /** * 在非空结点前插入 */ void linkBefore(E e, Node<E> succ) { // assert succ != null; 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; size++; modCount++; }linkedList 看起来没什么问题, 也是只改变下指向而已, 但是因为这时候我们不知道指向要改成什么,所以在调用linkBefore之前, 需要计算出来当前位置的元素, 也就是说LinkedList需要先查后增(
node(index)方法)/** * 返回非空指定index的结点. 虽然在查询效率上做了优化,但是还是要遍历一半元素 * 同时一半元素越靠近中值效率越低 */ Node<E> node(int index) { //尝试缩小范围, 如果index比size的一般小,那么就前半查询 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; } }
删
如上所说, LinkedList比ArrayList删除快
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); // 这里取了个巧, 直接赋值为null.让GC自己去回收丢失引用的对象 elementData[--size] = null; return oldValue; } -
指定元素
/** * 删除元素 * 其中 fastRemove偷了个懒, 直接把对应下标元素置null */ public boolean remove(Object o) { //为空,第一个为null的元素 if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } //不为空,使用equals删除第一个相同的元素.equals具体实现交给泛型自己处理 } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }
LinkedList删除分四种删除头结点/尾结点/中间结点下标/和中间结点元素:
-
删除头结点
/** * 删除头结点 将next结点,前指向赋值为空 */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } -
删除尾结点
尾结点同头结点删除, 将后指向赋值为空
-
删除中间结点下标
/** * 1. 首先检查是否越界. 其次又回到node(index)方法先查找,然后再unlink.unlink方法很简单 */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }/** * 很简单的方法, 前后指向赋值为空,当前元素置null */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> 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; } -
删除中间结点元素, 这个是直接调用上述的
unlink方法. 没有查询步骤.直接遍历删除
改
ArrayList在确认下标无误后, 直接赋值就可以了
/**
* 用元素替换指定index
*/
public E set(int index, E element) {
//校验下标越界
rangeCheck(index);
//通过下标查询,再直接赋值
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
LinkedList在确认index无误后, 需要额外去查询到当前指向节点
/**
* 设置指定元素
*/
public E set(int index, E element) {
//校验元素是否越界
checkElementIndex(index);
//找到对应元素,然后替换掉
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
查
这部分就不需要赘述了, ArrayList 直接拿取对应下标, 而LinkedList是经典的node(index)方法
总结
总结下来看: (因为ArrayList复制数组使用C++的copy方法.,确认不了暂时存疑, 先以网上结论为主)
ArrayList和LinkedList的增删效率可以分为三种情况：在头部增删，在中间增删和在尾部增删
当头部增删时：
LinkedList的效率是要优于ArrayList的，因为ArrayList要进行大量的数据迁移
在中间增删时:
LinkedList的效率要低于Arraylist的，因为Linked在从头部头部或者尾部遍历找到对应的节点，而ArrayList迁移的数据就比较少了
在尾部增删时：
1.当数据量较少时，两种的效率都很高，只需要在尾部添加元素即可
2.当添加的元素有一定规模时，LinkedList的效率要高于ArrayList，因为ArrayList要频繁的扩容，复制数据，耗费时间
3.当添加的元素非常大时，ArrayList的效率就要高于LinkedList，因为随着ArrayList的长度的增加，其扩容的次数会大大降低. ArrayList只需要一个简单的赋值就完成了. 而LinkedList需要不断地分配内存空间再进行赋值，本身效率就低于ArrayList的
而查询LinkedList就没有的比了
在修改上,和删除一个理解. ArrayList越靠前越差, 而LinkedList越靠近中值越差. 两者尾部是基本相同的
所以还是要根据使用场景去选择, 而不是直接根据定义去使用
评论区