集合实现类研究底层（部分）：手撕ArrayList底层源码、手撕LinkedList底层源码、手写单向链表和双向链表

day26上

集合框架图

标绿已经学习底层，深入底层主要是研究实现类底层
集合框架图上

继承关系图

继承关系图

手撕ArrayList底层源码

ps:研究添加元素的过程

思路：

1.研究继承关系

2.研究属性

3.理解创建集合的过程 – 构造方法的底层原理

4.研究添加元素的过程

提升：

1.研究删除集合的过程

2.研究遍历集合的过程

场景
	//ArrayList<String> list = new ArrayList<>();
	ArrayList<String> list = new ArrayList<>(10000);
	
	list.add("aaa");
	list.add("bbb");
	list.add("ccc");
	list.add("ddd");

底层

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    //回顾：其中抽象类的构造方法由子类调用
    
    //外部操作数（记录添加和删除的次数）
    protected transient int modCount = 0;//最终4
}

额外补充：
    //空数据，没有对象，输出长度为空指针异常
    private static final Object[] EMPTY_ELEMENTDATA = null;    
    //空内容的数组，有对象，输出长度为0
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //默认容量的空内容的数组，有对象，（后面两个对象不同）
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    

public class ArrayList<E> extends AbstractList<E> implements List<E>{
    //默认初始化容量
    private static final int DEFAULT_CAPACITY = 10;
    //空内容的数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //默认容量的空内容的数组
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //数据容器最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    //数据容器 - [“aaa”,"bbb","ccc","ddd",null,null,null,null,null,null]
    transient Object[] elementData;//new Object[10];
    //元素个数
    private int size;//最终4
    
    //无参构造，默认容量的空内容的数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //有参构造，初始化容量
    //initialCapacity - 10000
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }
    
    //e - 最终"ddd"
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;//添加一个元素size+1
        return true;
    }
    
    //minCapacity - 10--11（超）
    private void ensureCapacityInternal(int minCapacity) {
        //使用无参构造创建ArrayList，第一次添加元素时进入的判断
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //minCapacity =  Math.max(10, 1);
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
    
    //minCapacity - 10--11（超）
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 有溢出意识的代码（准备扩容的长度必须大于数据容器的长度）
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    //minCapacity - 10--11（超）
    private void grow(int minCapacity) {
        // oldCapacity - 10
        int oldCapacity = elementData.length;
        // newCapacity - 15，超过默认容量，开始扩容
        int newCapacity = oldCapacity + (oldCapacity >> 1);//ArrayList的扩容机制（1.5倍）
        if (newCapacity - minCapacity < 0)
            //newCapacity-10，没有超过默认容量
            newCapacity = minCapacity;
        //当超过最大容量Integer.MAX_VALUE-8
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //内存中一般不会存很多数据，一般几万都很多了，后面会讲解大量数据的处理情况
    //其他地方调用，minCapacity可能为负
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //minCapacity > 0
        return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
    }
    
}

面试题

ArrayList的数据结构是什么？

Object类型的一维数组

ArrayList默认初始化容量是多少？

10

ArrayList最大容量是多少？

Integer.MAX_VALUE-8

ArrayList最大容量为什么是Integer.MAX_VALUE-8？

减8是为了腾出空间存放数组的头部信息

ArrayList扩容机制是什么？

扩容后的长度是原来长度的1.5倍

如何减少集合的伸缩性及其目的是什么？

根据需求判断元素大概的长度，在创建集合时指定长度，减少扩容次数，提高效率

手撕LinkedList底层源码

ps:研究添加元素的过程

思路：

1.研究继承关系

2.研究属性

3.理解创建集合的过程 – 构造方法的底层原理

4.研究添加元素的过程

提升：

1.研究删除集合的过程

2.研究遍历集合的过程

场景：
    LinkedList<String> list = new LinkedList<>();
		
	list.add("小小");
	list.add("奇男子");
	list.add("大大");

底层

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    //外部操作数（记录添加和删除的次数）
    protected transient int modCount = 0;//0
}

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
}

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>{
    //元素个数
    transient int size = 0;//0
    //首节点
    transient Node<E> first;//null
	//尾节点
    transient Node<E> last;//null
    
    public LinkedList() {
    }//new对象，系统赋默认值
    
    //添加在inkLast()，所以研究linkLast()
    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++;
        modCount++;
    }
    
    //回顾：静态内部类应用场景（此处不需要调用外部类的成员属性）
    //节点类
    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;
        }
    }
    
}

节点对象理解图

在这里插入图片描述

补充：双向链表【站在数据结构的角度：结点】【站在java底层的角度：节点】

LinkedList理解图

LinkedList理解图

添加过程解析

第一次添加：

LinkLast（）

1.首先e-小小，l = last为null

2.newNode对象（l，e，null）找到第一个节；所以第一个节点为【0x001】

3.然后last =newNode【0x001】

4.然后判断条件，first = newNode【0x001】

5.然后size++，变成1；modCount++变成1

第二次添加：

重新LinkLast（）

e；l；newNode重新赋值

1.首先e-奇男子，l = last为0x001（上一个节点地址即赋值给下一个首节点，第二个节点的首节点可以找到上一个节点）

2.newNode对象（l，e，null）找到第二个节；所以第二个节点为【0x002】；

3.然后last =newNode【0x002】

4.然后判断条件，l.next = newNode【0x002】（下一个节点地址即赋值给上一个尾节点，上一个节点可以找到下一个节点）

5.然后size++，变成2；modCount++变成2

第三次添加：

重新LinkLast（）

e；l；newNode重新赋值

1.首先e-奇男子，l = last为0x002（上一个节点地址即赋值给下一个首节点，第二个节点的首节点可以找到上一个节点）

2.newNode对象（l，e，null）找到第二个节；所以第二个节点为【0x003】；

3.然后last =newNode【0x003】

4.然后判断条件，l.next = newNode【0x003】（下一个节点地址即赋值给上一个尾节点，上一个节点可以找到下一个节点）

5.然后size++，变成3；modCount++变成3

面试题

LinkedList底层数据结构是什么？

双向链表

ArrayList 和 LinkedList的效率区别：

​ ArrayList底层：一维数组

​ LinkedList底层：双向链表

​ 添加数据 – ArrayList扩容的情况：LinkedList快

​ 添加数据 – ArrayList不扩容的情况：ArrayList快（size指针指哪里添加到哪里）

​ 查询数据：ArrayList快（ArrayList下标查找，LinkedList需要遍历数据 ）

​ 删除数据：LinkedList快（ArrayList删除要往前移动元素，LinkedList删除只要断链接添链接）

​ 修改数据：ArrayList快（修改需要先查询）

补充：平时我们一般使用ArrayList，是因为众多业务中查询功能使用最为频繁，而ArrayList查询功能比LinkedList更快，所以我们选择使用ArrayList会更多

LinkedList如何实现删除？

​ 1.通过下标找到要删除的节点

​ 2.把要删除的节点的下一个节点地址赋值给上一个节点的next

​ 3.把要删除的节点的上一个节点地址赋值给下一个节点的prev

手写单向链表和双向链表

手写单向链表

简单实现

粗略思路：

节点（元素，下一个节点，有参构造）

首节点，尾节点，size

添加（new节点，判断赋值给节点相应位置）

遍历 迭代器 方法实现（仿写底层）判断有没有元素，获取下一个元素

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

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

手写双向链表

简单实现

粗略思路：

节点（上一个节点，元素，下一个节点，有参构造）

首节点，尾节点，size

添加（获取上一个节点，new节点，判断赋值给节点相应位置）

遍历 迭代器 方法实现（仿写底层）判断有没有元素，获取下一个元素

package com.qf.bidirectional_linked_list;

import java.util.Iterator;

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

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

总结

手撕实现类

1.手撕ArrayList底层源码
2.手撕LinkedList底层源码
ArrayList 和 LinkedList的效率区别
手写单向链表
手写双向链表

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

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

相关文章

变换，动画

变换，动画

面试题——需求&#xff1a;在不知道父元素与子元素的宽高时 如何让子元素在父元素内居中&#xff1f; 1.定位 父相子绝 2.子元素 top&#xff1a;50% left:50% 3.子元素 transform: translate(-50%,-50%) .parent{height: 500px;background-color: red;position: relative;}.c…
阅读更多...
算法第二十五天-寻找排序数组中的最小值

算法第二十五天-寻找排序数组中的最小值

寻找排序数组中的最小值 题目要求 解题思路 二分法 代码 class Solution:def findMin(self, nums: List[int]) -> int:low, high 0, len(nums) - 1while low < high:pivot low (high - low) // 2if nums[pivot] < nums[high]:high pivot else:low pivot 1re…
阅读更多...
微信小程序-可以用区域

微信小程序-可以用区域

简介 movable-view和movable-area是可移动的视图容器&#xff0c;在页面中可以拖拽滑动。 本篇文章将会通过该容器实现一个常用的拖拽按钮功能。 使用效果 代码实现 side-view.wtml 布局见下面代码&#xff0c;left view为内容区域&#xff0c;right view为操作按钮&a…
阅读更多...
进腾讯工作一个月，我想辞职了......

进腾讯工作一个月，我想辞职了......

前几天&#xff0c;我在网上看到一个微博。 一个应届的校招生&#xff0c;目前入职腾讯&#xff0c;工作了一个月。这一个月给他的感受是大量的写测试用例&#xff0c;自己写测试用例的能力熟练了不少&#xff0c;测试技能倒是没有多大的提高&#xff0c;真正需要技术的工作却…
阅读更多...
算法学习01：排序二分

算法学习01：排序二分

算法学习01&#xff1a;排序&&二分 文章目录 算法学习01&#xff1a;排序&&二分前言需要记忆的模版&#xff1a;快速排序归并排序&#xff1a;整数二分&#xff1a;浮点数二分 一、排序1.快速排序2.归并排序&#xff1a; 二、二分1.整数2.浮点数 总结 前言 需要…
阅读更多...
汽车协议学习

汽车协议学习

ⅠOBD 1.OBD接口 OBD有16个引脚&#xff0c;每个引脚的电压不同&#xff08;可以对应不同的协议&#xff09; 车端&#xff1a; 16- 9 (短一点点的) 8-1 &#xff08;长一点的&#xff09; 2.基于OBDⅡ的通信协议 CAN &#xff08;ISO-15765&am…
阅读更多...
grafana table合并查询

grafana table合并查询

注&#xff1a;本文基于Grafana v9.2.8编写 1 问题 默认情况下table展示的是一个查询返回的多个field&#xff0c;但是我想要的数据在不同的metric上&#xff0c;比如我需要显示某个pod的读写IO&#xff0c;但是读和写这两个指标存在于两个不同的metirc&#xff0c;需要分别查…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：Marquee）

鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：Marquee）

跑马灯组件&#xff0c;用于滚动展示一段单行文本。仅当文本内容宽度超过跑马灯组件宽度时滚动&#xff0c;不超过时不滚动。 说明&#xff1a; 该组件从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 Ma…
阅读更多...
一元函数微分学——刷题（26

一元函数微分学——刷题（26

目录 1.题目&#xff1a;2.解题思路和步骤&#xff1a;3.总结&#xff1a;小结&#xff1a; 1.题目&#xff1a; 2.解题思路和步骤&#xff1a; 归纳求解&#xff0c;把指数写成负数就比较容易看出来规律 3.总结&#xff1a; 归纳求解&#xff0c;把指数写成负数就比较容易…
阅读更多...
【蓝桥杯】k倍区间

【蓝桥杯】k倍区间

一.题目描述 二.问题分析 对于该问题&#xff0c;标签上写的是暴力&#xff0c;但是如果使用暴力的话&#xff0c;会超时。 首先&#xff0c;对于两个数a&#xff0c;b&#xff08;假设a小于b&#xff09;&#xff0c;若a与b对k取余后结果相同&#xff0c;则b-a可以整除k。 …
阅读更多...
axios的详细使用

axios的详细使用

目录 axios&#xff1a;现代前端开发的HTTP客户端王者 一、axios简介 二、axios的基本用法 1. 安装axios 2. 发起GET请求 3. 发起POST请求 三、axios的高级特性 1. 拦截器 2. 取消请求 3. 自动转换JSON数据 四、axios在前端开发中的应用 五、总结 axios&#xff1a…
阅读更多...
山泉还可以申请商标不，现阶段通过率如何！

山泉还可以申请商标不，现阶段通过率如何！

在32类类别啤酒饮料是许多生产水企业主要申请注册的类别&#xff0c;那现在山泉在这个类别还可以申请注册商标不&#xff0c;山泉在这个类别基本上是通用词&#xff0c;首先是需要前面词具有显著性&#xff0c;没的相同或近似才可以。 经普推知产老杨检索发现&#xff0c;在32…
阅读更多...
作业 字符数组-统计和加密

作业 字符数组-统计和加密

字串中数字个数 描述 输入一行字符&#xff0c;统计出其中数字字符的个数。 输入 一行字符串&#xff0c;总长度不超过255。 输出 输出为1行&#xff0c;输出字符串里面数字字符的个数。 样例 #include <iostream> #include<string.h> using namespace std; int m…
阅读更多...
瑞_JVM虚拟机_类的生命周期

瑞_JVM虚拟机_类的生命周期

文章目录 1 JVM虚拟机概述2 类的生命周期2.1 加载阶段2.1.1 加载过程2.1.2 查看内存中的对象&#xff08;hsdb工具&#xff09; 2.2 连接阶段2.2.1 验证2.2.2 准备&#xff08;final特殊&#xff09;2.2.3 解析 2.3 初始化阶段\<client> ★★★2.4 使用阶段2.5 卸载阶段 …
阅读更多...
不愧是华为出来的，太厉害了...

不愧是华为出来的，太厉害了...

实习去了博彦科技&#xff08;外包&#xff09;&#xff0c;做的就是螺丝钉的活&#xff0c;后面还因为人效不佳&#xff0c;被开了。 正式毕业后去了另外一个做电子发票的公司&#xff0c;但是都是功能测试和一点点APP测试&#xff0c;然后经常被开发怼&#xff0c;测试毫无地…
阅读更多...
筛选出等于1的式子

筛选出等于1的式子

然后统计和归类 归类分行归类方法 算术符号归类 数字大小排序算术符号归类 import randomdef generate_expression(num_range, num_count, operators):nums random.sample(range(num_range[0], num_range[1]1), num_count)ops random.choices(operators, knum_count-1)expre…
阅读更多...
考研复试要想顺利通关，务必掌握的一些问题

考研复试要想顺利通关，务必掌握的一些问题

亲爱的学弟学妹们&#xff0c;大家好&#xff01; 我是研一的学姐&#xff0c;深知考研路上的艰辛与不易。如今&#xff0c;为了回馈广大考研学子&#xff0c;我决定将自己精心整理的考研复试资料拿出来与大家分享&#xff0c;希望能为你们的复试之路添砖加瓦&#xff0c;助你…
阅读更多...
JS直接量及其相关对象

JS直接量及其相关对象

什么是直接量 直接量是指不需要创建对象就可以直接使用的变量。ES中的直接量主要有三种类型&#xff1a;表示字符串的string类型、表示数字的number类型和表示true/false的boolean类型。当我们直接将值赋给变量后&#xff0c;ES就会自动判断其类型&#xff0c;而且当参数发生变…
阅读更多...
vulhub中Weblogic ＜ 10.3.6 ‘wls-wsat‘ XMLDecoder 反序列化漏洞（CVE-2017-10271）复现

vulhub中Weblogic ＜ 10.3.6 ‘wls-wsat‘ XMLDecoder 反序列化漏洞（CVE-2017-10271）复现

Weblogic的WLS Security组件对外提供webservice服务&#xff0c;其中使用了XMLDecoder来解析用户传入的XML数据&#xff0c;在解析的过程中出现反序列化漏洞&#xff0c;导致可执行任意命令。 访问http://your-ip:7001/即可看到一个404页面&#xff0c;说明weblogic已成功启动 …
阅读更多...
缩放算法优化步骤详解

缩放算法优化步骤详解

添加链接描述 背景 假设数据存放在在unsigned char* m_pData 里面&#xff0c;宽和高分别是&#xff1a;m_nDataWidth m_nDataHeight 给定缩放比例&#xff1a;fXZoom fYZoom&#xff0c;返回缩放后的unsigned char* dataZoom 这里采用最简单的缩放算法即&#xff1a; 根据比…
阅读更多...
最新文章

Copyright @ 2022~2023