滚雪球学Java(57):解密Java中List接口底层实现原理

简介: 【6月更文挑战第11天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!

在这里插入图片描述

  咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE相关知识点了,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~

在这里插入图片描述


🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!

环境说明:Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

@[toc]

前言

  Java是一种广泛应用的编程语言,被广泛应用于各种平台和应用领域。List接口是Java中最重要的数据结构之一,它为我们提供了一种灵活、高效、可扩展的数据结构。

  当我们使用List接口时,我们经常需要了解它的底层实现原理,以便对其进行优化和调试。因此,本篇文章将深入研究Java中List接口的底层实现原理,帮助读者更好地理解List接口的使用和优化。

摘要

  本篇文章将首先介绍Java中List接口的基本特性和使用方法,然后深入研究List接口的底层实现原理,包括ArrayList和LinkedList两种实现方式。接着,我们将讨论List接口的应用场景和优缺点,并提供一些常用的测试用例和总结。

List

概述

  List是Java中最常用的数据结构之一。它提供了一种有序集合,可以按照添加的顺序进行访问,并且允许重复元素。

  Java中的List接口是一个标准接口,定义了一系列方法,可以用于访问和操作List中的数据。List接口有多种实现方法,每种实现方法都有不同的优缺点。

  在下面的章节中,我们将重点讲解Java中List接口的两种主要实现方式:ArrayList和LinkedList。

源代码解析

ArrayList

  ArrayList是Java中常用的数组实现方式。它使用一个数组来保存List中的元素,支持动态扩展。

  ArrayList的源代码可以在Java SDK中的java.util包中找到,其主要方法包括:

public boolean add(E e);
public E get(int index);
public int size();
public boolean isEmpty();
public boolean contains(Object o);
public int indexOf(Object o);
public E remove(int index);
public E set(int index, E element);

在这里插入图片描述

  这些方法可以用于添加、获取、删除和修改List中的元素。

  在ArrayList中,数组的默认大小为10,当元素个数超出数组大小时,会自动扩展数组的容量,以便可以继续添加元素。例如:

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
   
   
    list.add(i);
}

  在上面的例子中,我们用ArrayList保存了100个整数。由于ArrayList会自动扩展数组的大小,我们可以在不知道元素个数的情况下,随意添加元素。

  如下是部分源码截图:

在这里插入图片描述

LinkedList

  LinkedList是Java中另一种常用的List实现方式。它使用一个双向链表来保存List中的元素。每个元素节点都包含一个指向前一个元素和后一个元素的指针。

LinkedList的源代码可以在Java SDK中的java.util包中找到,其主要方法包括:

public boolean add(E e);
public E get(int index);
public int size();
public boolean isEmpty();
public boolean contains(Object o);
public int indexOf(Object o);
public E remove(int index);
public E set(int index, E element);
public void addFirst(E e);
public void addLast(E e);
public E getFirst();
public E getLast();
public E removeFirst();
public E removeLast();

LinkedList的节点结构如下所示:

   +------+    +------+    +------+  
--->| prev |<---| data |--->| next |---
   +------+    +------+    +------+

  在LinkedList中,每个节点包含一个数据项和两个指针,一个指向前一个元素,一个指向后一个元素。这种双向链表的结构,使得LinkedList可以支持快速添加和删除元素。

下面的代码演示了如何使用LinkedList:

List<Integer> list = new LinkedList<>();
for (int i = 0; i < 100; i++) {
   
   
    list.add(i);
}

  在上面的例子中,我们同样用LinkedList保存了100个整数。由于LinkedList使用链表结构,它可以快速添加和删除元素,因此在某些场景下,它可能比ArrayList更加适用。

  如下是部分源码截图:

在这里插入图片描述

应用场景案例

List接口的应用场景非常广泛,可以用于各种数据处理和存储场景。

ArrayList

  ArrayList适用于需要在List中快速访问元素的场景。由于ArrayList使用数组来存储元素,可以通过下标访问和修改元素,因此在需要频繁读取和修改List中元素的场景中,ArrayList是一种很好的选择。

  另外,由于ArrayList支持动态扩展数组大小,因此在不知道元素个数的情况下,也可以用ArrayList来保存元素。

LinkedList

  LinkedList适用于需要在List中快速添加和删除元素的场景。由于LinkedList使用链表结构来存储元素,可以快速添加和删除元素,因此在需要频繁添加和删除元素的场景中,LinkedList是一种很好的选择。

  另外,由于LinkedList支持在链表头和尾部添加和删除元素的方法,因此在需要快速访问第一个和最后一个元素的场景中,LinkedList也是一种很好的选择。

在这里插入图片描述

优缺点分析

ArrayList

优点:

  1. 由于ArrayList使用数组来存储元素,可以通过下标访问和修改元素。因此在需要频繁读取和修改List中元素的场景中,ArrayList是一种很好的选择。
  2. ArrayList支持动态扩展数组大小,因此在不知道元素个数的情况下,也可以用ArrayList来保存元素。

缺点:

  1. 当元素个数超过数组大小时,ArrayList会自动扩展数组的容量,这会导致一定的性能损失。
  2. 由于数组在内存中是连续的,因此在插入和删除元素时,需要移动数组中的其他元素,这会导致一定的时间复杂度。

LinkedList

优点:

  1. 由于LinkedList使用链表结构来存储元素,可以快速添加和删除元素。因此在需要频繁添加和删除元素的场景中,LinkedList是一种很好的选择。
  2. LinkedList支持在链表头和尾部添加和删除元素的方法,因此在需要快速访问第一个和最后一个元素的场景中,LinkedList也是一种很好的选择。

缺点:

  1. 由于LinkedList使用链表结构来存储元素,无法通过下标访问和修改元素。因此在需要频繁读取和修改元素的场景中,LinkedList可能不是最优选择。
  2. 在需要访问中间元素时,LinkedList的访问性能较差,因为需要从链表头或尾遍历到目标元素。

类代码方法介绍

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
   
   
    public ArrayList();
    public ArrayList(int initialCapacity);
    public ArrayList(Collection<? extends E> c);
    public void trimToSize();
    public void ensureCapacity(int minCapacity);
    public int size();
    public boolean isEmpty();
    public boolean contains(Object o);
    public int indexOf(Object o);
    public int lastIndexOf(Object o);
    public Object clone();
    public Object[] toArray();
    public <T> T[] toArray(T[] a);
    public E get(int index);
    public E set(int index, E element);
    public boolean add(E e);
    public void add(int index, E element);
    public E remove(int index);
    public boolean remove(Object o);
    public void clear();
    public boolean addAll(Collection<? extends E> c);
    public boolean addAll(int index, Collection<? extends E> c);
}

代码分析

  该代码展示了 Java 中 ArrayList 类的方法声明。ArrayList 类实现了 List 接口,是一个可变大小的数组实现,支持随机访问和快速插入和删除元素。其中,包含以下主要方法:

  • 构造方法:默认构造方法、指定初始容量的构造方法、从 Collection 中构造方法。
  • 容量操作方法:trimToSize(),确保该 ArrayList 实例的容量最小。
  • 容量增长方法:ensureCapacity(int minCapacity),调整该 ArrayList 实例的容量,以确保它最少能容纳指定最小容量的元素。
  • 查询方法:size(),返回列表中元素的数量;isEmpty(),如果列表为空,则返回 true;contains(Object o),如果此列表中包含指定元素,则返回 true;indexOf(Object o),返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回 -1;lastIndexOf(Object o),返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回 -1。
  • 元素操作方法:get(int index),返回列表中指定位置的元素;set(int index, E element),用指定元素替换此列表中指定位置上的元素,并返回替换前的元素;add(E e),将指定元素追加到此列表的末尾;add(int index, E element),在列表的指定位置插入指定元素;remove(int index),删除列表中指定位置的元素,并返回被删除的元素;remove(Object o),从此列表中删除指定元素的第一个出现(如果存在);clear(),从列表中移除所有元素。
  • 其他方法:clone(),返回此 ArrayList 实例的副本;toArray(),返回一个包含此列表中所有元素的数组;toArray(T[] a),返回一个包含此列表中所有元素的数组,数组类型为指定数组的运行时类型;addAll(Collection<? extends E> c),将指定集合中的所有元素添加到列表的末尾;addAll(int index, Collection<? extends E> c),在列表的指定位置插入指定的集合中的所有元素。

  这些方法使得 ArrayList 可以高效地进行常见的列表操作,例如添加、删除和搜索元素。

LinkedList

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
   
   
    public LinkedList();
    public LinkedList(Collection<? extends E> c);
    public int size();
    public boolean isEmpty();
    public boolean contains(Object o);
    public Iterator<E> iterator();
    public Iterator<E> descendingIterator();
    public boolean add(E e);
    public boolean remove(Object o);
    public void clear();
    public E get(int index);
    public E set(int index, E element);
    public void add(int index, E element);
    public E remove(int index);
    public boolean addAll(Collection<? extends E> c);
    public boolean addAll(int index, Collection<? extends E> c);
    public boolean removeAll(Collection<?> c);
    public boolean retainAll(Collection<?> c);
    public E getFirst();
    public E getLast();
    public E removeFirst();
    public E removeLast();
    public void addFirst(E e);
    public void addLast(E e);
    public boolean offer(E e);
    public boolean offerFirst(E e);
    public boolean offerLast(E e);
    public E peek();
    public E peekFirst();
    public E peekLast();
    public E poll();
    public E pollFirst();
    public E pollLast();
    public E element();
    public void push(E e);
    public E pop();
    public boolean removeFirstOccurrence(Object o);
    public boolean removeLastOccurrence(Object o);
    public Object[] toArray();
    public <T> T[] toArray(T[] a);
    private Entry<E> addBefore(E e, Entry<E> entry);
    private E remove(Entry<E> e);
    private Entry<E> entry(int index);
    private void linkFirst(E e);
    private void linkLast(E e);
    private void linkBefore(E e, Entry<E> succ);
    private E unlinkFirst(Entry<E> f);
    private E unlinkLast(Entry<E> l);
    E unlink(Entry<E> e);
    private static class Entry<E> {
   
   
        E element;
        Entry<E> next;
        Entry<E> previous;
        Entry(E element, Entry<E> next, Entry<E> previous) {
   
   
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
    }
}

  LinkedList实现了List、Deque和Cloneable等接口,提供了一些常用方法,如add、remove、get和set等。同时,LinkedList还提供了一些与双向链表相关的方法,如linkFirst、linkLast、linkBefore、unlinkFirst和unlinkLast等。

代码分析

  这是一个泛型的双向链表实现,实现了 List、Deque 接口,并继承了 AbstractSequentialList 抽象类。其中包含了链表的基本操作,如添加、移除、查询元素等等。同时还包含了一些特殊的操作,如获取头尾元素、在头尾添加元素、弹出元素等。内部使用了 Entry 类来表示链表节点,其中包含了元素、前驱节点和后继节点。同时还实现了一些私有方法来辅助链表的操作。

测试用例

测试代码演示

以下是一个简单的测试用例:

package com.demo.javase.day56.collection;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author bug菌
 * @Date 2023-11-05 23:32
 */
public class ListTest {
   
   
        public static void main(String[] args) {
   
   
            // 创建一个列表
            List<String> list = new ArrayList<>();

            // 添加元素到列表
            list.add("A");
            list.add("B");
            list.add("C");

            // 输出列表长度
            System.out.println("Size of list: " + list.size());

            // 输出列表中的元素
            System.out.println("List contents: ");
            for (String s : list) {
   
   
                System.out.println(s);
            }

            // 删除第一个元素
            list.remove(0);

            // 输出修改后的列表中的元素
            System.out.println("List contents after removing first element: ");
            for (String s : list) {
   
   
                System.out.println(s);
            }

            // 判断列表中是否包含指定元素
            if (list.contains("A")) {
   
   
                System.out.println("List contains A");
            } else {
   
   
                System.out.println("List does not contain A");
            }

            // 清空列表
            list.clear();

            // 输出清空后的列表长度
            System.out.println("Size of list after clearing: " + list.size());
        }

}

此测试用例演示了如何创建List对象,添加元素,删除元素,检查列表是否包含特定元素以及清空列表。

测试结果

  根据如上测试用例,本地测试结果如下,仅供参考,你们也可以自行修改测试用例或者添加更多的测试数据或测试方法,进行熟练学习以此加深理解。

在这里插入图片描述

测试代码分析

  根据如上测试用例,在此我给大家进行深入详细的解读一下测试代码,以便于更多的同学能够理解并加深印象。

  如上测试用例介绍了Java中List(列表)的基本用法。List可以存储一组有序的元素,在添加、删除、修改和查询元素时非常方便。可以使用ArrayList实现List接口。常用的方法包括add()、remove()、contains()和clear()。在使用List时,可以通过迭代器或者for循环遍历列表中的元素。需要注意的是,在删除元素时可能会导致元素位置变化,因此在迭代器中删除元素时必须使用iterator.remove()方法,否则会抛出ConcurrentModificationException异常。

小结

  本篇文章对Java中List接口的底层实现原理进行了探讨,介绍了ArrayList和LinkedList两种主要实现方式的特点和应用场景,并分析了它们的优缺点。

  在实际使用中,我们应该根据场景的不同,选择最合适的List实现方式,以达到最佳的性能和应用体验。

总结

  本篇文章介绍了Java中List接口的基本特性和使用方法,并深入研究了List接口的底层实现原理,包括ArrayList和LinkedList两种实现方式。在实际应用中,如果需要频繁读取和修改元素,可以使用ArrayList;如果需要频繁添加和删除元素,可以使用LinkedList。此外,本文还分析了它们的优缺点,提供了一些常用的测试用例和总结。

  ...
  好啦,这期的内容就基本接近尾声啦,若你想学习更多,可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》,本专栏致力打造最硬核 Java 零基础系列学习内容,🚀打造全网精品硬核专栏,带你直线超车;欢迎大家订阅持续学习。

附录源码

  如上涉及所有源码均已上传同步在「Gitee」,提供给同学们一对一参考学习,辅助你更迅速的掌握。

☀️建议/推荐你


  无论你是计算机专业的学生,还是对编程有兴趣的小伙伴,都建议直接毫无顾忌的学习此专栏「滚雪球学Java」,bug菌郑重承诺,凡是学习此专栏的同学,均能获取到所需的知识和技能,全网最快速入门Java编程,就像滚雪球一样,越滚越大,指数级提升。

  最后,如果这篇文章对你有所帮助,帮忙给作者来个一键三连,关注、点赞、收藏,您的支持就是我坚持写作最大的动力。


目录
相关文章
|
1天前
|
缓存 监控 算法
Java面试题:描述Java垃圾回收的基本原理,以及如何通过代码优化来协助垃圾回收器的工作
Java面试题:描述Java垃圾回收的基本原理,以及如何通过代码优化来协助垃圾回收器的工作
24 8
|
1天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
11 1
|
1天前
|
Java API
Java面试题:说明Lambda表达式在Java中的应用,以及函数式接口的概念和作用。
Java面试题:说明Lambda表达式在Java中的应用,以及函数式接口的概念和作用。
7 0
|
1天前
|
缓存 Java
Java面试题:描述Java中的线程池及其实现方式,详细说明其原理
Java面试题:描述Java中的线程池及其实现方式,详细说明其原理
5 0
|
2天前
|
Java 应用服务中间件 开发者
Java面试题:解释Spring Boot的优势及其自动配置原理
Java面试题:解释Spring Boot的优势及其自动配置原理
20 0
|
2天前
|
设计模式 Java
Java面试题:描述观察者模式的工作原理及其在Java中的应用。
Java面试题:描述观察者模式的工作原理及其在Java中的应用。
7 0
|
2天前
|
SQL Java 关系型数据库
Java面试题:描述JDBC的工作原理,包括连接数据库、执行SQL语句等步骤。
Java面试题:描述JDBC的工作原理,包括连接数据库、执行SQL语句等步骤。
12 0
|
2天前
|
SQL Java 数据库连接
Java面试题:简述ORM框架(如Hibernate、MyBatis)的工作原理及其优缺点。
Java面试题:简述ORM框架(如Hibernate、MyBatis)的工作原理及其优缺点。
5 0
|
2天前
|
Java 应用服务中间件 持续交付
Java面试题:简述Docker等容器化技术的原理及其在Java应用部署中的作用。
Java面试题:简述Docker等容器化技术的原理及其在Java应用部署中的作用。
9 0
|
2天前
|
网络协议 Java
Java面试题:什么是Java中的接口?与抽象类有什么区别?
Java面试题:什么是Java中的接口?与抽象类有什么区别?
7 0