作文网站高中,昆明小程序开发公司,泉州企业做网站,怎么设计公司的网站模板目录
1. 数据结构
2. 性能特点
3. 源码分析
4. 代码演示
5. 细节和使用场景 ArrayList 和 LinkedList 分别代表了两类不同的数据结构#xff1a;动态数组和链表。它们都实现了 Java 的 List 接口#xff0c;但是有着各自独特的特点和性能表现。
1. 数据结构
ArrayList… 目录
1. 数据结构
2. 性能特点
3. 源码分析
4. 代码演示
5. 细节和使用场景 ArrayList 和 LinkedList 分别代表了两类不同的数据结构动态数组和链表。它们都实现了 Java 的 List 接口但是有着各自独特的特点和性能表现。
1. 数据结构
ArrayList 是基于可调整大小的数组实现的。它允许快速随机访问因为内部元素可通过数组索引直接访问。LinkedList 是基于双向链表实现的。链表中的每个元素都包含了对其前一个和后一个元素的引用允许双向遍历。
2. 性能特点
特性/操作ArrayListLinkedList随机访问O(1)O(n)添加元素(一般)O(1) (摊销时间)O(1)在末尾添加元素O(1) (摊销时间)O(1)在中间/开始添加元素O(n)O(1)删除元素(一般)O(n)O(1)内存开销较小 (只存数据)较大 (数据 两个引用)
3. 源码分析
ArrayList 源码关键部分
public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable {transient Object[] elementData; // 存储数据private void ensureCapacityInternal(int minCapacity) {if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity Math.max(DEFAULT_CAPACITY, minCapacity);}if (minCapacity - elementData.length 0) {grow(minCapacity);}}private void grow(int minCapacity) {// 扩容逻辑}public E get(int index) {rangeCheck(index);return elementData[index];}public boolean add(E e) {ensureCapacityInternal(size 1); // 确保容量elementData[size] e;return true;}// ...省略其他方法
}ArrayList的核心是一个数组。当添加元素会超过当前数组大小时会触发一个“扩容”操作通常是将数组大小增加到当前大小的1.5倍。
LinkedList 源码关键部分
public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable {transient NodeE first;transient NodeE last;private static class NodeE {E item;NodeE next;NodeE prev;Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}}public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {final NodeE l last;final NodeE newNode new Node(l, e, null);last newNode;if (l null)first newNode;elsel.next newNode;size;modCount;}// ...省略其他方法
}LinkedList中的每个元素都是一个节点对象包含了数据和两个指向其它节点的引用。
4. 代码演示
以下代码展示了ArrayList和LinkedList的基本使用
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class ListExample {public static void main(String[] args) {ListString arrayList new ArrayList();ListString linkedList new LinkedList();// 添加元素arrayList.add(Element1);linkedList.add(Element1);// 在列表中间插入元素arrayList.add(0, Element2); // O(n)linkedList.add(0, Element2); // O(1), 只需要改变引用// 获取元素String elementFromArrayList arrayList.get(1); // O(1)String elementFromLinkedList linkedList.get(1); // O(n), 需要从头遍历链表// 删除元素arrayList.remove(0); // O(n)linkedList.remove(0); // O(1), 只需要改变引用}
}5. 细节和使用场景 ArrayList 优先选择当需要频繁访问列表中的元素。注意处理扩容操作可能会导致短暂的性能下降。更低的内存占用。 LinkedList 当需要频繁进行添加和删除操作尤其是在列表的开头或中间时可以考虑使用。每个元素占用更多内存因为存储了两个额外的引用。
理解这些区别和细节可以帮助你做出适合你应用场景的数据结构选择。尽管LinkedList在某些操作中有其优势但由于内存使用和大多数操作中的性能影响ArrayList通常是默认首选。只有在特定的、频繁进行插入和删除的场景下LinkedList才是更好的选择。
