顺序表、链表（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() + " ");}
}

总结： 

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

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

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

相关文章

Go 语言中如何大小端字节序？int 转 byte 是如何进行的？

Go 语言中如何大小端字节序？int 转 byte 是如何进行的？

嗨&#xff0c;大家好&#xff01;我是波罗学。 本文是系列文章 Go 技巧第十五篇&#xff0c;系列文章查看&#xff1a;Go 语言技巧。 我们先看这样一个问题&#xff1a;“Go 语言中&#xff0c;将 byte 转换为 int 时是否涉及字节序&#xff08;endianness&#xff09;&#x…
阅读更多...
《Git 简易速速上手小册》第4章：Git 与团队合作（2024 最新版）

《Git 简易速速上手小册》第4章：Git 与团队合作（2024 最新版）

文章目录 4.1 协作流程简介4.1.1 基础知识讲解4.1.2 重点案例&#xff1a;为 Python Web 应用添加新功能4.1.3 拓展案例 1&#xff1a;使用 CI/CD 流程自动化测试4.1.4 拓展案例 2&#xff1a;处理 Pull Request 中的反馈 4.2 使用 Pull Requests4.2.1 基础知识讲解4.2.2 重点案…
阅读更多...
MES生产制造管理:汽车零部件生产MES解决方案

MES生产制造管理:汽车零部件生产MES解决方案

某某汽车部件科技有限公司是一家铝合金零部件研发、压铸和精加工为一体的高新技术企业,拥有先进压铸、机加、检测等设备,并配套自动化生产线。为解决发动机支架等产品的全程生产质量追溯和实现机台设备联网,梅施科技提供了车间级的MES解决方案,如图所示&#xff1a; 梅施科技采…
阅读更多...
[项目管理] 如何使用git客户端管理gitee的私有仓库

[项目管理] 如何使用git客户端管理gitee的私有仓库

最近发现即使翻墙也无法g使用ithub了&#xff0c;需要把本地的项目搬迁到新的git托管平台。 gitee 是一个国内开源项目托管平台&#xff0c;是开源开发者、团队、个人进行 git 代码管理和协作的首选平台之一。本文将详细介绍如何向 gitee 提交私有项目。 注册 Gitee 账号并创建…
阅读更多...
每日五道java面试题之java基础篇（一）

每日五道java面试题之java基础篇（一）

第一题 什么是java? PS&#xff1a;碎怂 Java&#xff0c;有啥好介绍的。哦&#xff0c;⾯试啊。 Java 是⼀⻔⾯向对象的编程语⾔&#xff0c;不仅吸收了 C语⾔的各种优点&#xff0c;还摒弃了 C⾥难以理解的多继承、指针等概念&#xff0c;因此 Java 语⾔具有功能强⼤和简单易…
阅读更多...
Flask 入门7：使用 Flask-Moment 本地化日期和时间

Flask 入门7：使用 Flask-Moment 本地化日期和时间

如果Web应用的用户来自世界各地&#xff0c;那么处理日期和时间可不是一个简单的任务。服务器需要统一时间单位&#xff0c;这和用户所在的地理位置无关&#xff0c;所以一般使用协调世界时&#xff08;UTC&#xff09;。不过用户看到 UTC 格式的时间会感到困惑&#xff0c;他们…
阅读更多...
C#静态数组删除数组元素不改变数组长度 vs 动态数组删除数组元素改变数组长度

C#静态数组删除数组元素不改变数组长度 vs 动态数组删除数组元素改变数组长度

目录 一、使用的方法 1.对静态数组删除指定长度并不改变数长度的方法 &#xff08;1&#xff09;静态数组 &#xff08;2&#xff09;对静态数组删除元素不得改变其长度 2.对动态数组删除指定长度并改变数长度的方法 &#xff08;1&#xff09;动态数组 &#xff08;2&a…
阅读更多...
Linux 命令基础

Linux 命令基础

Shell概述 Linux操作系统的Shell作为操作系统的外壳&#xff0c;为用户提供使用操作系统的接口。它是命令语言、命令解释程序及程序设计语言的统称。 Shell是用户和Linux内核之间的接口程序&#xff0c;如果把硬件想象成一个球体的中心&#xff0c;内核围绕在硬件的外层管理着…
阅读更多...
vscode +git +gitee 文件管理

vscode +git +gitee 文件管理

文章目录 前言一、gitee是什么&#xff1f;2. Gitee与VScode连接大概步骤 二、在vscode中安装git1.安装git2.安装过程3.安装完后记得重启 三、使用1.新建文件夹first2.vscode 使用 四、连接git1.初始化仓库2.设置git 提交用户和邮箱3.登陆gitee账号新建仓库没有的自己注册一个4…
阅读更多...
python进行批量搜索匹配替换文本文字的matlab操作实例

python进行批量搜索匹配替换文本文字的matlab操作实例

在进行一些数据处理时&#xff0c;可能需要抓取原文中的一些内容&#xff0c;批量替换原文另外的一些内容&#xff0c;而且事先还需要一步搜索匹配的步骤。 举个例子&#xff0c;如下matlab输出的txt文件&#xff0c;原文件有几万行数据&#xff0c;这里只摘取3行对应的 文件文…
阅读更多...
单片机学习笔记---DS1302时钟

单片机学习笔记---DS1302时钟

上一节我们讲了DS1302的工作原理&#xff0c;这一节我们开始代码演示。 新创建一个工程写上框架 我们需要LCD1602进行显示&#xff0c;所以我们要将LCD1602调试工具那一节的LCD1602的模块化代码给添加进来 然后我们开始创建一个DS1302.c和DS1302.h 根据原理图&#xff0c;为了…
阅读更多...
spring boot(2.4.x之前版本)和spring cloud项目中配置文件的作用

spring boot(2.4.x之前版本)和spring cloud项目中配置文件的作用

spring 版本以及相关的组件一直在变化&#xff0c;其中一些类或者功能在低版本中有&#xff0c;高版本中去掉了&#xff0c;有的新功能只在高版本有。 为了防止理解问题&#xff0c;pom.xml 版本依赖如下 <parent><groupId>org.springframework.boot</groupId…
阅读更多...
leetcode 3027. 人员站位的方案数 II【离散化前缀和+枚举】

leetcode 3027. 人员站位的方案数 II【离散化前缀和+枚举】

原题链接&#xff1a;3027. 人员站位的方案数 II 题目描述&#xff1a; 给你一个 n x 2 的二维数组 points &#xff0c;它表示二维平面上的一些点坐标&#xff0c;其中 points[i] [xi, yi] 。 我们定义 x 轴的正方向为 右 &#xff08;x 轴递增的方向&#xff09;&#x…
阅读更多...
STM32Cubmax DAC 采集

STM32Cubmax DAC 采集

一、概念 DMA&#xff0c;全称为&#xff1a; Direct Memory Access&#xff0c;即直接存储器访问&#xff0c; DMA 传输将数据从一个 地址空间复制到另外一个地址空间。 当 CPU 初始化这个传输动作&#xff0c;传输动作本身是由 DMA 控制器 来实行和完成。典型的例子就是移动…
阅读更多...
怎么理解 Redis 事务

怎么理解 Redis 事务

背景 在面试中经常会被问到&#xff0c;redis支持事务吗&#xff1f;事务是怎么实现的&#xff1f;事务会回滚吗&#xff1f;又是一键三连&#xff0c;我下面分析下&#xff0c;看看能不能吊打面试官 什么是Redis事务 事务是一个单独的隔离操作&#xff1a;事务中的所有命令…
阅读更多...
嵌入式学习之Linux入门篇笔记——17，makefile基本语法（上）

嵌入式学习之Linux入门篇笔记——17，makefile基本语法（上）

配套视频学习链接&#xff1a;http://【【北京迅为】嵌入式学习之Linux入门篇】 https://www.bilibili.com/video/BV1M7411m7wT/?p4&share_sourcecopy_web&vd_sourcea0ef2c4953d33a9260910aaea45eaec8 目录 一&#xff0e;设置 vim 首行缩进 二.Makefile 基本语法…
阅读更多...
golang windows 环境搭建 环境配置

golang windows 环境搭建 环境配置

golang windows 环境搭建 环境配置 Golang学习之路一环境搭建 MacBook Linux 树莓派raspberrypi安装Golang环境 官网下载地址: https://go.dev/dl/ https://golang.google.cn/dl/ 下载对应系统版本&#xff0c;例如windows 64位系统&#xff0c;下载&#xff1a;xxx.window…
阅读更多...
云计算市场分析

云计算市场分析

目录 一、云计算市场概述 1.1 概述 二、国外云计算厂商 2.1 亚马逊AWS 2.2 微软AzureAzure 2.3 Apple iCloud 三、国内云计算厂商 3.1 阿里云 3.2 腾讯云 3.3 华为云 3.4 百度智能云 一、云计算市场概述 1.1 概述 云计算从出现以来&#xff0c;其发展就非常迅速。以…
阅读更多...
【数据结构】前缀树的模拟实现

【数据结构】前缀树的模拟实现

目录 1、什么是前缀树&#xff1f; 2、模拟实现 2.1、前缀树节点结构 2.2、字符串的添加 2.3、字符串的查寻 2.3.1、查询树中有多少个以字符串"pre"作为前缀的字符串 2.3.2、查询某个字符串被添加过多少次 2.4、字符串的删除 3、完整代码 1、什么是前缀树&…
阅读更多...
MacOS - M1芯片 Mac 在“恢复”模式中启用系统扩展教程

MacOS - M1芯片 Mac 在“恢复”模式中启用系统扩展教程

部分软件需要开启系统扩展才能正常使用&#xff0c;但是默然M1芯片的Mac不能直接打开系统扩展&#xff0c;如下两图。 若要启用系统扩展&#xff0c;您需要在“恢复”环境中修改安全性设置。 若要执行此操作&#xff0c;请将系统关机&#xff0c;然后按住触控ID或电源按钮以开…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

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