让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明

2024-05-14 14:08
文章标签 源码 方法 数据结构 说明 底层 arraylist 星星 告诉 linkedlist 月亮

本文主要是介绍让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、⭐⭐⭐LinkedList(同时实现了List< E >接口和Deque< E > implements Queue< E >接口)🌙🌙🌙

1.LinkedList底层数据结构是一个双向链表(每个节点除了本身元素外,还包含了要指向的前一个节点Node< E > prev和后一个节点Node< E > next),双向链表还记录了头节点Node< E > first和尾节点Node< E > last(从JDK1.7才开始有的，之前JDK1.6里只有头节点header，头节点的前一个节点代表的是最后一个节点).
2.链表的数据结构在逻辑上是连续的,但是在物理空间上是不连续的(因此,索引下标和头元素存放的物理内存地址是不相关的,所以不能根据索引下标直接获取到元素,需要根据前后节点关系、索引值以及链表元素总个数size循环遍历才能走访到指定索引位置的元素);
3.LinkedList根据索引下标获取元素get(index)方法的具体逻辑如下:

 public E get(int index) {checkElementIndex(index);//这个方法逻辑很简单,就是判断索引下标是否在链表长度范围内,超出范围则报IndexOutOfBoundsExceptionreturn node(index).item;//重点关注这里的node(index)方法采用了优化算法,先用index与链表长度size的一半比较(index < (size>>1)),若小于则从first-index,利用Node.next去一个个从前往后循环遍历直到到达index所在位置;若大于则从last-index,利用Node.prev去一个个从后向前循环遍历直到到达index所在位置.这样可以减少一半的遍历次数,性能有所提升.之所以可以采用这种优化算法,前提是在向链表中新增元素时,size加一和更新next/prev指向会同时执行,从而使得size\first\last之间通过next/prev的逻辑串联起来,第一个索引下标元素first,那么第二个索引下标元素就是first.next,最后一个索引下标元素last,那么倒数第二个索引下标元素就是last.prev.}/*** Returns the (non-null) Node at the specified element index.*/Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) {//用index与链表长度size的一半比较,右移>>位运算Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;//从first开始,从前往后一个个遍历直到到达index所在位置return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;//从last开始,从后向前一个个遍历直到到达index所在位置return x;}}

4.LinkedList增加元素到指定索引下标add(index,Node< E > e)方法的具体逻辑如下:

/*** Inserts the specified element at the specified position in this list.* Shifts the element currently at that position (if any) and any* subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/public void add(int index, E element) {checkPositionIndex(index);//这个方法逻辑很简单,就是判断索引下标是否在链表长度范围内,超出范围则报IndexOutOfBoundsExceptionif (index == size)linkLast(element);//若index等于size,说明要在末位增加元素,直接调用末位增加元素的指定方法linkLast(element)即可,这样可以避免走下面的逻辑,避免多绕弯儿elselinkBefore(element, node(index));//该方法分两部分:(1)查到指定index所在位置的元素Node<E> succ,然后再将succ.prev指向要增加的新元素element,这样就在index位置插入了新元素.}/*** Inserts element e before non-null Node succ.*/void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}

5.LinkedList在首尾增加元素时请务必直接使用addFirst(E e)和addLast(E e)方法,直接对first和last节点进行前prev后next指向的更新操作,这样可以少走一些代码逻辑,执行更快一些,removeFirst(Node< E > l)和removeLast(Node< E > l)也一样.

6.LinkedList更新指定索引位置的元素值时,原理跟增删一样,都需要先根据index循环遍历查找到index位置的节点Node< e >,然后再进行相关处理(节点前后指向的更新或节点元素值的更新)

 /*** Replaces the element at the specified position in this list with the* specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}

7.由于Linked List 也实现了Deque< E > implements Queue< E >接口,所以具有以下相关方法:
(1)add VS offer(**注意:**LinkedList重写的offer方法体里是直接调用的add方法)：
add()和offer()方法都可以往队列末尾增加元素。当队列已经到达最大容量后,再往里面增加元素,add() 会抛出属于非检查异常的几种RuntimeException(IllegalStateException/ClassCastException/NullPointerException/IllegalArgumentException)，而offer返回false不抛出异常。
(2)element VS peek：
element() 和 peek()方法 都可以查询队列的首位元素。当队列为空时，element()方法会抛出异常，而 peek()返回null不抛出异常。
(3)remove VS poll：
remove() 和 poll() 方法都可以从删除队列的首位元素。当队列为空时，remove()方法会抛出异常，而 poll()返回null不抛出异常。

二、⭐⭐⭐ArrayList🌙🌙🌙

1.ArrayList底层数据结构是基于动态数组，与普通数组相比较而言，动态数组可以实现数组长度的自动扩容。由于是底层是数组结构(Object []),且实现了RandomAccess随机存取标志接口(表明实现这个这个接口的 List 集合是支持快速随机访问的。也就是说，实现了这个接口的集合是支持 快速随机访问策略,而且如果是实现了这个接口的 List，那么使用for循环的方式获取数据会优于用迭代器获取数据【所以大家在看ArrayList源码时能观察到遍历时采用的都是for而非迭代器】，因为for里面利用的就是随机访问(根据下标快速找到指定位置的元素)这一特性);
2.所以其指定索引位置查询get(index)的操作效率就比较高，时间复杂度为O(1)；

 /*** Returns the element at the specified position in this list.** @param  index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {rangeCheck(index);//此方法很简单,检查索引是否越界return elementData(index);//返回数组的指定位置的元素}// Positional Access Operations 位置访问操作@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}

3.但其在指定位置的增add(index,E element)删remove(index)操作就性能就比较低，因为会导致后续相关数组元素的位置移动(数据复制,调用System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length))),add(index,E element)可能会引发二次数组复制.
add(index,E element)

/*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/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++;}

注意:当往数组add元素时,可能会引发数据扩容的相关操作,代码逻辑如下:

(1)private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}
(2)private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}
(3)private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}
(4)
/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容为旧容量的1.5倍if (newCapacity - minCapacity < 0)//若扩容为原容量的1.5倍后依然不满足要存的元素个数的要求(在往数组中添加集合addAll(Collection<? extends E> c)时可能会出现这种情况)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);
}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

remove(index)

/*** Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their* indices).** @param index the index of the element to be removed* @return the element that was removed from the list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)//除非要删除的元素是最后一个,否则会发生数组复制System.arraycopy(elementData, index+1, elementData, index,numMoved);//数组复制,将数组中原先处于(index+1,index+1+numMoved)的这段元素复制到(index,index+numMoved),相当于这段元素(索引值都减了1)都往前移动了一位.elementData[--size] = null; // clear to let GC do its workreturn oldValue;}

4.[指定删除某个元素数据的方法remove(Object o)效率更低,因为会先去循环遍历找到元素所在索引位置,然后再去进行数组复制,多了一层循环操作];

/*** Removes the first occurrence of the specified element from this list,* if it is present.  If the list does not contain the element, it is* unchanged.  More formally, removes the element with the lowest index* <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>* (if such an element exists).  Returns <tt>true</tt> if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** @param o element to be removed from this list, if present* @return <tt>true</tt> if this list contained the specified element*/public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)//从0开始在0-size范围内循环遍历if (elementData[index] == null) {//找到满足条件的元素fastRemove(index);//开始remove处理,很大可能会引发数组复制,除非要删除的元素是最后一个return true;}} else {for (int index = 0; index < size; index++)//从0开始在0-size范围内循环遍历if (o.equals(elementData[index])) {//找到满足条件的元素fastRemove(index);//开始remove处理,很大可能会引发数组复制,除非要删除的元素是最后一个return true;}}return false;}/** Private remove method that skips bounds checking and does not* return the value removed.*/private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;if (numMoved > 0)//除非要删除的元素非最后一个,否则会发生数组复制System.arraycopy(elementData, index+1, elementData, index,numMoved);//数组复制,将数组中原先处于(index+1,index+1+numMoved)的这段元素复制到(index,index+numMoved),相当于这段元素(索引值都减了1)都往前移动了一位.elementData[--size] = null; // clear to let GC do its work}

5.而在尾部增add(E element)(不触发扩容时不移动,触发扩容的话就同在指定位置增add(int index,E element)一样,也还是会调用native的System.arraycopy方法发生数组复制)删remove(index)时不用移动。

 /*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!可能会引发数据扩容,进而可能出现数组复制(元素个数超过数组目前容量值时)elementData[size++] = e;return true;}

6.更新指定索引位置的元素值set(int index,E element)需要先查找到该索引下的元素(因为需要返回该旧值),然后再更新为新元素,故其效率几乎等同于查找指定索引位置元素的get(index)方法.

 /*** Replaces the element at the specified position in this list with* the specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}

这篇关于让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/988945。

相关文章

Zookeeper安装和配置说明

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种，单机模式和集群模式以及伪集群模式。 ■ 单机模式：Zookeeper只运行在一台服务器上，适合测试环境； ■ 伪集群模式：就是在一台物理机上运行多个Zookeeper 实例； ■ 集群模式：Zookeeper运行于一个集群上，适合生产环境，这个计算机集群被称为一个“集合体”（ensemble） Zookeeper通过复制来实现
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
浅谈主机加固，六种有效的主机加固方法

浅谈主机加固，六种有效的主机加固方法

在数字化时代，数据的价值不言而喻，但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露，企业的数据安全面临着前所未有的挑战。为了应对这些挑战，一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案，采用先进的安全容器中间件技术，构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限，即使在管理员权限被恶意利用的情况下，也能确保服务器的安全稳定运行。 普适主机加固措施：
阅读更多...
webm怎么转换成mp4？这几种方法超多人在用！

webm怎么转换成mp4？这几种方法超多人在用！

webm怎么转换成mp4？WebM作为一种新兴的视频编码格式，近年来逐渐进入大众视野，其背后承载着诸多优势，但同时也伴随着不容忽视的局限性，首要挑战在于其兼容性边界，尽管WebM已广泛适应于众多网站与软件平台，但在特定应用环境或老旧设备上，其兼容难题依旧凸显，为用户体验带来不便，再者，WebM格式的非普适性也体现在编辑流程上，由于它并非行业内的通用标准，编辑过程中可能会遭遇格式不兼容的障碍，导致操
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
git使用的说明总结

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库：创建新文件夹，进入文件夹目录，执行指令 git init ，用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2