当前位置: 首页 > news >正文

顺序表、链表(ArrayList、LinkedList)

目录

前言:

顺序表(ArrayList):

顺序表的原理:

ArrayList源码: 

的含义:​编辑

ArrayList的相关方法:​编辑

向上转型List: 

练习题(杨辉三角): 

扑克牌游戏:

链表(LinkedList): 

链表的原理:

自定义链表的实现:

LinkedList源码: 

LinkedList使用注意事项: 

练习题(判断是否是会问链表): 

迭代器(Iterator): 

总结: 


前言:

        本篇我们来讲解数据结构中的顺序表和顺序表,因为Java有集合框架,所以可以直接使用类创建对象来完成。

顺序表(ArrayList):

顺序表的原理:

        顾名思义,就是有顺序的表,类是ArrayList,底层原理是一个数组,当到达最大容量时,会进行扩容。

        当一个数组(顺序表)中存放的基本类型数据时,我们想要全部清除可以直接将有效下标置为0,这样再添加就是覆盖的效果。

        但是如果数组中存放的是引用类型,则不能这样。因为基本类型都会默认初始化,比如整形会默认初始化为0。

        此时引用类型不能直接将有效下标置为0,否则会发生内存泄漏。 因为引用类型开辟的空间没有回收,JVM中,回收算法有很多。最好通过for循环来置空。

for() {elem[i] = null;
}

ArrayList源码: 

        接下来我们就来细致观察ArrayList源码: ArrayList底层就是顺序表,继承了AbstractList类,里面重写了toString方法。

        ArrayList底层就是顺序表,继承了AbstractList类,里面重写了toString方法。

public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(0,99);for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i) + " ");}System.out.println(list);
}

        ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表。

        我们再来看源码:

        此时就分配了10个空间。 

        所以当使用无参构造器时,第一次添加元素是申请10个空间,之后每次到达上限以后就扩容1.5倍。

<? extends E>的含义:

         因为ArrayList实现了Collection接口。

public class Test {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);ArrayList<Number> list1 = new ArrayList<>(list);list1.add(99);list1.add(88);System.out.println(list1);}
}

ArrayList的相关方法:

public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);ArrayList<Number> list1 = new ArrayList<>();list1.addAll(list);list1.remove(new Integer(2));//删除指定对象System.out.println(list1);}

        我们来观察一下代码: 

public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);List<Integer> list1 = list.subList(1, 3);//[1,3)list1.set(1,99);System.out.println(list);System.out.println(list1);
}

向上转型List: 

List<List<Integer>> list1 = new ArrayList<>();
list1.add(new ArrayList<>());
list1.add(new ArrayList<>());

        观察这个代码,意思其实是有一个ArrayList类,每一个元素里面是一个ArrayList存放整形的引用类型(List是一个接口)。其实可以理解为二维数组。

练习题(杨辉三角): 

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> list = new ArrayList<>();list.add(1);ret.add(list);for (int i = 1; i < numRows; i++) {List<Integer> cur = new ArrayList<>();cur.add(1);//获取上一行List<Integer> prev = ret.get(i - 1);for (int j = 1; j < i; j++) {int val = prev.get(j) + prev.get(j - 1);cur.add(val);}//将此行最后一个元素置为1cur.add(1);ret.add(cur);}return ret;}
}

扑克牌游戏:

public class Test {public static void main(String[] args) {CardDome cardDome = new CardDome();List<Card> cardList = cardDome.buyCard();System.out.println("买的牌如下:");System.out.println(cardList);System.out.println("洗牌");cardDome.shuffle(cardList);System.out.println(cardList);System.out.println("揭牌:");cardDome.getCards(cardList);}
}
public class CardDome {//定义四种花色private static final String[] suits = {"♥","♣","♦","♠"};//52张//J - 11  Q - 12  K - 13//买一副牌public List<Card> buyCard() {List<Card> cardList = new ArrayList<>();for (int i = 0; i < 4; i++) {for (int j = 1; j <= 13; j++) {Card card = new Card(suits[i], j);cardList.add(card);}}return cardList;}//洗牌public void shuffle(List<Card> cardList) {//生成随机数Random random = new Random();//从后向前打乱for (int i = cardList.size() - 1; i > 0; i--) {//有52张牌//第一次生成的就是 0 - 50 的随机数int index = random.nextInt(i);//index i 交换swap(cardList, i, index);}}private void swap(List<Card> cardList, int e1,int e2) {Card tmp = cardList.get(e1);cardList.set(e1,cardList.get(e2));cardList.set(e2,tmp);}//揭牌public void getCards (List<Card> cardList) {//3个人List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<Card> hand3 = new ArrayList<>();List<List<Card>> hand = new ArrayList<>();hand.add(hand1);hand.add(hand2);hand.add(hand3);//3个人轮流抓牌5张牌for (int i = 0; i < 5; i++) {//j 代表人for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);hand.get(j).add(card);}}System.out.println("第一个人揭牌如下:");System.out.println(hand1);System.out.println("第二个人揭牌如下:");System.out.println(hand2);System.out.println("第三个人揭牌如下:");System.out.println(hand3);System.out.println("剩下的牌:");System.out.println(cardList);}
}
public class Card {private String suit;//花色private int rank;//数字public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public int getRank() {return rank;}public void setRank(int rank) {this.rank = rank;}@Overridepublic String toString() {return suit + ":" + rank + " ";}
}

链表(LinkedList): 

链表的原理:

        顺序表还是有缺点的,因为每次都是1.5倍扩容,所以有时量大时就会浪费内存,所以就衍生出了链表,不是连续内存,如果了解C语言中的链表,那么将是易如反掌。

自定义链表的实现:

        我们定义head成员,是为了保存头结点。

public class MySingleList {//节点使用内部类来写static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//定义一个链表的成员的头结点public ListNode head;public void createList() {ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(33);ListNode node3 = new ListNode(99);ListNode node4 = new ListNode(67);ListNode node5 = new ListNode(88);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}
}

LinkedList源码: 

        LinkedList的底层代码,可以发现这就是一个双向循环链表。 LinkedList的任意位置插入和删除元素师效率比较高,时间复杂度为O(1),比较适合任意位置插入的场景。

        还有很多方法无法注意介绍,大家可以看Structure里面的所有相关方法、属性和内部类。因为效率高,所以底层只使用了双向链表,没有使用单向链表。

LinkedList使用注意事项: 

        当我们使用的是自定义链表时(就是没用Java框架),清空链表,可以直接将头尾置空,也可以逐个将其置空。因为Java有回收算法。

        这里我们使用迭代器进行遍历,我们也可以反向遍历: 

public class Test2 {public static void main(String[] args) {LinkedList<Integer> linkedList = new LinkedList<>();linkedList.add(1);linkedList.add(2);System.out.println(linkedList);//通过迭代器遍历链表ListIterator<Integer> it1 = linkedList.listIterator();while (it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("===反向===");ListIterator<Integer> it2 = linkedList.listIterator(linkedList.size());while (it2.hasPrevious()) {System.out.print(it2.previous() + " ");}}
}

 

练习题(判断是否是会问链表): 

public class PalindromeList {public boolean chkPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// write code hereListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}//翻转slow以后的链表ListNode cur = slow.next;while (cur != null) {ListNode nextPos = cur.next;//翻转(利用指针翻转)cur.next = slow;slow = cur;cur = nextPos;}//从前向后 从后向前while(head != slow) {if (slow.val != head.val) {return false;}if (head.next == slow) {return true;}head = head.next;slow = slow.next;}return true;}
}

迭代器(Iterator): 

        我们可以利用迭代器进行遍历:

public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);Iterator<Integer> it = list.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}
}

总结: 

        这里我还是默认各位都有基础,希望可以对有基础的人有些帮助(更多的是记笔记),感谢各位支持。

相关文章:

顺序表、链表(ArrayList、LinkedList)

目录 前言&#xff1a; 顺序表&#xff08;ArrayList&#xff09;&#xff1a; 顺序表的原理&#xff1a; ArrayList源码&#xff1a; 的含义&#xff1a;​编辑 ArrayList的相关方法&#xff1a;​编辑 向上转型List&#xff1a; 练习题&#xff08;杨辉三角&#x…...

第11讲投票创建后端实现

投票创建页面实现 文件选择上传组件 uni-file-picker 扩展组件 安装 https://ext.dcloud.net.cn/plugin?nameuni-file-picker 日期选择器uni-datetime-picker组件 安装 https://ext.dcloud.net.cn/plugin?nameuni-datetime-picker iconfont小图标 https://www.iconfont…...

SNMP 简单网络管理协议、网络管理

目录 1 网络管理 1.1 网络管理的五大功能 1.2 网络管理的一般模型 1.3 网络管理模型中的主要构件 1.4 被管对象 (Managed Object) 1.5 代理 (agent) 1.6 网络管理协议 1.6.1 简单网络管理协议 SNMP 1.6.2 SNMP 的指导思想 1.6.3 SNMP 的管理站和委托代理 1.6.4 SNMP…...

计算机设计大赛 深度学习YOLOv5车辆颜色识别检测 - python opencv

文章目录 1 前言2 实现效果3 CNN卷积神经网络4 Yolov56 数据集处理及模型训练5 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习YOLOv5车辆颜色识别检测 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0…...

OpenCV-36 多边形逼近与凸包

目录 一、多边形的逼近 二、凸包 一、多边形的逼近 findContours后的轮廓信息countours可能过于复杂不平滑&#xff0c;可以用approxPolyDP函数对该多边形曲线做适当近似&#xff0c;这就是轮廓的多边形逼近。 apporxPolyDP就是以多边形去逼近轮廓&#xff0c;采用的是Doug…...

transformer中的QKV是如何得到的?

多头自注意力机制&#xff1a;...

console.log导致内存泄露 打包时自动去掉console.log方法

webpack通过工具&#xff1a;terser 使用前需要先安装一下 vue.config.js const { defineConfig } require(vue/cli-servise); module.exports defineConfig({transpileDependencies:true,terser:{terserOptions:{compress:{drop_console:true,drop_debugger:true,},},},}…...

《合成孔径雷达成像算法与实现》FIgure6.20

% rho_r c/(2*Fr)而不是rho_r c/(2*Bw) % Hsrcf exp函数里忘记乘pi了 clc clear close all参数设置 距离向参数设置 R_eta_c 20e3; % 景中心斜距 Tr 2.5e-6; % 发射脉冲时宽 Kr 20e12; % 距离向调频率 alpha_os_r 1.2; …...

Spring Boot 笔记 015 创建接口_更新文章分类

1.1.1 实体类id增加NotNull注释&#xff0c;并做分组校验 1.1.1.1 定义分组 1.1.1.2 实体类中指定校验项属于哪个分组 如果说某个校验项没有指定分组,默认属于Default分组 分组之间可以继承, A extends B 那么A中拥有B中所有的校验项package com.geji.pojo;import com.faste…...

【Java基础题型】判断是否是回文数

需求&#xff1a;如果给你一个正数x。 如果x是一个回文整数&#xff0c;打印true&#xff0c;否则&#xff0c;返回false 解释&#xff1a; 回文数是指正序(从左到右)和从倒序(从右到左)都是一样的整数数字。 eg.121是回文数&#xff0c;123不是&#xff0c;2112是回文数&…...

Linux paste命令教程:并行合并文件的利器(附案例详解和注意事项)

Linux paste命令介绍 paste 是一个在 Unix 或 Linux 操作系统中非常有用的命令。它用于通过在标准输出中输出由每个指定文件的行组成的行&#xff0c;以制表符为分隔符&#xff0c;来水平&#xff08;并行&#xff09;合并文件。 Linux paste命令适用的Linux版本 paste 命令…...

用163邮箱或者outlook接收国科大邮箱的邮件

使用如图下路径&#xff0c;创建一个新的密码&#xff0c;用于在163大师邮箱或者outlook登录即可 如果不行&#xff0c;则需要手动配置邮箱服务器 参考网址&#xff1a;中国科学院邮件系统帮助中心...

VitePress-15- 配置- description 的作用详解

作用描述 1、descriptioin 是站点的描述&#xff0c; 会被解析为 html 页面的 <meta name"description" content "xxx"> 标签 。2、description 本身就是 <meta> 标签的一种&#xff0c;不会在页面上展示出来&#xff0c; 仅仅是作为页面的一…...

寒假学习记录17:包管理器(包管理工具)

概念 包&#xff08;package&#xff09; 包含元数据的库&#xff0c;这些元数据包括&#xff1a;名称&#xff0c;描述&#xff0c;git主页&#xff0c;许可证协议&#xff0c;作者&#xff0c;依赖..... 库&#xff08;library&#xff0c;简称lib&#xff09; 以一个或多个模…...

【AIGC】Stable Diffusion的常见错误

Stable Diffusion 在使用过程中可能会遇到各种各样的错误。以下是一些常见的错误以及可能的解决方案&#xff1a; 模型加载错误&#xff1a;可能出现模型文件损坏或缺失的情况。解决方案包括重新下载模型文件&#xff0c;确保文件完整并放置在正确的位置。 依赖项错误&#x…...

线段树解决-----P1161 开灯 P1047 [NOIP2005 普及组] 校门外的树 python解法

# [NOIP2005 普及组] 校门外的树 ## 题目描述 某校大门外长度为 l 的马路上有一排树&#xff0c;每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴&#xff0c;马路的一端在数轴 0 的位置&#xff0c;另一端在 l的位置&#xff1b;数轴上的每个整数点&#xf…...

学习总结16

# 【模板】最小生成树 ## 题目描述 如题&#xff0c;给出一个无向图&#xff0c;求出最小生成树&#xff0c;如果该图不连通&#xff0c;则输出 orz。 ## 输入格式 第一行包含两个整数 N,M&#xff0c;表示该图共有 N 个结点和 M 条无向边。 接下来 M 行每行包含三个整数 …...

问题:从完整的问题解决过程来看,( )是首要环节。A.理解问题 B.提出假设C.发现问题 D.检验假设 #学习方法#学习方法

问题&#xff1a;从完整的问题解决过程来看&#xff0c;&#xff08; &#xff09;是首要环节。A&#xff0e;理解问题 B&#xff0e;提出假设C&#xff0e;发现问题 D&#xff0e;检验假设 A.理解问题 B.提出假设 C&#xff0e;发现问题 参考答案如图所示...

服务器感染了.mallox勒索病毒,如何确保数据文件完整恢复?

导言&#xff1a; 在当今数字化的世界中&#xff0c;恶意软件已成为企业和个人数据安全的一大威胁&#xff0c;其中.mallox勒索病毒是最为恶劣的之一。本文91数据恢复将介绍.mallox勒索病毒的特点&#xff0c;以及如何恢复被其加密的数据文件以及预防措施。 如果您正在经历勒索…...

Android java基础_多态性

一.Android Java基础_多态性 向上转换:只能定义被子类覆写的方法&#xff0c;不能调用在子类中定义的方法。 class Father {private int money; public int getMoney() {return money; }public void setMoney(int money) {this.money money; }public void printInfo() {Syst…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...