Day26 手撕各种集合底层源码（一）

news/2024/5/15 8:59:23/文章来源:https://blog.csdn.net/yjp1240201821/article/details/137158512

Day26 手撕各种集合底层源码（一）

一、手撕ArrayList底层源码

1、概念： ArrayList的底层实现是基于数组的动态扩容结构。

2、思路：
1.研究继承关系
2.研究属性
3.理解创建集合的过程 – 构造方法的底层原理
4.研究添加元素的过程

3、关键源码：

成员变量：

transient Object[] elementData; // 用于存储元素的数组
private int size; // ArrayList中元素的数量

构造方法：

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 初始容量为0的空数组
}public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity]; // 指定初始容量的数组} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; // 初始容量为0的空数组} else {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}
}

添加元素方法（add）：

public boolean add(E e) {ensureCapacityInternal(size + 1);  // 确保容量足够elementData[size++] = e; // 将元素添加到数组末尾return true;
}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 默认容量为10}ensureExplicitCapacity(minCapacity); // 确保容量足够
}private void ensureExplicitCapacity(int minCapacity) {modCount++;if (minCapacity - elementData.length > 0) {grow(minCapacity); // 扩容}
}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}if (newCapacity - MAX_ARRAY_SIZE > 0) {newCapacity = hugeCapacity(minCapacity);}elementData = Arrays.copyOf(elementData, newCapacity); // 数组扩容
}

4、举例：

public static void main(String[] args) {​	//ArrayList<String> list = new ArrayList<>();
​	ArrayList<String> list = new ArrayList<>(10000);
​	
​	list.add("aaa");
​	list.add("bbb");
​	list.add("ccc");
​	list.add("ddd");
​	
}

二、手撕LinkedList底层源码

1、概念： LinkedList的底层实现是基于双向链表的数据结构。

2、思路：

​ 1.研究继承关系
​ 2.研究属性
​ 3.理解创建集合的过程 – 构造方法的底层原理
​ 4.研究添加元素的过程

3、关键源码：

节点定义：

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;}
}

成员变量：

transient int size = 0; // LinkedList中元素的数量
transient Node<E> first; // 链表的头节点
transient Node<E> last; // 链表的尾节点

添加元素方法（add）：

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++; // 元素数量加1
}

删除元素方法（remove）：

public E remove() {return removeFirst(); // 删除链表的第一个节点
}public E removeFirst() {final Node<E> f = first;if (f == null) {throw new NoSuchElementException();}return unlinkFirst(f); // 删除第一个节点
}E unlinkFirst(Node<E> f) {final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next; // 将下一个节点设置为头节点if (next == null) {last = null; // 如果下一个节点为空，将尾节点置空} else {next.prev = null; // 将下一个节点的前驱节点置空}size--; // 元素数量减1return element;
}

4、举例：

	public static void main(String[] args) {LinkedList<String> list = new LinkedList<>();list.add("小浩");list.add("小威");list.add("小刘");}

三、手撕Stack底层源码

1、概念： Java中的Stack类是基于动态数组实现的后进先出（LIFO）栈结构。然而，需要注意的是，Java官方推荐使用Deque接口的实现类ArrayDeque来代替Stack类，因为Deque接口提供了更完善的栈操作方法，并且在性能上更优秀。

2、关键源码：

成员变量：

private transient Object[] elementData; // 用于存储栈元素的数组
private int elementCount; // 栈中元素的数量

基本方法：

public E push(E item) {addElement(item); // 将元素压入栈顶return item;
}public synchronized E pop() {E obj;int len = size();obj = peek(); // 获取栈顶元素removeElementAt(len - 1); // 移除栈顶元素return obj;
}public synchronized E peek() {int len = size();if (len == 0) {throw new EmptyStackException();}return elementAt(len - 1); // 获取栈顶元素
}

扩容方法：

java复制代码private void ensureCapacity(int minCapacity) {if (minCapacity - elementData.length > 0) {grow(minCapacity); // 扩容}
}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}if (newCapacity - MAX_ARRAY_SIZE > 0) {newCapacity = hugeCapacity(minCapacity);}elementData = Arrays.copyOf(elementData, newCapacity); // 数组扩容
}

3、举例：

import java.util.Stack;public class Test01 {/*** 知识点：手撕Stack底层源码*/public static void main(String[] args) {Stack<String> stack = new Stack<>();stack.push("aaa");stack.push("bbb");stack.push("ccc");stack.push("ddd");}
}

四、单向链表

1、概念： 单向链表（Singly Linked List）是一种常见的链表数据结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。单向链表的最后一个节点指向空值（null），表示链表的结束。

2、特点：

  1. 单向遍历：只能从头到尾遍历链表，无法反向遍历。
  2. 插入和删除：在已知节点的情况下，可以方便地进行节点的插入和删除操作。
  3. 空间开销：相对于数组，单向链表需要额外的空间来存储指针。

3、应用场景：

  • 需要频繁的插入和删除操作，且不需要反向遍历的场景。
  • 需要在已知节点的情况下进行插入和删除操作的场景。

4、关键源码：

成员变量：

private transient Object[] elementData; // 用于存储栈元素的数组
private int elementCount; // 栈中元素的数量

基本方法：

public E push(E item) {addElement(item); // 将元素压入栈顶return item;
}
public synchronized E pop() {E obj;int len = size();obj = peek(); // 获取栈顶元素removeElementAt(len - 1); // 移除栈顶元素return obj;
}
public synchronized E peek() {int len = size();if (len == 0) {throw new EmptyStackException();}return elementAt(len - 1); // 获取栈顶元素
}

扩容方法：

private void ensureCapacity(int minCapacity) {if (minCapacity - elementData.length > 0) {grow(minCapacity); // 扩容}
}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}if (newCapacity - MAX_ARRAY_SIZE > 0) {newCapacity = hugeCapacity(minCapacity);}elementData = Arrays.copyOf(elementData, newCapacity); // 数组扩容
}

5、举例：

import java.util.Iterator;
public class Test01 {/*** 知识点：实现单向链表*/public static void main(String[] args) {UnidirectionalLinkedList<String> list = new UnidirectionalLinkedList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");list.add("eee");Iterator<String> it = list.iterator();while(it.hasNext()){String element = it.next();System.out.println(element);}}
}
public class UnidirectionalLinkedList<E> {private Node<E> first;private Node<E> last;private int size;public void add(E e){Node<E> node = new Node<>(e, null);if(first == null){first = node;}else{last.next = node;}last = node;size++;}public Iterator<E> iterator(){return new Itr();}public class Itr implements Iterator<E>{private int cursor;private Node<E> node = first;@Overridepublic boolean hasNext() {return cursor != size;}@Overridepublic E next() {E item = node.item;node = node.next;cursor++;return item;}}public static class Node<E>{E item;Node<E> next;public Node(E item, Node<E> next) {this.item = item;this.next = next;}}}

五、双向链表

1、概念： 双向链表（Doubly Linked List）是一种常见的链表数据结构，每个节点包含两个指针，分别指向前一个节点和后一个节点。与单向链表相比，双向链表可以支持双向遍历，提供了更多的灵活性 。

2、特点：

  1. 双向遍历：可以从头到尾或者从尾到头遍历链表，提供了更多的遍历方式。
  2. 插入和删除：在已知节点的情况下，可以更方便地进行节点的插入和删除操作。
  3. 空间开销：相对于单向链表，双向链表需要额外的空间来存储前驱节点的指针。

3、应用场景：

  • 需要频繁的插入和删除操作，且需要双向遍历的场景。
  • 需要在已知节点的情况下进行插入和删除操作的场景。

4、基本操作：

  1. 插入节点：在给定节点后或前插入新节点，需要更新前后节点的指针。
  2. 删除节点：删除给定节点，同样需要更新前后节点的指针。
  3. 遍历：可以从头到尾或者从尾到头遍历链表，获取节点的值或执行其他操作。

5、代码理解：

import java.util.Iterator;
import com.qf.bidirectional_linked_list.BidirectionalLinkedList.Node;public class Test01 {/*** 知识点：实现双向链表*/public static void main(String[] args) {BidirectionalLinkedList<String> list = new BidirectionalLinkedList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");list.add("eee");//正序遍历Iterator<String> it = list.iterator();while(it.hasNext()){String element = it.next();System.out.println(element);}System.out.println("-----------------------");//倒序遍历Node<String> node = list.getLast();while(node != null){System.out.println(node.item);node = node.prev;}}
}public class BidirectionalLinkedList<E> {private Node<E> first;private Node<E> last;private int size;public void add(E e){Node<E> l = last;Node<E> node = new Node<>(l,e, null);if(first == null){first = node;}else{last.next = node;}last = node;size++;}public Node<E> getLast() {return last;}public Iterator<E> iterator(){return new Itr();}public class Itr implements Iterator<E>{private int cursor;private Node<E> node = first;@Overridepublic boolean hasNext() {return cursor != size;}@Overridepublic E next() {E item = node.item;node = node.next;cursor++;return item;}}public static class Node<E>{Node<E> prev;E item;Node<E> next;public Node(Node<E> prev,E item, Node<E> next) {this.prev = prev;this.item = item;this.next = next;}}}

LinkedList理解图：
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_1028653.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

wpf 自定义命令

wpf 自定义命令

自定义命令 MyCommand.cs public class MyCommand : ICommand {private readonly Action<Object> execAction;private readonly Func<Object,bool> changedFunc;public event EventHandler? CanExecuteChanged;public MyCommand(Action<object> execAction…
阅读更多...
离线linux服务器安装mysql8

离线linux服务器安装mysql8

本文的服务器环境&#xff1a;openEuler毛坯版的&#xff0c;很多常用的指令都没有预装&#xff0c;比如rpm、tar等等&#xff0c;没有网络坏境&#xff0c;需要自己手动配置本地yum仓库&#xff0c;安装相关指令 1、检查服务器是否已经安装了MySQL 1.1、查询mysql以安装的相关…
阅读更多...
NRF52832修改OTA升级时的bootloader蓝牙MAC

NRF52832修改OTA升级时的bootloader蓝牙MAC

NRF52832在OTA升级时&#xff0c;修改了APP的蓝牙MAC会导致无法升级&#xff0c;原因是OTA程序的蓝牙MAC没有被修改所以手机扫描蓝牙时无法连接 解决办法 在bootloader的程序里面加入修改蓝牙mac地址的代码实现原理&#xff1a; 在bootloader蓝牙广播开启之前修改蓝牙mac 通…
阅读更多...
无人车网关案例：记SV900无人清扫车网关的现场应用

无人车网关案例：记SV900无人清扫车网关的现场应用

​随着无人驾驶技术的不断发展,无人车辆已经开始广泛应用于物流配送、环境保洁、巡逻监控等众多领域,助力城市运营更加高效智能。而要实现无人车辆的安全可靠运行,关键在于选择一款性能卓越的车载网络通信系统.在这一背景下,星创易联推出了SV900无人车网关系列产品。它集5G/4G网…
阅读更多...
算法打卡day17

算法打卡day17

今日任务&#xff1a; 1&#xff09;654.最大二叉树 2&#xff09;617.合并二叉树 3&#xff09;700.二叉搜索树中的搜索 4&#xff09;98.证二叉搜索树 654.最大二叉树 题目链接&#xff1a;654. 最大二叉树 - 力扣&#xff08;LeetCode&#xff09; 给定一个不含重复元素的整…
阅读更多...
计算机网络数据链路层知识总结

计算机网络数据链路层知识总结

物理层知识总结传送门 计算机网络物理层知识点总结-CSDN博客 功能 功能概述 一些基本概念 结点:主机、路由器链路﹔网络中两个结点之间的物理通道&#xff0c;链路的传输介质主要有双绞线、光纤和微波。分为有线链路、无线链路。数据链路︰网络中两个结点之间的逻辑通道&a…
阅读更多...
HarmonyOS实战开发-如何实现一个自定义抽奖圆形转盘

HarmonyOS实战开发-如何实现一个自定义抽奖圆形转盘

介绍 本篇Codelab是基于画布组件、显式动画&#xff0c;实现的一个自定义抽奖圆形转盘。包含如下功能&#xff1a; 通过画布组件Canvas&#xff0c;画出抽奖圆形转盘。通过显式动画启动抽奖功能。通过自定义弹窗弹出抽中的奖品。 相关概念 Stack组件&#xff1a;堆叠容器&am…
阅读更多...
STM32第十节（中级篇）：EXTI（第一节）——EXTI功能框图及初始化结构体讲解（包括STM32中断应用总结）

STM32第十节（中级篇）：EXTI（第一节）——EXTI功能框图及初始化结构体讲解（包括STM32中断应用总结）

目录 前言 STM32第十节&#xff08;中级篇&#xff09;&#xff1a;EXTI&#xff08;第一节&#xff09;——EXTI功能框图及初始化结构体讲解&#xff08;包括STM32中断应用总结&#xff09; EXTI功能框图 EXTI初始化结构体讲解 STM32中断应用总结 NVIC介绍 优先级 优先…
阅读更多...
后端常问面经之并发

后端常问面经之并发

volatile 关键字 volatile关键字是如何保证内存可见性的&#xff1f;底层是怎么实现的&#xff1f; "观察加入volatile关键字和没有加入volatile关键字时所生成的汇编代码发现&#xff0c;加入volatile关键字时&#xff0c;会多出一个lock前缀指令”lock前缀指令实际上相…
阅读更多...
Radash一款JavaScript最新的实用工具库，Lodash的平替！

Radash一款JavaScript最新的实用工具库，Lodash的平替！

文章目录 Lodash 的痛点进入正题--Radash特点 举例几个常用的api 一说lodash应该大部分前端同学都知道吧&#xff0c;陪伴我们好多年的JavaScript工具库&#xff0c;但是自从 ES6 出现后就慢慢退出前端人的视线&#xff0c;能ES6写的代码绝对不会用Lodash&#xff0c;也不是完全…
阅读更多...
C#预处理器指令（巨细版）

C#预处理器指令（巨细版）

文章目录 一、预处理器指令的基本概念二、预处理器指令的基本规则三、C# 预处理器指令详解3.1 #define 和 #undef3.2 #if、#else、#elif 和 #endif3.3 #line3.4 #error 和 #warning3.5 #region 和 #endregion 四、高级应用&#xff1a;预处理器指令的最佳实践4.1 条件编译的最佳…
阅读更多...
PS从入门到精通视频各类教程整理全集，包含素材、作业等复发（2）

PS从入门到精通视频各类教程整理全集，包含素材、作业等复发（2）

PS从入门到精通视频各类教程整理全集&#xff0c;包含素材、作业等 最新PS以及插件合集&#xff0c;可在我以往文章中找到 由于阿里云盘有分享次受限制和文件大小限制&#xff0c;今天先分享到这里&#xff0c;后续持续更新 初级教程素材 等文件 https://www.alipan.com/s/fC…
阅读更多...
【edge浏览器无法登录某些网站，以及迅雷插件无法生效的解决办法】

【edge浏览器无法登录某些网站，以及迅雷插件无法生效的解决办法】

edge浏览器无法登录某些网站&#xff0c;以及迅雷插件无法生效的解决办法 edge浏览器无法登录某些网站&#xff0c;但chrome浏览器可以登录浏览器插件无法使用&#xff0c;比如迅雷如果重装插件重装浏览器重装迅雷后仍然出现问题 edge浏览器无法登录某些网站&#xff0c;但chro…
阅读更多...
【生活】如何学习理财

【生活】如何学习理财

文章目录 1. 了解基本财务知识2. 制定预算4321理财法则 3. 学习投资知识股票债券基金外汇房地产 4. 了解保险知识人身保险人寿保险健康保险意外伤害保险 财产保险财产损失保险责任保险信用保险 5. 寻求专业建议6. 持续学习和实践参考 首先我们想文心一言提问&#xff1a;如何学…
阅读更多...
二十二、软考-系统架构设计师笔记-真题解析-2018年真题

二十二、软考-系统架构设计师笔记-真题解析-2018年真题

软考-系统架构设计师-2018年上午选择题真题 考试时间 8:30 ~ 11:00 150分钟 1.在磁盘调度管理中&#xff0c;应先进行移臂调度&#xff0c;再进行旋转调度。假设磁盘移动臂位于21号柱面上&#xff0c;进程的请求序列如下表所示。如果采用最短移臂调度算法&#xff0c;那么系统…
阅读更多...
EXCEL VBA根据表数据写入数据库中

EXCEL VBA根据表数据写入数据库中

EXCEL VBA根据表数据写入数据库中 Option Explicithttps://club.excelhome.net/thread-1687531-1-1.htmlSub UpdateAccess()Const adStateOpen 1Dim vData, i As Variant, j As LongDim AccessTable As String, ExcelTable As String, ExcelFile As String, AccessFile As Str…
阅读更多...
力扣.21. 合并两个有序链表(c语言）

力扣.21. 合并两个有序链表(c语言）

题目描述&#xff1a; 解题方法&#xff1a; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(!list1)return list2;if(!list2)return list1;struct ListNode* l1list1,*l2list2,*newheadNULL,*newtailNULL;while(l1&&l2){if(l…
阅读更多...
[羊城杯 2020]EasySer

[羊城杯 2020]EasySer

[羊城杯 2020]EasySer 进入页面&#xff0c;发现是ubuntuapache2&#xff0c;但是好像没啥用 尝试访问/robots.txt&#xff0c;得到 访问/star1.php/&#xff0c;查看源码&#xff0c;得到提示 一看就知道是ssrf&#xff0c;使用http://127.0.0.1/ser.php&#xff0c;得到…
阅读更多...
uniapp 微信小程序 前端登录流程

uniapp 微信小程序 前端登录流程

步骤&#xff1a; 1. 从uniapp button 中通过 getphonenumber 获取 encryptedData、iv 2. 调用 uni.login() 获取 wx code&#xff0c;然后用wx code 获取session_key、unionid 等信息&#xff08;老用户直接用union_id调后端登录接口即可&#xff0c;新用户需进行加密解密获…
阅读更多...
EXCEL通过VBA字典快速分类求和

EXCEL通过VBA字典快速分类求和

EXCEL通过VBA字典快速分类求和 汇总截图 Option ExplicitOption Explicit Sub answer3() Dim wb As Workbook Dim sht As Worksheet Set wb ThisWorkbook Set sht wb.Worksheets(2) Dim ss1 As Integer Dim ss2 As Integer Dim i As Integer Dim j As Integer j 1Dim aa()…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业