List集合源码解析

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
1.List集合概述和特点
- 1.2 List集合中特有的方法【应用】
2.数据结构初步了解
- 2.1 常见数据结构
- 2.1 List集合的实现类ArrayList
3. List集合的实现类
总结

前言

本篇文章主要讲解List集合的基本使用，初步了解一些像栈、队列等的数据结构，List集合的实现子类ArrayList、LinkedList相关源码的解析，如果本文对您有帮助，请不要吝啬您的鼓励哦，你的鼓励是我继续创作的动力。

1.List集合概述和特点

List集合概述

有序集合，这里的有序指的是存取的数据。

用户可以精确控制列表中每个元素的插入位置，用户可以通过整数索引访问元素，并搜索列表中的元素。

与set集合不同，列表通常允许重复的元素
List集合的特点

存取有序

可以重复

有索引
List集合的基本使用

相关文章请阅读

集合基础

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("历史上繁华的朝代");
    list.add("唐朝");
    list.add("明朝");
    list.add("清朝");
    list.add("汉朝");
    list.add("秦朝");

    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
    System.out.println("---------------------");
    for (String s : list) {
        System.out.println(s);
    }
}

1.2 List集合中特有的方法【应用】

方法介绍

方法名	描述
void add(int index,E element)	在此集合中指定位置插入指定元素
E remove(int index)	删除指定索引处的元素，返回被删除的元素
E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

代码演示

 public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("历史上繁华的朝代");
        list.add("唐朝");
        list.add("明朝");
        list.add("清朝");
        list.add("汉朝");
        list.add("秦朝");
        //执行时需单个执行，方能得出以下相应结果
//        method1(list);
//        method2(list);
//        method3(list);
//        method4(list);
    }

/**
 * 演示获取集合中元素的方法
 * @param list
 */
private static void method4(List<String> list) {
    String s = list.get(0);
    System.out.println(s);//历史上繁华的朝代
}

/**
 * 演示set方法
 * @param list
 */
private static void method3(List<String> list) {
    String set = list.set(0, "历史上繁华的朝代>>>");
    System.out.println(set);//历史上繁华的朝代
    System.out.println(list);//[历史上繁华的朝代>>>, 唐朝, 明朝, 清朝, 汉朝, 秦朝]
}

/**
 * List集合中有两个删除方法
 * ① 删除指定元素值，返回一个Boolean值
 * ② 删除指定索引，返回被删除的元素
 * @param list
 */
private static void method2(List<String> list) {
    String removeRet = list.remove(0);
    //返回被删除的元素
    System.out.println(removeRet);//历史上繁华的朝代
    System.out.println(list);//[唐朝, 明朝, 清朝, 汉朝, 秦朝]

    list.add("秦朝");
    // 删除找到的第一个元素，返回值为是否删除成功
    boolean remove = list.remove("秦朝");
    System.out.println(remove);//true
    System.out.println(list);//[唐朝, 明朝, 清朝, 汉朝]
}

/**
 * 演示List集合添加元素
 * @param list
 */
private static void method1(List<String> list) {
    // 原来位置的元素会后移
    list.add(0,"秦朝");
    System.out.println(list);//[秦朝, 历史上繁华的朝代, 唐朝, 明朝, 清朝, 汉朝, 秦朝]
}

2.数据结构初步了解

2.1 常见数据结构

栈结构

先进后出，借助手枪弹夹来理解
队列结构

先进先出（借助排队来理解）

数据从后端进入队列模型的过程称为：入队列

数据从前端离开队列模型的过程称为：出队列
数组

查询数据时通过地址值和索引定位，查询任意数据耗时相同，查询速度快。

删除数据时，要将原始的数据删除，同时后面的数据前移，删除效率低。
链表

通过前一个节点记录后一个节点的地址值。

插入元素：

①数据B对应的笑一个数据地址指向数据C

②数组A对应的下一个数据地址执行数据B

删除元素：

①数据B对应的下一个数据地址指向数据D

②删除数据C

对于数组来说，链表是一种增删效率非常高的模型，但是查询效率低！

查询第N个元素的时候，必须从头（head）开始查询！

双向链表：要查询第几个元素的话，就会判断离头近还是离尾近，那个近就从哪里开始查询。

2.1 List集合的实现类ArrayList

ArrayList：底层数据结构是数组，查询快，增删慢
源码解析

List list = new ArrayList<>();

transient Object[] elementData;//ArrayList在底层创建的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 空参数的构造方法创建的是一个长度为0的数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

源代码示例：

protected transient int modCount = 0;
private int size;

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

图解（往空集合中添加第一个元素时）

3. List集合的实现类

3.1 List集合子类的特点

ArrayList集合

底层是数据结构实现，查询快、增删慢。
LinkedList集合

底层是链表结构实现，查询慢，增删快。

3.2 LinkedList集合的初步使用

代码演示

public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<>();
    list.add("历史上繁华的朝代");
    list.add("唐朝");
    list.add("明朝");
    list.add("清朝");
    list.add("汉朝");
    list.add("秦朝");
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }
    System.out.println("===========");
    Iterator it = list.iterator();
    while (it.hasNext()) {
        Object s = it.next();
        System.out.println(s);
    }
    System.out.println("===========");
    for (String s : list) {
        System.out.println(s);
    }
}

3.3 LinkedList集合的特有功能

特有方法

方法名	说明
public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast(E e)	将指定的元素追加到此列表的末尾
public E getFirst()	返回此列表中的第一个元素
public E getLast()	返回此列表中最后一个元素
public E removeFirst()	从此列表中删除并返回第一个元素
public E removeLast()	从此列表中删除并返回最后一个元素

代码演示

/**
 * LinkedList集合中删除首尾元素
 * @param list
 */
private static void method4(LinkedList<String> list) {
    String s = list.removeFirst();
    String s1 = list.removeLast();
    System.out.println(s);//历史上繁华的朝代
    System.out.println(s1);//秦朝
    System.out.println(list);//[唐朝, 明朝, 清朝, 汉朝]
}

/**
 * 演示LinkedList集合中获取首尾元素值的方法
 * @param list
 */
private static void method3(LinkedList<String> list) {
    String first = list.getFirst();
    String last = list.getLast();
    System.out.println(first + "----" + last);//历史上繁华的朝代----秦朝
}

/**
 * 演示LinkedList集合中在尾添加元素
 * @param list
 */
private static void method2(LinkedList<String> list) {
    list.addLast("秦朝1");
    System.out.println(list);//[历史上繁华的朝代, 唐朝, 明朝, 清朝, 汉朝, 秦朝, 秦朝1]
}

/**
 * 演示LinkedList集合中a在头添加元素
 * @param list
 */
private static void method1(LinkedList<String> list) {
    list.addFirst("历史上繁华的朝代1");
    System.out.println(list);//[历史上繁华的朝代1, 历史上繁华的朝代, 唐朝, 明朝, 清朝, 汉朝, 秦朝]
}

3.4 LinkedList源代码解析

源代码示例

//添加方法
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
//获取源代码
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

图解

总结

希望本文对大家有所帮助，建议读者在学习时打开自己编程工具多多练习哦！大家一起学习一起进步！

原文链接：https://blog.csdn.net/weixin_45432729/article/details/128764228