Java中的List: 理解与实践

news/2025/3/14 23:47:03/

在Java编程语言中，List是一种被广泛使用的集合类型，它提供了一种灵活的方式来存储和操作有序的元素序列。List是Java集合框架（Java Collections Framework）的一部分，是一个接口，提供了一系列标准的方法来对元素进行增加、删除、检索和遍历操作。

List的核心特性

  • 有序性：List中的元素按照插入的顺序进行存储，可以通过元素的索引（位置）来访问它们。
  • 元素唯一性：List允许添加重复的元素，即两个或更多的元素可以有相同的值。
  • 动态扩展：列表的大小不是固定的，它可以根据需要动态地增加或减少元素。

List的实现类

ArrayList

基于动态数组实现，默认初始容量是10，动态数组允许元素的随机访问，即可以通过索引直接访问任何位置的元素。

动态数组（Dynamic Array）是一个可以根据需要进行自动扩容的数据结构。与普通数组相同。然而，与传统的数组（其大小在创建时固定）不同，动态数组在添加更多元素时可以自动地扩大其容量。

  1. 随机访问：动态数组支持快速的随机访问，这意味着可以在常数时间内访问任何索引的元素，即时间复杂度为O(1)。

  2. 自动扩容：当数组中的元素填满所有可用空间时，动态数组可以自动进行扩容以适应更多的元素。这通常涉及以下步骤：

    • 创建一个更大的新数组（通常是旧数组大小的两倍）。
    • 将旧数组中的所有元素复制到新数组中。
    • 释放旧数组，并将引用指向新数组。

  3. 添加/删除元素：向动态数组添加元素通常是一个快速的操作，特别是在数组的末尾添加。但是，如果数组已经满了，那么添加操作需要进行一次扩容，这将涉及到额外的内存分配和元素复制。平均而言，添加操作的时间复杂度是O(1)，但在最坏情况下会是O(n)。删除元素也是一种支持的操作，但可能涉及到移动元素以填补被删除元素留下的空隙。

  4. 内存利用率：由于动态数组可能会在其容量达到上限之前就进行扩容，它可能不会始终使用所有分配的内存。这意味着它可能在某些时候会有额外的空间开销。

ArrayList扩容过程的基本步骤：

  1. 检查容量：每次添加元素时，ArrayList都会检查内部数组是否足够大，可以容纳新的元素。如果不够大，那么就需要进行扩容。
  2. 计算新容量：ArrayList计算新数组的大小。新容量的计算方式可能依赖于具体的实现，但通常是当前数组容量的1.5到2倍。在OpenJDK中，它是旧容量的1.5倍（即旧容量加上旧容量右移一位，newCapacity = oldCapacity + (oldCapacity >> 1)）。
  3. 创建新数组：ArrayList创建一个新的更大的数组，大小为计算出的新容量。
  4. 复制元素：将原有数组中的所有元素复制到新数组中。这通常使用System.arraycopy()方法实现，它是一个原生方法，可以快速地将数据从一个数组复制到另一个数组。
  5. 更新引用：ArrayList将内部数组的引用更新为新数组。
  6. 添加新元素：现在新数组已经有足够的空间，ArrayList将新元素添加到数组中。

模拟ArrayList扩容过程的简化代码示例：

public static void main(String[] args) {// 假定初始容量为5，仅为示例Object[] elements = new Object[5];int size = 0; // ArrayList的当前元素数量// 添加元素，模拟添加过程中的扩容for (int i = 0; i < 10; i++) { // 添加10个元素，超出初始容量if (size == elements.length) {// 计算新容量：旧容量 + 旧容量的一半int newCapacity = elements.length + (elements.length >> 1);// 创建新数组elements = Arrays.copyOf(elements, newCapacity);}// 添加新元素elements[size++] = "Element " + i; }System.out.println(Arrays.toString(elements));
}

LinkedList

基于双向链表实现，没有固定大小的内部数组，提供了优秀的顺序访问和中间插入/删除操作的性能。

双向链表（Doubly Linked List）是一种数据结构，它由一系列节点（Node）组成，每个节点包含数据以及两个指针，分别指向前一个节点和后一个节点。这种结构允许双向遍历，即可以从头节点遍历到尾节点，也可以从尾节点遍历到头节点。

每个节点通常包含以下部分：

  1. 数据（Data）：存储的元素或值。
  2. 前驱指针（Prev）：指向链表中上一个节点的指针。
  3. 后继指针（Next）：指向链表中下一个节点的指针。

双向链表的第一个节点称为头节点（Head），最后一个节点称为尾节点（Tail）。在双向链表的头节点中，前驱指针通常指向 null，表示没有前一个节点。同样，在尾节点中，后继指针指向 null，表示没有下一个节点。

双向链表的优势在于它可以轻松地向两个方向遍历，并且在链表中间插入或删除节点时，可以更高效地进行，因为可以直接访问任何节点的前驱和后继。这在单向链表中需要更多的步骤，因为你只能从头节点开始按顺序遍历。

双向链表的简单实现：

public class DoublyLinkedListNode<T> {T data;DoublyLinkedListNode<T> prev;DoublyLinkedListNode<T> next;public DoublyLinkedListNode(T data) {this.data = data;this.prev = null;this.next = null;}
}

public class DoublyLinkedList<T> {private DoublyLinkedListNode<T> head;private DoublyLinkedListNode<T> tail;public DoublyLinkedList() {head = null;tail = null;}// 在链表尾部添加节点public void append(T data) {DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(data);// 链表为空if (tail == null) { head = newNode;tail = newNode;} else {tail.next = newNode;newNode.prev = tail;tail = newNode;}}// 在链表头部添加节点public void prepend(T data) {DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(data);// 链表为空if (head == null) { head = newNode;tail = newNode;} else {newNode.next = head;head.prev = newNode;head = newNode;}}}

双向链表相对于数组和单向链表来说，在插入和删除节点时可能更加高效，因为不需要重新排列整个数据结构。然而，它也具有额外的内存开销，因为每个节点都包含两个额外的指针。在实际的软件开发中，选择哪种数据结构取决于具体的应用场景和性能需求。

单向链表（Singly Linked List）是一种线性数据结构，由一系列节点（Node）组成，每个节点包含两部分：数据域和指向下一个节点的指针。这种结构允许顺序访问其元素，从头节点（Head）开始，一直到尾节点（Tail）结束。尾节点的指针指向 null，标记着链表的结束。

每个节点通常包含以下部分：

  1. 数据（Data）：存储的元素或值。
  2. 指针（Next）：指向链表中下一个节点的指针。

单向链表的头节点是链表的起点，它是访问链表中其他节点的入口。在单向链表中，由于每个节点只包含指向下一个节点的指针，所以你不能直接反向遍历，只能从头节点开始，按顺序向后遍历。

单向链表的简单实现：

public class SinglyLinkedListNode<T> {T data;SinglyLinkedListNode<T> next;public SinglyLinkedListNode(T data) {this.data = data;this.next = null;}
}

public class SinglyLinkedList<T> {private SinglyLinkedListNode<T> head;public SinglyLinkedList() {this.head = null;}// 在链表的末尾添加一个新的节点public void append(T data) {if (head == null) {head = new SinglyLinkedListNode<>(data);return;}SinglyLinkedListNode<T> current = head;while (current.next != null) {current = current.next;}current.next = new SinglyLinkedListNode<>(data);}// 在链表头部添加一个新的节点public void prepend(T data) {SinglyLinkedListNode<T> newHead = new SinglyLinkedListNode<>(data);newHead.next = head;head = newHead;}// 删除具有特定值的节点public void remove(T data) {if (head == null) return;if (head.data.equals(data)) {head = head.next;return;}SinglyLinkedListNode<T> current = head;while (current.next != null) {if (current.next.data.equals(data)) {current.next = current.next.next;return;}current = current.next;}}}

Vector

和ArrayList类似，默认初始容量是10，也会在需要时自动增长其容量，但是它是线程安全的。

每种实现都有其特定的使用场景。如果你需要频繁的随机访问元素，那么ArrayList将是最合适的，因为它提供了优秀的随机访问性能。但是，如果你需要在List中插入和删除元素，特别是在List的开头或中间，LinkedList会更加适合，因为它的插入和删除操作不需要像数组那样进行大量的元素移动。

List的基本操作

  • add(E e)：将指定的元素添加到列表的末尾。
  • add(int index, E element)：在列表的指定位置插入指定元素。
  • remove(Object o)：移除列表中首次出现的指定元素（如果存在）。
  • remove(int index)：移除列表中指定位置的元素。
  • get(int index)：返回列表中指定位置的元素。
  • set(int index, E element)：用指定元素替换列表中指定位置的元素。
  • size()：返回列表中的元素个数。
  • isEmpty()：如果列表不包含元素，则返回true。
  • contains(Object o)：如果列表包含指定元素，则返回true。
  • clear()：移除列表中的所有元素。

List的迭代

  • 使用传统的for循环通过索引访问。
  • 使用增强的for-each循环进行迭代。
  • 使用迭代器（Iterator）。

List的线程安全问题

在多线程环境中使用List时，开发者需要注意线程安全的问题。ArrayList和LinkedList并不是线程安全的，如果需要在多线程环境下访问和修改List，可以考虑使用Vector或者Collections.synchronizedList方法来包装非线程安全的List：

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;public class SynchronizedListExample {public static void main(String[] args) {// 创建一个同步的ListList<String> syncList = Collections.synchronizedList(new ArrayList<>());// 添加元素syncList.add("Synchronized");syncList.add("List");// 访问元素需要同步块synchronized (syncList) {for (String item : syncList) {System.out.println(item);}}}}

然而，在高并发场景下，Vector和Collections.synchronizedList的性能可能不是最优的。在这种情况下，可以考虑使用CopyOnWriteArrayList，它是java.util.concurrent包提供的一个线程安全的List实现，它通过在修改操作（如add、set）时创建底层数组的副本来实现线程安全。

CopyOnWriteArrayList的核心思想是，每当对列表进行修改操作（添加、设置或删除元素）时，它都会创建并使用内部数组的一个新副本。因此，任何写入操作都不会影响到原始数组，从而保证了迭代器不会看到这些变化，避免了并发修改异常。

这里是CopyOnWriteArrayList的一些主要特点：

  1. 线程安全：CopyOnWriteArrayList内的所有可变操作（add、set、remove等）都是通过创建内部数组的新副本来实现的，从而避免了线程间的冲突。
  2. 读写分离：读操作（如get、iterator、size等）是在原有数组的基础上进行的，而写操作则在复制的新数组上执行。这种机制称为“写时复制”（Copy-on-Write）。
  3. 迭代器一致性：迭代器返回的是写操作发生时的数组快照。因此，在迭代器创建之后的写操作不会反映在迭代器上，保证了迭代器不会抛出ConcurrentModificationException。迭代器也不支持修改操作，remove、set和add方法会抛出UnsupportedOperationException。
  4. 内存和性能考虑：由于每次修改都涉及创建数组的副本，对于大的列表或频繁修改的情况，CopyOnWriteArrayList可能会带来显著的内存和性能开销。
  5. 适用场景：CopyOnWriteArrayList适合于列表大小相对固定，但需要在多线程环境中经常遍历、读取和枚举的应用场景。如果列表经常发生变化，或者列表非常大，使用CopyOnWriteArrayList可能不是最好的选择。
import java.util.concurrent.CopyOnWriteArrayList;public class CopyOnWriteArrayListExample {public static void main(String[] args) {CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();list.add("Element 1");list.add("Element 2");list.add("Element 3");// 创建一个迭代器，它不会反映在迭代过程中加入的新元素for (String element : list) {System.out.println(element);// 这里的添加操作不会影响迭代器list.add("Element 4");}// 最终列表的内容System.out.println("Final list: " + list);}
}

尽管在迭代过程中向CopyOnWriteArrayList添加了新元素，迭代器仍然只会遍历开始迭代时列表的原始内容。最终的输出将包括新添加的元素。

List的高级用法

除了基本操作，List还提供了一系列高级操作，如排序、查找和转换等。

  • 排序：可以使用Collections.sort方法对List进行排序。
  • 查找：可以使用Collections.binarySearch方法在已排序的List中快速查找元素。
  • 转换：可以使用toArray方法将List转换为数组，或者使用stream方法进行更复杂的数据转换和操作。
// 对List进行排序
Collections.sort(fruits);// 使用二分查找法查找元素
int index = Collections.binarySearch(fruits, "Cherry");// 将List转换为数组
String[] fruitsArray = fruits.toArray(new String[0]);// 使用Stream API进行过滤
List<String> filteredFruits = fruits.stream().filter(f -> f.startsWith("A")).collect(Collectors.toList());

List与Java 8的流

Java 8引入了流（Streams），这为在List上进行复杂的查询和转换操作提供了新的可能性。你可以使用流来执行过滤、映射、排序和其他聚合操作，通常配合lambda表达式使用。

使用流的一个例子：

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;public class StreamListExample {public static void main(String[] args) {// 创建一个List实例List<String> items = new ArrayList<>();items.add("One");items.add("Two");items.add("Three");// 使用流过滤和输出元素List<String> filteredItems = items.stream().filter(s -> s.contains("T")).collect(Collectors.toList());System.out.println("Filtered Items:");filteredItems.forEach(System.out::println);}}

性能考量

在决定使用哪种List实现之前，需要考虑以下几个性能相关的因素：

  • 随机访问：如果你需要频繁地通过索引访问元素，ArrayList通常是更好的选择，因为它提供常数时间复杂度的随机访问能力。
  • 插入和删除：如果你的应用场景中经常在List中间插入或删除元素，LinkedList可能会提供更好的性能，因为它只需要改变节点的指针。
  • 内存占用：ArrayList可能会预留一些空间以减少扩容操作的频率，这可能导致一定程度的内存浪费。相比之下，LinkedList对于每个元素都需要额外的内存来维护节点之间的链接。
  • 线程安全：如果在多线程环境中使用List，应该考虑线程安全的问题。Vector是同步的，但是通常建议使用Collections.synchronizedList或CopyOnWriteArrayList来获得线程安全的List。

常见问题

  • List是否可以存储基本数据类型？：List不能存储基本数据类型，例如int、char等，但可以存储它们的包装类，如Integer、Character等。

  • 如何将List转换为数组？：可以使用toArray()方法将List转换为数组。

    import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;public class ListStreamExample {public static void main(String[] args) {List<String> fruits = Arrays.asList("Apple", "Banana", "Cherry", "Apricot");// 使用Stream API对List进行过滤和转换List<String> filteredFruits = fruits.stream().filter(f -> f.startsWith("A")) // 过滤出以"A"开头的水果.sorted() // 按自然顺序排序.collect(Collectors.toList()); // 收集为ListSystem.out.println("Filtered and Sorted Fruits: " + filteredFruits);}}

  • 并发修改异常（ConcurrentModificationException）: 当尝试在遍历List的过程中改变其结构（例如添加或删除元素）时，可能会抛出ConcurrentModificationException。要避免这个问题，可以使用迭代器的remove()方法来删除元素，或者采用Java 8及以上版本的新特性，如removeIf()方法。对于并发环境，可以考虑使用线程安全的集合类型，如CopyOnWriteArrayList。

  • 类型安全问题: 自Java 5起，Java引入了泛型，使得可以创建特定类型的List（例如List<String>）。尽量避免使用原始类型（raw types），如简单的List，因为这会导致类型转换问题和运行时错误。

  • 忘记使用泛型: 始终使用泛型来声明和初始化List，这有助于编译时类型检查，并减少在运行时出现ClassCastException的风险。

  • 使用不当的equals和hashCode: 当使用包含自定义对象的List时，确保正确重写这些对象的equals()和hashCode()方法，这对于列表的搜索和去重操作至关重要。

  • 不正确的遍历和删除: 在for循环中遍历并删除元素可能导致跳过某些元素或抛出ConcurrentModificationException。使用迭代器或Java 8的removeIf方法可以安全地删除元素。

手写ArrayList

import java.util.Arrays;public abstract class SimpleArrayList<E> implements java.util.List<E> {/*** 默认的初始容量*/private static final int DEFAULT_CAPACITY = 10;/*** 内部用来存储元素的数组*/private Object[] elements;/*** 列表的当前元素数量*/private int size;public SimpleArrayList() {// 初始化内部数组elements = new Object[DEFAULT_CAPACITY];}// 确保内部数组有足够的容量来存储新元素private void ensureCapacity() {if (size >= elements.length) {// 如果当前元素数量达到数组容量，需要扩容// 通常扩展到旧容量的1.5倍int newCapacity = elements.length + (elements.length >> 1);// 复制旧数组元素到新的扩容后的数组elements = Arrays.copyOf(elements, newCapacity);}}@Overridepublic boolean add(E e) {// 确保有足够容量添加新元素ensureCapacity();// 将元素添加到数组末尾，并递增大小elements[size++] = e;  return true;}@Overridepublic E get(int index) {// 检查索引范围if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}// 返回请求索引处的元素return (E) elements[index];  }@Overridepublic E remove(int index) {// 保存要删除的元素E oldValue = get(index);// 计算要移动的元素数目int numMoved = size - index - 1;  if (numMoved > 0) {// 将删除元素后的所有元素向前移动一个位置System.arraycopy(elements, index + 1, elements, index, numMoved);}// 清除引用并递减大小elements[--size] = null;// 返回被删除的元素return oldValue;  }@Overridepublic int size() {// 返回列表当前元素数量return size; }// ... 其他 List 接口方法的实现(略)@Overridepublic boolean isEmpty() {return size == 0;}// ... 实现 Comparable, Serializable 等接口和方法(略)
}

http://www.ppmy.cn/news/1294965.html

相关文章

阿里云系统盘测评ESSD、SSD和高效云盘IOPS、吞吐量性能参数表

阿里云系统盘测评ESSD、SSD和高效云盘IOPS、吞吐量性能参数表

阿里云服务器系统盘或数据盘支持多种云盘类型&#xff0c;如高效云盘、ESSD Entry云盘、SSD云盘、ESSD云盘、ESSD PL-X云盘及ESSD AutoPL云盘等&#xff0c;阿里云百科aliyunbaike.com详细介绍不同云盘说明及单盘容量、最大/最小IOPS、最大/最小吞吐量、单路随机写平均时延等性…
阅读更多...
原型和原型链剖析

原型和原型链剖析

原型 每一个函数都有一个属性&#xff0c;这个属性名就叫做prototype prototype的属性值是一个对象 原型它就是函数的一个prototype属性 这个函数的prototype属性里面有什么&#xff0c;它可以干什么 默认的prototype对象里面有一个constructor属性&#xff0c;这个constructor…
阅读更多...
第1章 图片与初用OpenCV

第1章 图片与初用OpenCV

在本章&#xff0c;初步介绍OpenCV的一些基本操作&#xff0c;例如图片的读取以及图片格式的转换。1图片在计算机中的几种存储形式2图片的读取和延时操作3图片的各种输出形式1.1 图片在计算机中的存储形式 即使我们对图片在计算机中的存储格式不是很清楚&#xff0c;也知道图片…
阅读更多...
Hive实战：网址去重

Hive实战：网址去重

文章目录 一、实战概述二、提出任务三、完成任务&#xff08;一&#xff09;准备数据1、在虚拟机上创建文本文件2、上传文件到HDFS指定目录 &#xff08;二&#xff09;实现步骤1、启动Hive Metastore服务2、启动Hive客户端3、基于HDFS数据文件创建Hive外部表4、利用Hive SQL实…
阅读更多...
Windows 搭建ninja 编译c++的环境

Windows 搭建ninja 编译c++的环境

1. 系统安装python, 测试版本为&#xff08;3.7.0&#xff09; 2. 从官方网站获取get-pip.py https://bootstrap.pypa.io/get-pip.py 3. 安装pip python get-pip.py 4. 安装ninja pip install ninja 5. 准备CMakeLists.txt cmake_minimum_required(VERSION 3.22) proje…
阅读更多...
Mybatis-Plus乐观锁配置使用流程【OptimisticLockerInnerInterceptor】

Mybatis-Plus乐观锁配置使用流程【OptimisticLockerInnerInterceptor】

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家:人工智能学习网站 1.乐观锁实现 1.配置插件 1.XML方式 <bean class"com.baomidou.mybatisplus.extension.plugins.inner.OptimisticLockerInnerI…
阅读更多...
C++学习笔记 ——this指针+对象数组

C++学习笔记 ——this指针+对象数组

目录 一、Cthis指针 二、this指针的一个案列 三、对象数组 四、对象数组代码案列详解 一、Cthis指针 C中的this指针是一个特殊的指针&#xff0c;它指向当前对象的地址。在类中的成员函数中&#xff0c;this指针可以用来访问当前对象的成员变量和成员函数。 当我们调用一…
阅读更多...
PyQT5+MySQL的学生信息管理系统【附源码，运行简单】

PyQT5+MySQL的学生信息管理系统【附源码，运行简单】

PyQT5MySQL的学生信息管理系统【附源码&#xff0c;运行简单】 总览 1、《PyQT5MySQL的学生信息管理系统》1.1 方案设计说明书设计目标需求分析工具列表 2、详细设计2.1 登录2.2 程序主页面2.3 学生新增界面2.4 学生更改界面2.4 学生删除界面2.5 其他功能贴图 3、下载 总览 自…
阅读更多...
最新文章

Copyright @ 2022~2023