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

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.rhkb.cn/news/291487.html

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

相关文章

Typora for Mac/Win：让Markdown编辑更高效，创作更自由

Typora for Mac/Win：让Markdown编辑更高效，创作更自由

在数字化时代&#xff0c;文本编辑已成为我们日常生活与工作中的重要环节。Markdown作为一种轻量级标记语言&#xff0c;以其简洁、易读、易写的特性&#xff0c;受到了广大用户的喜爱。而Typora&#xff0c;作为一款专为Markdown设计的文本编辑器&#xff0c;更是让Markdown编…
阅读更多...
对接中泰极速行情 | DolphinDB XTP 插件使用教程

对接中泰极速行情 | DolphinDB XTP 插件使用教程

XTP 是中泰证券推出的高性能交易平台&#xff0c;专为专业投资者提供高速行情及交易系统&#xff0c;旨在提供优质便捷的市场接入通道。目前支持股票、基金、ETF、债券、期权等多个市场&#xff0c;可满足不同投资者需求。 基于 XTP 官方 C SDK&#xff0c;DolphinDB 开发了 X…
阅读更多...
【SAP2000】在框架结构中应用分布式面板荷载Applying Distributed Panel Loads to Frame Structures

【SAP2000】在框架结构中应用分布式面板荷载Applying Distributed Panel Loads to Frame Structures

在框架结构中应用分布式面板荷载 Applying Distributed Panel Loads to Frame Structures 使用"Uniform to Frame"选项,可以简单地将荷载用于更多样化的情况。 With the “Uniform to Frame” option, loads can be easily used for a greater diversity of situat…
阅读更多...
2024Web自动化测试的技术框架和工具有哪些？

2024Web自动化测试的技术框架和工具有哪些？

Web 自动化测试是一种自动化测试方式&#xff0c;旨在模拟人工操作对 Web 应用程序进行测试。这种测试方式可以提高测试效率和测试精度&#xff0c;减少人工测试的工作量和测试成本。在 Web 自动化测试中&#xff0c;技术框架和工具起着至关重要的作用。本文将介绍几种常见的 W…
阅读更多...
Fastjson配置消息转换器（时间格式问题）

Fastjson配置消息转换器（时间格式问题）

问题&#xff1a; 我们可以看见&#xff0c;日期的格式有点问题。 由于ArticleListVO类的createTime成员变量是Date类型&#xff0c;默认是由java的Jackson来处理&#xff0c;使用 ISO-8601 规范来处理日期时间格式。ISO-8601 是一种国际标准的日期时间表示法&#xff0c;例如&…
阅读更多...
Oracle中实现根据条件对数据的增删改操作——Merge Into

Oracle中实现根据条件对数据的增删改操作——Merge Into

一、需求描述 在我们进行项目开发的过程中&#xff0c;会遇到这样的场景&#xff0c;需要根据某个条件对数据进行增、删、改的操作&#xff1b;遇到这种情况我们有2种方法进行解决&#xff1a; 方法一&#xff1a;①查询指定条件&#xff1b;②根据查询出的指定条件结果在执行…
阅读更多...
conda配置完整的pytorch虚拟环境

conda配置完整的pytorch虚拟环境

新建环境 conda create -n py38 python3.8虚拟环境中安装CUDA&#xff0c;conda安装的cudatoolkit和NVIDIA提供的CUDA Toolkit不一样&#xff0c;前者是系统CUDA的子集。在虚拟环境中安装了cudatoolkit&#xff0c;则pytorch就会用虚拟环境中的cudatoolkit进行编译。注意cudato…
阅读更多...
Centos安装部署

Centos安装部署

Centos安装部署 linux安装JDK 下载地址&#xff1a;https://www.oracle.com/java/technologies/oracle-java-archive-downloads.html 创建文件夹&#xff0c;输入命令&#xff1a; mkdir /usr/local/jdk 查看JDK信息&#xff0c;输入命令&#xff1a; java -version 将下载的…
阅读更多...
配置visual studio code 用秘钥远程连接SSH服务器

配置visual studio code 用秘钥远程连接SSH服务器

配置visual studio code 用秘钥远程连接SSH服务器 文章目录 配置visual studio code 用秘钥远程连接SSH服务器简介1. 生成SSH密钥对2. 将公钥添加到Ubuntu服务器3. 将私钥添加到visual studio code的SSH配置文件中 简介 通过SSH密钥认证&#xff0c;用户无需在每次连接时输入密…
阅读更多...
C++11 shared_from_this学习

C++11 shared_from_this学习

最近学习网络变成发现一些C源码库中封装对象时会公有继承enable_shared_from_this&#xff1b; 用一个案例进行说明&#xff0c;案例代码如下&#xff1a; #include <iostream> #include <memory> #include <stdio.h>using namespace std;class C : public…
阅读更多...
谈一谈BEV和Transformer在自动驾驶中的应用

谈一谈BEV和Transformer在自动驾驶中的应用

谈一谈BEV和Transformer在自动驾驶中的应用 BEV和Transformer都这么火&#xff0c;这次就聊一聊。 结尾有资料连接 一 BEV有什么用 首先&#xff0c;鸟瞰图并不能带来新的功能&#xff0c;对规控也没有什么额外的好处。 从鸟瞰图这个名词就可以看出来&#xff0c;本来摄像头…
阅读更多...
啥是MCU，MCU科普

啥是MCU，MCU科普

啥是MCU&#xff0c;MCU科普 附赠自动驾驶学习资料和量产经验&#xff1a;链接 MCU是Microcontroller Unit 的简称&#xff0c;中文叫微控制器&#xff0c;俗称单片机&#xff0c;是把CPU的频率与规格做适当缩减&#xff0c;并将内存、计数器、USB、A/D转换、UART、PLC、DMA等…
阅读更多...
剑指Offer题目笔记21（计数排序）

剑指Offer题目笔记21（计数排序）

面试题74&#xff1a; 问题&#xff1a; ​ 输入一个区间的集合&#xff0c;将重叠的区间合并。 解决方案&#xff1a; ​ 先将所有区间按照起始位置排序&#xff0c;然后比较相邻两个区间的结束位置就能知道它们是否重叠。如果它们重叠就将它们合并&#xff0c;然后判断合并…
阅读更多...
VS Code常用前端开发插件和基础配置

VS Code常用前端开发插件和基础配置

VS Code插件安装 VS Code提供了非常丰富的插件功能&#xff0c;根据你的需要&#xff0c;安装对应的插件可以大大提高开发效率。 完成前端开发&#xff0c;常见插件介绍&#xff1a; 1、Chinese (Simplified) Language Pack 适用于 VS Code 的中文&#xff08;简体&#xff…
阅读更多...
再次加深理解Java中的并发编程

再次加深理解Java中的并发编程

目录 一、线程、进程、程序 二、线程状态 三、线程的七大参数 四、lock与synchronized锁机制 一&#xff09;、lock与synchronized锁区别 二&#xff09;、synchronized锁原理 三&#xff09;、Lock锁原理 五、synchronized锁升级原理 一&#xff09;、锁升级基础知识 …
阅读更多...
AIGC重塑金融：AI大模型驱动的金融变革与实践

AIGC重塑金融：AI大模型驱动的金融变革与实践

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-tVrfBkGvUD0Qi13F {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…
阅读更多...
【微服务】配置Nacos管理SpringBoot配置文件（附解压包）

【微服务】配置Nacos管理SpringBoot配置文件（附解压包）

&#x1f4dd;个人主页&#xff1a;哈__ 期待您的关注 一、什么是Nacos Nacos可以帮助我们配置和管理微服务&#xff0c;是阿里的一个开源产品&#xff0c;是针对微服务架构中的服务发现、配置管理、服务治理的综合型解决方案。Nacos可以用来实现配置中心和服务注册中心。 …
阅读更多...
我国伺服系统市场规模逐渐扩大 未来有望实现完全国产替代

我国伺服系统市场规模逐渐扩大 未来有望实现完全国产替代

我国伺服系统市场规模逐渐扩大 未来有望实现完全国产替代 伺服系统又称为随动系统&#xff0c;是用于精确地跟随或复现某个过程的反馈控制系统。伺服系统主要包括驱动器、指令机构和电机等&#xff0c;可根据控制指令&#xff0c;对功率进行放大、变换与调控等处理&#xff0c;…
阅读更多...
Jackson 2.x 系列【6】注解大全篇二

Jackson 2.x 系列【6】注解大全篇二

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Jackson 版本 2.17.0 源码地址&#xff1a;https://gitee.com/pearl-organization/study-jaskson-demo 文章目录 注解大全2.11 JsonValue2.12 JsonKey2.13 JsonAnySetter2.14 JsonAnyGetter2.15 …
阅读更多...
QT 最近使用的项目配置文件

QT 最近使用的项目配置文件

目录 1 QT 最近使用的项目配置文件所在路径 2 QtCreator.ini 1 QT 最近使用的项目配置文件所在路径 C:\Users\your username\AppData\Roaming\QtProject QtCreator.ini最好先备份一份 2 QtCreator.ini ProjectExplorer 下面的 RecentProjects\FileNames RecentProjects\…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023