| 谈谈ArrayList和LinkedList的区别？ | 您所在的位置：网站首页 › arraylist和linkedlist扩容 › 谈谈ArrayList和LinkedList的区别？ |
谈谈ArrayList和LinkedList的区别？
|
ArrayList和LinkedList是Java中两种常见的集合类，它们都实现了List接口，但在使用过程中却存在一些区别。本文将详细分析ArrayList和LinkedList的区别，并提供相应的代码示例。 1. 数据结构ArrayList和LinkedList采用不同的数据结构来存储元素。ArrayList是基于数组实现的，内部维护着一个Object[]数组。每当数组无法容纳更多元素时，ArrayList会自动扩容，将原有的元素复制到一个新的更大的数组中。 相比之下，LinkedList是基于双向链表实现的，内部维护着一个Node节点序列。每个节点包含了指向前一节点和后一节点的引用，通过这种方式将节点链接起来。此外，LinkedList还有指向头节点和尾节点的引用，方便进行头尾操作。 虽然两种数据结构各有优劣，但总体来说，ArrayList的读取效率要高于LinkedList，因为数组可以直接按照索引随机访问，而链表需要从头开始遍历直到目标位置。而LinkedList的插入和删除操作比ArrayList更加高效，因为LinkedList只需要修改节点的引用，而ArrayList需要进行数组复制和移动元素等操作。 ArrayListArrayList 实现了 List 接口，继承了 AbstractList 抽象类。 底层是基于数组实现的，并且实现了动态扩容（当需要添加新元素时，如果 elementData 数组已满，则会自动扩容，新的容量将是原来的 1.5 倍），有空可以去看一下 ArrayList 的源码。 Java中的ArrayList是基于数组实现的，它内部维护了一个Object[]数组作为元素存储结构。当我们向ArrayList添加元素时，如果空间不足，ArrayList会根据需要自动扩容。扩容时，ArrayList会创建一个更大的数组，并将原有的元素复制到新的数组中。同时，ArrayList还支持通过索引快速访问和修改数组中的元素。 以下是Java ArrayList的基本定义和实现原理： 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 = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } }在上述代码中，我们可以看到： ArrayList中包含了一个Object[]数组作为元素存储结构，名为elementData； 当我们向ArrayList添加元素时，每次都会判断当前的elementData数组是否够用，不够用则自动进行扩容，并将原有元素复制到新的更大数组中； ArrayList还提供了ensureCapacityInternal、ensureExplicitCapacity和grow方法来实现动态扩容操作； 在扩容时，ArrayList会按照一种经典的策略——按原有的数组长度增长一半的方式进行扩容。Java的ArrayList是一种高效的集合类，它不仅具备了数组的随机访问性能，同时支持动态扩容。 LinkedList
下面是Java LinkedList的基本节点类定义： private static class Node { E item; Node prev; Node next; Node(Node prev, E element, Node next) { this.item = element; this.prev = prev; this.next = next; } }其中，item属性存储节点的数据值，prev属性和next属性分别存储前一个节点和后一个节点的引用。在创建LinkedList时，我们需要为它初始化一个空的头节点和尾节点。头节点和尾节点之间没有元素时，prev和next都指向自身。当有元素加入时，头节点的next指向新的节点，尾节点的prev指向新的节点。 以下是一个简单的Java LinkedList示例代码： import java.util.LinkedList; public class LinkedListDemo { public static void main(String[] args){ LinkedList linkedList = new LinkedList(); linkedList.addFirst("A"); linkedList.addLast("B"); linkedList.addLast("C"); for(String s : linkedList){ System.out.println(s); } } }输出结果： A B C以上示例代码中，我们通过addFirst和addLast方法向LinkedList添加元素，并使用for-each语句遍历LinkedList中的所有元素。LinkedList中的元素是按照它们添加的顺序保存的。 2. 内存消耗由于ArrayList是基于数组实现的，因此它的内存消耗较大。在实际应用中，如果数组的大小超过了实际元素的数量，就会造成内存浪费。另外，由于ArrayList需要在数组满时进行扩容，因此如果重复执行插入操作，则会导致数组不断扩容，进而造成频繁的GC。 相比之下，LinkedList的内存消耗较小。由于它采用双向链表的数据结构，并且可以动态调整节点位置，因此只需要在每个节点中存储前一个和后一个节点的引用即可。在链表中插入或删除节点时，只需要修改节点的引用即可，不需要进行额外的内存分配和复制操作。 3. 随机访问性能由于ArrayList是基于数组实现的，因此它在随机访问方面的性能比LinkedList更好。在ArrayList中，可以通过索引值来直接访问数组中的元素，而在LinkedList中，必须先遍历到目标位置才能访问到相应的元素。 以下是使用ArrayList和LinkedList进行随机访问的示例代码： List arrayList = new ArrayList(); for(int i=0; i |
【本文地址】