ArrayList和LinkedList

您所在的位置：网站首页 › arraylist和linkedlist的比较 › ArrayList和LinkedList

ArrayList和LinkedList

2023-08-06 00:46| 来源: 网络整理| 查看: 265

Java中ArrayList和LinkedList的区别

两者数据结构不同，ArrayList是基于数组实现、LinkedList是基于双向链表实现。从获取、删除、插入、内存开销这几个点来说明两者的区别。

1、获取：

ArrayList的获取比LinkedList获取相比非常快，因为ArrayList的get方法的时间复杂度为O(1)，而LinkList的为O(n)。

ArrayList的get方法源码：

public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { // 直接下标获取数组值, 时间复杂度为O(1) return (E) elementData[index]; }

LinkList的get方法源码：

public E get(int index){ checkElementIndex(index); return node(index).item; } Node node(int index){ // assert isElementIndex(index); if (index > 1)) { Node x = first; for (int i = 0; i checkElementIndex(index); return unlink(node(index)); } public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } E unlink(Node x){ final E emelemt = 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; }

LinkedList还提供了删除收尾元素的方法，removeFirst()、removeLast()。

ArrayList删除源码如下：

public boolean remove(Object o) { if (o == null) { for (int index = 0; index for (int index = 0; 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; }

结论：LinkedList元素删除比ArrayList要快。

原因：LinkedList的每个元素都维护着两个指针，它们指向列表中的两个相邻元素。因此删除只需要更改将要删除的节点的两个相邻节点中的指针位置。而ArrayList都要进行数组copy移动填充删除元素创建的空间。

3、插入

LinkedList add方法就是向尾部插入方法，时间复杂度为O(1)，而ArrayList add方法时间复杂度是可变的最坏为O(n)，原因是ArrayList扩容的时候需要元素的复制移动。

LinkedList add方法源码如下：

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

ArrayList add方法扩容源码如下：

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }

一般情况下插入LinkedList性能比ArrayList性能要高，但是也不能绝对的说LinkedList插入的性能高，因为这个要根据容量和插入操作（头插、尾插、中间插）来决定。可以通过实验得出以下结论，10万、100万、1000万数据插入的时候：

头插：LinkedList性能比ArrayList高，因为ArrayList要进行大量的复制和位置操作，而LinkedList只是一个对象的实例化。

尾插：ArrayList性能比LinkedList高，因为ArrayList不需要频繁的扩容，而LinkedList需要大量的创建对象。

中间插：ArrayList性能比LinkedList高，因为LinkedList需要遍历寻址。

所以在不同的情况下，需要选择不同的List集合做业务。

4、内存开销

ArrayList维护索引和元素数据，而LinkedList维护元素数据和相邻节点的两个指针，所以LinkedList的内存消耗相对较高。

什么时候用LinkedList，什么时候用ArrayList？

通过上面对比，从时间复杂度来说，LinkedList的插入和删除提供了更好的性能，因此在业务中需要频繁的增删操作，查询较少选择LinkedList较合适。而ArrayList的获取性能比LinkedList高，因此在业务中增删操作较少，获取操作比较多选择ArrayList较合适。

【本文地址】

ArrayList和LinkedList

ArrayList和LinkedList

今日新闻

推荐新闻