Java集合ArrayList与LinkedList详解
作者：亚雷??????? 发布时间：2022-11-11 12:14:31
标签：Java,ArrayList,LinkedList
前言
对于Java程序员，可以说对于ArrayList和LinkedList可谓是十分熟悉了
对于ArrayList和LinkedList，他们都是List接口的一个实现类，并且我们知道他们的实现方式各不相同，例如ArrayList底层实现是一个数组，而LinkedList底层实现是链表，对于数组来说，插入慢但是查询快，而对于链表来说查询慢，插入快
今天我们就来分析分析他们的源码
ArrayList
我们先看一看ArrayList的类图。他继承于AbstractList，而这个类是List类的的骨架，可以说这个类是List类的基石
成员属性
/**
序列化ID
**/
private static final long serialVersionUID = 8683452581122892189L;
/**
默认容量
**/
private static final int DEFAULT_CAPACITY = 10;
/**
如果传入的容量为0，那么将使用这个空元素数组
**/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
默认空元素数组，长度为0，传入元素时会初始化为默认元素大小
**/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
真正存储数据的数组
**/
transient Object[] elementData;
/**
列表中元素的个数
**/
private int size;
这里需要主要关注的成员属性为size和elementData，一个是元素个数，一个是真正存储数据的数组
构造函数
/**
指定数组长度构造
**/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
空参构造
**/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
传入一个集合，将该集合的元素初始化到ArrayList种
**/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
扩容机制
我们知道ArrayList是一个动态数组，但是他的底层实现是一个数组，那他是怎样保证动态的呢？
ArrayList每次添加元素之前，都会检查添加元素后的元素个数是否超过数组长度，如果超出，那么就会进行扩容，而数组扩容通过一个公开的方法实现，我们也可以手动进行扩容
public void ensureCapacity(int minCapacity) {
//判断数组是否等于默认空数组，不等于则给minExpand赋值为10
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0 : DEFAULT_CAPACITY;
//判断参数是否大于minExpand大于的时候才会去扩容
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//记录数组修改次数 + 1
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//真正扩容的方法
private void grow(int minCapacity) {
//获取原来的容量
int oldCapacity = elementData.length;
//计算新容量，新容量大小 = 旧容量大小的1.5倍
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);
}
我们可以发现每次扩容，ArrayList都会扩容1.5倍，通过位运算完成计算扩容大小的，我们知道，扩容之后进行数据迁移这个操作是很费时间的，比如我们有10w条数据，这样的话，进行数据迁移的时候，我们会耗费很长时间，所以我们建议再初始化的时候就定义一个容量，这样可以让ArrayList的效率提高很多
add方法
//添加元素到尾部
public boolean add(E e) {
//检查是否需要扩容
ensureCapacityInternal(size + 1);
//将元素添加到数组末尾，并把size++
elementData[size++] = e;
return true;
}
//添加元素到指定索引
public void add(int index, E element) {
//检查index是否越界
rangeCheckForAdd(index);
//检查是否需要扩容
ensureCapacityInternal(size + 1);
//将index以及之后的元素向后挪动一位
//这样index就能添加元素了
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//添加元素到index的位置
elementData[index] = element;
size++;
}
//将集合c的元素添加到list中
public boolean addAll(Collection<? extends E> c) {
//把c转换为数组
Object[] a = c.toArray();
//拿到c的长度
int numNew = a.length;
//检查是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//将a数组拷贝到原来数组的末尾
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//将集合c的元素从index位置开始添加到list中
public boolean addAll(int index, Collection<? extends E> c) {
//检查index是否越界
rangeCheckForAdd(index);
//将c转换为数组
Object[] a = c.toArray();
//获取数组a的长度
int numNew = a.length;
//检查是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//计算需要移动的长度
int numMoved = size - index;
if (numMoved > 0)
//向后移动
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
将数组a拷贝到原数组中
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
get方法
public E get(int index) {
//检查index是否越界
rangeCheck(index);
//返回对应数组中指定索引的元素
return elementData(index);
}
remove方法
//删除指定索引的元素
public E remove(int index) {
//判断index是否越界
rangeCheck(index);
//将数组修改次数+1
modCount++;
//拿到对应索引的元素
E oldValue = elementData(index);
计算移动位置
int numMoved = size - index - 1;
if (numMoved > 0)
//移动数组
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//size-1，并把尾部元素置为null，这里把尾部置为null主要是为了让GC起作用
elementData[--size] = null;
return oldValue;
}
//删除第一个满足o.equals(elementData[index]的元素
public boolean remove(Object o) {
if (o == null) {
//如果o为null使用==进行判断
//从索引为0的元素开始寻找
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//否则使用equals判断
//从索引为0的元素开始寻找
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
小结
如果我们的数据量很大，我们可以给List估算一个容量，然后进行初始化，否则会对效率有影响，毕竟一直进行数据迁移。
最开始Arraylist的容量为10，每次扩容为原先容量的1.5倍，但是如果我们已经扩容的数组，是不能进行缩容的，例如我们添加了10个元素，这个时候已经扩容了，但是我们删除最后一个元素，他是不会进行缩容的
我们并没有看到他方法上有synchronized关键字，所以他也不是线程安全的，我们可以使用Vector或者使用
Collections.synchronizedList(list)
LinkedList
对于LinkedList，它同样继承与AbstractList，在前面已经说过了，AbstractList是List的骨架，我们还可以看到它实现了Deque，所以LinkedList既可以看做一个链表也可以看做是一个队列，同样也可以看做一个栈，所以LinkedList比较全能
Node类
我们知道LinkedList是一个双向链表，那么肯定有一个个的Node，所以我们先来看一看Node类
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
这部分代码比较简单就简单说一下，Node节点有三个成员属性，分别是value，前驱指针，后继指针，以及一个全参构造方法
成员属性
/**
元素个数
*/
transient int size = 0;
/**
指向链表头结点
*/
transient Node<E> first;
/**
指向链表尾节点
*/
transient Node<E> last;
/**
序列化ID
*/
private static final long serialVersionUID = 876323262645176354L;
构造函数
//空参构造，没什么好说的
public LinkedList() {
}
//将集合c的元素添加到链表中
public LinkedList(Collection<? extends E> c) {
//调用空参构造
this();
//调用addAll()这个方法在下面讲述
addAll(c);
}
添加
public boolean add(E e) {
linkLast(e);//添加元素到末尾
return true;
}
//将元素添加到指定index位置
public void add(int index, E element) {
//检查索引是否大于size或者小于0
checkPositionIndex(index);
//如果索引位置和size相等添加到末尾
if (index == size)
linkLast(element);
else
//添加到指定位置
linkBefore(element, node(index));
}
public void addFirst(E e) {
linkFirst(e);//添加元素到头部
}
public void addLast(E e) {
linkLast(e);//添加元素到末尾
}
//添加到头部
private void linkFirst(E e) {
//拿到头指针
final Node<E> f = first;
//new一个Node节点，值为e，next为头指针，pre为null
final Node<E> newNode = new Node<>(null, e, f);
//将头指针替换为新的
first = newNode;
//将f的pre修改为现在的头指针
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//添加到末尾
void linkLast(E e) {
//拿到尾指针
final Node<E> l = last;
//new一个Node节点，值为e，next为null，pre为尾指针
final Node<E> newNode = new Node<>(l, e, null);
//替换尾指针
last = newNode;
//将l的next修改为现在的尾指针
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//将集合c的元素添加到list中
public boolean addAll(Collection<? extends E> c) {
//从尾部开始添加
return addAll(size, c);
}
//真正的addAll方法
public boolean addAll(int index, Collection<? extends E> c) {
//检查index正确
checkPositionIndex(index);
//先把c转换为数组
Object[] a = c.toArray();
//拿到c的长度
int numNew = a.length;
if (numNew == 0)
return false;
//定义两个指针，一个前驱一个后继
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//遍历数组a
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//new一个Node节点，值为e，前驱为pred，后继为null
Node<E> newNode = new Node<>(pred, e, null);
//pred为null，证明前驱为null，当前节点为链表的头结点
if (pred == null)
first = newNode;
else
//前驱节点后继指针指向头结点
pred.next = newNode;
//前驱节点后移
pred = newNode;
}
//succ为null证明index索引位于链表最后
if (succ == null) {
last = pred;
} else {
//pred的后继节点为succ
pred.next = succ;
//succ的前驱节点为pred
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
获取
//这个方法是Node类的方法，我们可以看到上面的addAll方法也使用了这个方法
//这个方法作用是返回指定索引的非空节点
Node<E> node(int 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;
}
}
//获取index位置的元素
public E get(int index) {
//检查索引是否正常
checkElementIndex(index);
return node(index).item;
}
//获取头部元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//获取尾部元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
删除
//删除index位置的元素
public E remove(int index) {
//检查索引是否大于size或者小于0
checkElementIndex(index);
//删除index位置的元素
return unlink(node(index));
}
//删除头部元素，这个方法是Node类的方法
private E unlinkFirst(Node<E> f) {
//拿到头节点的值
final E element = f.item;
//拿到头结点的next值
final Node<E> next = f.next;
//将头结点的值置为null(帮助GC)
f.item = null;
//将头结点的next置为null(帮助GC)
f.next = null;
//将头结点修改为next
first = next;
if (next == null)
//此时链表没有元素了
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//删除尾部元素，这个方法是Node类的方法
private E unlinkLast(Node<E> l) {
//拿到尾节点的值
final E element = l.item;
//拿到尾节点的前驱
final Node<E> prev = l.prev;
//将尾结点的值置为null(帮助GC)
l.item = null;
//将尾结点的next置为null(帮助GC)
l.prev = null;
//将尾指针修改为prev
last = prev;
if (prev == null)
//此时链表没有元素了
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
小结
虽然说链表的删除的效率为O(1),但是在LinkedList中我们需要先利用node方法查询到指定节点的位置，然后再去删除，所以千万不要误认为LinkedList的remove方法是O(1)
LinkedList删除头部和尾部的元素效率为O(1)
来源：https://juejin.cn/post/7129794709882404894
0
投稿猜你喜欢
- Java代码1. ReentrantLock加锁阻塞，一个condition对应一个线程，以便于唤醒时使用该condition一定会唤醒该线
- 测试例:PageElement pe = new PageElement();pe.LoadDataFromJsonString("
- 自定义工具类PropertyUtil，并在该类的static静态代码块中读取properties文件内容保存在static属性中以供别的程序
- 我们都知道EditText与TextView是Android的文本输入框和文本显示框，但是基于手机屏幕的大小因素，如果在需要输入较多文字或者
本文实例讲述了Android编程单选项框RadioGroup用法。分享给大家供大家参考，具体如下：今天介绍的是RadioGroup 的组事件- Idea2020.2创建JavaWeb的方式略有改动,以下做个记录，大家可以参考下，对以后的工作有所帮助！1.创建项目不再是Java Ent
- 一、前期准备我们要在IDEA上创建一个新的项目，创建好一个项目后，我们需要创建4个包，分别是英雄包，装备包，铭文包，野怪包，皮肤包然后我们就
- 实现客户端发送请求，服务器端响应机制UDP客户端代码using System;using System.Text;using System.
- forword跳转页面的三种方式：1.使用serlvet/** * 使用forward跳转,传递基本类型参数到页面
- 一种方法是可以在窗体的属性面板将窗体的 ControlBox属性设置为false，或者在窗体的构造函数中这样写：public F
- 前言近期有个业务需求，涉及用户付费相关的计算，需要一个日历组件，组件功能如下：仅支持从明天开始选择预定日期仅支持可选范围内的日期日期的选择是
- spring cloud gateway读取请求参数1. 我的版本：spring-cloud：Hoxton.RELEASEspring-bo
- 一、前言最近在回顾数据结构与算法，有部分的算法题用到了栈的思想，说起栈又不得不说链表了。数组和链表都是线性存储结构的基础，栈和队列都是线性存
- C#将图片2值化示例代码，原图及二值化后的图片如下：原图：二值化后的图像：实现代码：using System;using System.Dr
- 本文实例讲述了Android自定义ViewPager的方法。分享给大家供大家参考，具体如下：package com.rong.activit
- SessionSession对象用于获取与数据库的物理连接。 Session对象是重量轻，设计了一个互动是需要与数据库每次被实例化。持久化对
- 网上的教程大都是手动通过protoc编译, 比较难用给当前工程添加"Google.Protobuf"和"Grp
- IComparable<T>.NET 里，IComparable<T>是用来作比较的最常用接口。如果某个类型的实例需
- 前言文件的上传和下载都是基于io复制,只不过文件上传是浏览器向服务器发送报文文件下载是服务器向浏览器发送报文提示：以下是本篇文章正文内容，下
- Spring中实现多线程，其实非常简单，只需要在配置类中添加@EnableAsync就可以使用多线程。在希望执行的并发方法中使用@Async
