Java ArrayList与LinkedList使用方法详解
作者:宏远十一冠王 发布时间:2023-08-12 08:23:46
前言
最近参加了21天打卡活动,希望可以让自己养成写博客的习惯…
ArrayList和LinkedList
ArrayList和LinkedList都是常用的List类型,两者都继承了AbstratctList,并实现List接口。
List的方法
列举一些常见的方法,ArrayList和LinkedList会实现List里面的方法
方法 | 描述 |
---|---|
boolean isEmpty() | 判断当前列表是否为空 |
boolean contains(Object o) | 是否包含这个元素 |
T[] toArray(T[] a) | |
boolean add(E e) | 添加一个元素 |
boolean remove(Object o) | 移除 |
boolean containsAll(Collection<?> c) | |
void add(int index, E element) | 在固定位置添加元素 |
int indexOf(Object o) | 定位元素 |
ListIterator listIterator() | 遍历列表 |
上述的方法都是List的常用方法,相信大家都非常的熟悉。
ArrayList
ArrayList是实现List接口的可扩容数组(动态数组),它的内部是基于数组实现的,数组这个结构具有的特点
随机存取:随机存取就是可以通过索引直接访问列表的元素
可以实现动态扩容,下面我们来看一下它的源码实现
属性 | 描述 |
---|---|
size | 列表的元素个数 |
DEFAULT_CAPACITY | 创建一个空对象时的默认大小 |
我们来看一下ArrayList是怎么实现动态扩容的。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
如果当容量比初始容量大时,新的容量相当于是原来的1.5倍这里
add
ArrayList重载了List的add方法,这里面重写的方法有直接添加,和在某一个位置添加一个元素,这里就可以看出ArrayList的底层是由数组实现的了
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
这里采用的是System.arraycopy来进行数组的拷贝,属于深度拷贝,效率很高。
remove
这里的移除也是有直接移除某个索引下的数据,但是这里面有两个不同的方式移除数据,一个是remove,一个是fastRemove两种方式移除元素,remove和fastRemove不同的是一个是需要返回删除的元素,一个是不返回的。
LinkedList
LinkedList是基于双向链表来实现的,是属于链式存储,只能顺序存取元素,不能随机存取。
LinkedList的结点结构,包括指向下一个结点的指针next和指向上一个结点的指针prev
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;
}
}
属性包括
名称 | 描述 |
---|---|
size | 元素个数 |
first | 头节点 |
last | 尾节点 |
remove
移除头节点,需要更新size大小和把删除的节点为NULL,里面还有removeRange方法,可以把从fromIndex到toIndex的全部节点释放掉
public E remove() {
return removeFirst();
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
get和peek
下面可以来看看LinkedList的访问元素的形式,前面说了这个结构是只能顺序遍历的,不能随机进行访问,需要遍历整个列表,但是我们使用的是双向链表,由于我们维护了头节点和尾节点,当需要访问元素时,如果根据的是下标(这里的下标不是数组的下标),先判断和头节点近还是和尾节点近,然后再进行顺序遍历。
peek方法是访问头节点。
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;
}
}
push
向列表中添加元素,我们可以采用offerFirst和offerLast往列表头部添加元素或者往尾部添加元素,push方法调用的是addFrist方法,采用的是头插法,删除也是才有删除头部元素;
ArrayList和LinkedList的使用场景和区别
前面也提到两者的存取结构是不同的,一个是用数组来操作,一个采用的是双向链表,一般ArrayList用在访问更加多的情况下,由于插入会相对较慢,但是LinkedList采用的是顺序访问,在插入和删除较多的场景会更加适用。
来源:https://blog.csdn.net/zly03/article/details/126129147
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- springboot嵌套子类使用在实际项目里,我们会使用到一个User用户含有子类Address、这种嵌套子类在开发中会遇到很多问题,现在主
- 1. 新建TestServlet类package com.yanek.test;import java.io.IOException;imp
- spinner组件有点类型于HTML中的下拉框<Select></select>的样子,让用户每次从下拉框中选取一个
- 前言很多时候,当你以为掌握了事实真相的时间,如果你能再深入一点,你可能会发现另外一些真相。比如面向切面编程的最佳编程实践是AOP,AOP的主
- 前言spring中解析元素最重要的一个对象应该就属于 BeanDefinition了;这个Spring容器中最基本的内部数据结构;它让xml
- 1、使用JPA 的@Enumerated 注解 ,可以直接将Enum映射到数据库中。但是value的值只有两种方式选择,一种是使用枚举的序号
- 前言:什么是多数据源?最常见的单一应用中最多涉及到一个数据库,即是一个数据源(Datasource)。那么顾名思义,多数据源就是在一个单一应
- SqlMapConfig.xml的约束,也就是Mybatis主配置文件的约束<?xml version="1.0"
- 本文实例讲述了Java文件操作工具类fileUtil。分享给大家供大家参考,具体如下:package com.gcloud.common;i
- 面试题1:谈一下你对 Nginx 的理解Nginx 是一款自由的、开源的、高性能的 HTTP 服务器和反向代理服务器;同时也是一个 IMAP
- makeCertPic.javapackage pic;import java.awt.Color;import java.awt.Font
- 本文实例讲述了Java集合定义与用法。分享给大家供大家参考,具体如下:java集合大体可分为三类,分别是Set、List和Map,它们都继承
- 一、一级缓存二级缓存的概念解释(1)一级缓存就是Session级别的缓存,一个Session做了一个查询操作,它会把这个操作的结果放在一级缓
- 前言Hello!上一期我大致讲解了关于Collection单列集合以及它的子接口List集合的概述、特点和遍历等,今天我为大家讲解关于Col
- File 类:文件和目录路径名的抽象表示。注意:File 类只能操作文件的属性,文件的内容是不能操作的。1、File 类的字段我们知道,各个
- 最近在做一个项目,遇到了项目打成 war 包的一个问题,项目创建时选择的时 jar 包方式,后因项目部署要求,需要打成 war 包部署,遇到
- import java.util.Arrays;/** * 栈的实现<br> * @author Skip&
- 最近在开发项目的时候遇到一个问题,在myecilpes上使用googlede gson读取项目中的json文件成功,然后把项目发布到tomc
- 1. 前言我们知道,在日常开发中使用的 HashMap 是线程不安全的,而线程安全类 HashTable 和 SynchronizedMap
- Java8新特性系列我们已经介绍了Stream、Lambda表达式、DateTime日期时间处理,最后以“NullPointerExcept