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 GC
    first = next; // 将下一个节点设置为头节点
    if (next == null) {
        last = null; // 如果下一个节点为空，将尾节点置空
    } else {
        next.prev = null; // 将下一个节点的前驱节点置空
    }
    size--; // 元素数量减1
    return 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;
		
		@Override
		public boolean hasNext() {
			return cursor != size;
		}

		@Override
		public 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;
		
		@Override
		public boolean hasNext() {
			return cursor != size;
		}

		@Override
		public 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理解图：
在这里插入图片描述

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

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

相关文章

微机原理-基于8086倒计时多路抢答器系统

微机原理-基于8086倒计时多路抢答器系统

**单片机设计介绍&#xff0c;微机原理-基于8086倒计时多路抢答器系统 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 微机原理-基于8086倒计时多路抢答器系统概要主要关注于利用8086微处理器设计和实现一个具有倒计时功能的多路抢答器系统…
阅读更多...
总结UDP协议各类知识点

总结UDP协议各类知识点

前言 本篇博客博主将详细地介绍UDP有关知识点&#xff0c;坐好板凳发车啦~ 一.UDP特点 1.无连接 UDP传输的过程类似于发短信&#xff0c;知道对端的IP和端口号就直接进行传输&#xff0c;不需要建立连接&#xff1b; 2.不可靠传输 没有任何的安全机制&#xff0c;发送端发…
阅读更多...
MySQL Innodb 引擎中预防 Update 操作上升为表锁

MySQL Innodb 引擎中预防 Update 操作上升为表锁

一、MySQL 如何预防 Update 上升为表锁 在 MySQL 中&#xff0c;进行任何数据的 修改 操作都会进行一定的锁操作&#xff0c;而锁的不同直接导致性能的差异。例如 MyISAM 引擎&#xff0c;更新时采用表锁&#xff0c;并发性较差。而 Innodb 引擎支持事务&#xff0c;更新时采用…
阅读更多...
c++调用阿里云短信服务

c++调用阿里云短信服务

&#x1f482; 个人主页:pp不会算法^ v ^ &#x1f91f; 版权: 本文由【pp不会算法v】原创、在CSDN首发、需要转载请联系博主 &#x1f4ac; 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦 购买套餐包 申请资质 申请模板 申请签名 上面这些审核通过之后 添…
阅读更多...
低代码平台与自动化软件开发的关系

低代码平台与自动化软件开发的关系

引言 随着信息技术的不断发展&#xff0c;软件开发领域也在不断演进。在追求更高效、更快速的软件开发过程中&#xff0c;低代码平台和自动化软件开发技术日益受到关注。低代码平台以其可视化开发界面和快速构建应用的能力&#xff0c;为非专业开发人员提供了参与软件开发的机会…
阅读更多...
预处理详解(一) -- 预定义符号与#define定义

预处理详解(一) -- 预定义符号与#define定义

目录 一. 预定义符号二. #define1.#define定义常量2.#define定义宏3.带有副作用的宏参数4.宏替换的规则5.宏和函数的对比 一. 预定义符号 %s _ _FILE_ _ //文件 %s _ _ DATE_ _ //日期 %s _ _ TIME_ _ //时间 %d _ _ LINE_ _ //行号 %d _ _ STDC_ _ //如果编译器支持 ANSI C,那…
阅读更多...
【Vue】动态样式

【Vue】动态样式

内联样式的动态样式 body(){ boxASelect:false, } v-bind:style"{borderColor:boxASelect ? red : #ccc}" <body><header><h1>Vue Dynamic Styling</h1></header><section id"styling"><div class"demo&quo…
阅读更多...
kubernetes(K8S)学习（七）：K8S之系统核心组件

kubernetes(K8S)学习（七）：K8S之系统核心组件

K8S之系统核心组件 K8s系统核心组件1.1 Master和Node1.2 kubeadm1.3 先把核心组件总体过一遍1.4 Kubernetes源码查看方式1.5 kubectl1.6 API Server1.7 集群安全机制之API Server1.8 Scheduler1.9 kubelet1.10 kube-proxy K8s系统核心组件 1.1 Master和Node 官网 &#xff1a;…
阅读更多...
蓝桥杯刷题-重新排序

蓝桥杯刷题-重新排序

重新排序 差分&#xff1a; s,d [0]*100010,[0]*100010 tmp 0 n int(input()) a list(map(int,input().split())) a.insert(0,0) for i in range(1,n1):s[i] s[i-1] a[i] m int(input()) for _ in range(m):l,r map(int,input().split())# [l,r]的和tmp s[r] - s[l-1…
阅读更多...
【AI】命令行调用大模型

【AI】命令行调用大模型

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 【AI】命令行调用大模型引入正文初始化项目撰写脚本全局安装 成果展示 【AI】命令…
阅读更多...
基于Spring Boot的在线学习系统的设计与实现

基于Spring Boot的在线学习系统的设计与实现

基于Spring Boot的在线学习系统的设计与实现 摘 要 在线学习系统是以大学传统线下教学方式不适应信息技术的迅速发展为背景&#xff0c;提高学习效率&#xff0c;解决传统教学问题&#xff0c;并且高效的实现教学信息化的一款软件系统。为了更好的实现对于教学和学生的管理&a…
阅读更多...
【C++进阶】多态，带你领悟虚函数和虚函数表

【C++进阶】多态，带你领悟虚函数和虚函数表

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;c大冒险 总有光环在陨落&#xff0c;总有新星在闪烁 【本节目标】 1. 多态的概…
阅读更多...
实验一 Python集成开发环境的搭建及可视化库的安装

实验一 Python集成开发环境的搭建及可视化库的安装

一、安装集成开发环境 下载安装包 官方网址&#xff1a; Free Download | Anaconda 或者镜像网站下载&#xff08;较快&#xff09; https://repo.anaconda.com/archive/ 安装 配置环境变量 验证 输入&#xff1a; conda -V 二、下载pyecharts环境 点击 Anaconda Promp…
阅读更多...
C++树状数组 (原理 + 代码 + lowbit解释)

C++树状数组 (原理 + 代码 + lowbit解释)

目录: 什么是树状数组&#xff1f; 代码模板 原理 lowbit解释 什么是树状数组&#xff1f; 树状数组作为一种高效的数据结构&#xff0c;可以在O(logn)内完成更新和查询操作&#xff0c;因此非常适合加减&#xff0c; 区间和&#xff0c; 查询。 适合问题&#xff1a;…
阅读更多...
【YOLOv8 代码解读】数据增强代码梳理

【YOLOv8 代码解读】数据增强代码梳理

1. LetterBox增强 当输入图片的尺寸和模型实际接收的尺寸可能不一致时&#xff0c;通常需要使用LetterBox增强技术。具体步骤是先将图片按比例缩放&#xff0c;将较长的边缩放到设定的尺寸以后&#xff0c;再将较短的边进行填充&#xff0c;最终短边的长度为stride的倍数即可。…
阅读更多...
Web APIs知识点讲解(阶段五)

Web APIs知识点讲解(阶段五)

DOM- 网页特效篇 一.课前回顾(手风琴) <!DOCTYPE html> <html><head lang"en"><meta charset"UTF-8"><title>手风琴</title><style>ul {list-style: none;}* {margin: 0;padding: 0;}div {width: 1200px;heig…
阅读更多...
Mysql从0到1 —— CRUD/索引/事务

Mysql从0到1 —— CRUD/索引/事务

文章目录 1 预备知识1.1 安装1.2 登录 & 退出1.3 配置文件my.cnf 2 基础知识2.1 链接服务器2.2 什么是数据库2.3 基本使用2.3.1创建表2.3.2 插入数据 2.4 服务器、数据库、表的关系2.5 SQL分类2.6 存储引擎 3 Mysql数据库的操作3.1 创建和删除3.2 字符集和校验规则3.3 查看…
阅读更多...
WinServer启用Hyper-V新建虚拟机没有网络、无法开启增强模式、开启远程连接功能

WinServer启用Hyper-V新建虚拟机没有网络、无法开启增强模式、开启远程连接功能

没有网络问题如下&#xff1a; 原因&#xff1a;没有在Hyper-V中新增交换机 操作—虚拟交换机管理器—新建虚拟网络交换机-外部-允许管理员操作系统共享此网络适配器 无法开启增强模式&#xff1a; 开启远程连接功能 或者&#xff1a;
阅读更多...
蓝桥杯keil软件添加stc芯片

蓝桥杯keil软件添加stc芯片

打开烧录软件&#xff0c;点击Keil仿真设置&#xff0c;点击勾选出来的选项 将文件放入keil软件放的地址&#xff0c;放入C51这个文件夹&#xff0c;再点击确认 打开keil软件&#xff0c;点击Project&#xff0c;选择第一个 选择一个空文件夹&#xff0c;输入文件名&#xff0c…
阅读更多...
Python基础之Class类的定义、继承、多态

Python基础之Class类的定义、继承、多态

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、class类1.类属性操作&#xff08;增删改&#xff09;2.类方法操作 二、类的继承1、语法2、方法重写 二、类的多态 一、class类 、三部分组成 1、类名&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023