嗨，大家好！ 莫斯在这里！ 今天，我们将 讨论数据结构和算法的基础知识，
这是 编码面试中经常出现的话题之一
。 事实上，越来越 多的公司会询问有关数据
结构和算法的问题，看看您是否 能像程序员一样在本
视频中进行思考 我们将讨论 算法上的数据结构基础知识
我们将讨论 Big O 表示法 数组
如果您想了解更多信息，请观看此视频后的链接列表，我 鼓励您注册我的终极
数据结构和算法 课程，链接在此视频下方，现在即可
观看此视频，您不需要任何 有关算法的数据结构的先验知识
但是您需要了解 此视频中的编程基础知识 我
将使用 Java 但如果您不了解 Java 完全没问题您可以使用
您最喜欢的编程语言进行编码 如果 您喜欢本教程请
通过喜欢和分享它来支持我 与其他人一起 也一定要订阅，因为我现在定期
上传附近的视频，让
我们在讨论数据结构和算法之前先开始 我们需要讨论
我们使用的 Big O 表示法 描述算法性能
的 O 表示法 很多人觉得 Big O 很可怕， 但别担心，我会让你觉得它非常
简单，所以让我们 开始吧，这个 Big O 到底是什么，
让我们开始吧 维基百科上的经典定义 Big O 表示法
是一种数学符号，它 描述了
当参数趋向于 特定值或无穷大时函数的限制行为，
这就是为什么很多人 觉得 Big O 可怕的原因，但正如您将在
本节的基本概念 实际上并不难，我们使用 Big O 来
描述算法的性能 ，这有助于我们确定给定的
算法是否具有可扩展性，这 基本上意味着当输入增长非常大时，该算法是否可以
很好地扩展 所以仅仅因为你的代码
在你的计算机上快速执行并不意味着 当你给它一个大数据集时它会表现得很好，
这就是为什么我们 使用大 o 符号来描述
算法的性能 现在 这与数据结构有什么关系
，你将在本课程中学到， 某些操作的
成本可能或多或少取决于 我们使用的数据结构，例如
通过索引访问数组元素 非常快，但数组有一个固定的
长度，如果你想不断地添加 或删除项目，他们
必须调整大小，随着我们输入的大小变得非常大，这将变得代价高昂，
所以如果这是我们需要做的，那么我们 必须使用另一种
称为 a 的数据结构 链表这些数据 结构可以快速增长或收缩，
但是 通过索引访问链表元素很慢，所以这就是
为什么你需要先了解大 O 表示法，然后才能讨论
各种数据结构 以及像谷歌微软这样的大公司
亚马逊总是问你关于 Big O 他们 想知道你是否真的
了解算法的可扩展性，最终 了解 Big L 会让你成为更好的
开发人员或软件工程师，所以 在接下来的几个视频中 s 我们将查看
代码片段并使用大 O 符号
来描述我们算法的性能
你
这是我们的第一个例子 这个方法 接受一个整数数组并
在控制台上打印第一项 不管有多大 数组是我们可以有
一个包含 1 或 100 万个项目的数组， 您在这里所做的只是打印第一个
项目，因此这个甲基只有一个 操作并且需要恒定的
时间来运行我们不关心 确切的执行 以毫秒为单位的时间，
因为这可以从一 台机器到另一台机器甚至在同一
台机器上不同，我们关心的是这个 方法在恒定时间内运行，
我们使用一个的大 O 表示这 是这个方法的运行时间复杂度，
所以 在这个例子中， 我们输入的大小无关紧要，这个方法
将始终以恒定时间或 1 的大 O 现在运行，如果我们
在这里复制这一行，我们有两个操作， 这两个操作都在恒定时间内运行，因此
此方法的运行时复杂性 方法是 Bi 现在 g O 为 2 在谈论
运行时复杂度时，我们并不真正 关心操作的数量，我们只是
想知道 随着输入的增加，算法上的速度减慢了多少，因此
在此示例中，我们有 1 还是 100 万 items 我们的方法在
恒定时间内运行，所以我们可以通过 写下 o of 1 来简化它，这意味着恒定
时间让我们接下来看另一个例子
，我们有一个稍微复杂的 例子有一个循环，所以我们
迭代这个中的所有项目 数组并 在控制台上打印每个项目 这
是输入的大小很重要的地方 如果您在此数组中只有一个项目，
我们将进行一次打印操作 如果 您有一百万个项目显然我们
将进行一百万次打印操作 所以 这个算法的成本
线性增长并且 与输入的大小直接相关，所以我们
使用 n 的大 O 对这种方法的运行时复杂性感到不满， 其中 n 代表
输入的大小，因此 n 增加 了这个算法的成本 也长李 几乎
现在用什么样的循环 来迭代这个数组并不重要这里
我们使用传统的 for 循环我们 也可以使用 for each 循环
例如对于 int number in numbers 我们 可以简单地打印我们的数字
仍然迭代 这个数组中的所有项目 我们也可以使用 while
循环或 do-while 循环 现在如果我们在循环 之前和之后有一个打印语句
你认为 这个方法的运行时复杂度是多少
你已经看到了 这个单一的操作 运行恒定时间，所以这里我们
有一个大 O，我们的循环在 n 的大 O 中运行，再次我们有大 O
1，所以这个方法的运行时间复杂度 是 1 加 n 加 1 的 o 我们
可以简化为 2 加 n 但是 当使用大 O 表示法时，我们删除
这个常量，因为它们并不 重要，这就是如果我们的数组
有 100 万个输入的原因， 添加两个额外的操作并没有
真正对 我们算法的成本我们算法的成本
仍然增加 线性缓和，所以我们 可以通过删除这个常数来简化
这个问题重要的是这个算法的成本 线性增加，并且
与我们输入的大小成正比， 如果输入中有五个项目，
我们将有五个操作， 如果你有 一百万，
我们现在将有一百万个操作 ，如果你在这里有两个循环，那么
让我删除这些打印语句并 复制这个循环你认为
这个方法的运行时复杂度是多少， 它会是 n 加 n 的大哦 或
2n 的大 O 这是另一个我们 放弃常数的例子，因为我们
在这里需要的是 这个算法相对于其输入
大小的成本的近似值，所以 N 或 2n 现在仍然代表 线性增长，如果这个方法
有两个参数怎么办 一个数字数组 和一个名称数组，所以首先我们
遍历数字区域， 然后像这样遍历名称数组，
您认为
这里的运行时复杂度是多少？ 三角 在这种情况下，n 是什么我们不
处理一个输入我们有两个 输入数字和名称所以我们需要
区分这两个输入我们 可以使用 n 表示第一个
输入的大小，使用 M 表示第一个输入的大小 第二个 输入，因此此方法的运行时复杂
度将是 n 加 M 的 o 并且 我们可以再次将其简化为
n 的 O 因为此方法的运行时 线性增加
您
在上一个视频中您了解到 运行线性时间的简单循环 或 Olaf n 但
这里我们有嵌套循环 这是 我们用于打印
数组中项目的所有组合的算法 所以这里的运行时复杂度是多少
让我们在我们的外部循环中找出我们正在 迭代我们的输入数组 所以在这里
我们现在在每次迭代中都有 o of n 我们再次迭代
这个数组中的所有项目 oh of n 的另一个例子所以这个方法的运行时复杂度
是 n 乘以 N 或 N 平方的 o 我们说这个算法运行在
正如您在此图 alg 中看到的那样，二次时间 在 O of N 平方中运行的
算法比 在 O of n 中运行的算法要慢，当然这
取决于输入的大小，如果您正在 处理一个假设为 50 个项目的数组，
我们不会看到任何差异，但是 随着我们的输入越来越大，
在 N 平方的 O 中运行的算法 变得越来越慢，现在如果你
在这个循环之前或之后有另一个循环怎么办 ，例如让我们添加一个 for 循环
并再次迭代 这个数组中的所有项目和 在控制台上打印它们，
这个方法的运行时复杂 度是多少，这里我们有 n 的 o
所以这个方法的运行时复杂度 将是 n 的 o 加上 N 的平方，现在
我们可以再次简化这个 这个数字的平方总是
大于数字本身所以在这个 表达式中 N 平方总是比 n 增长得更快
再次使用大 O 符号来 理解算法的成本增加了多少
我们需要的是一个 近似值而不是一个精确的值，所以
我们可以在这里放入 并得出结论， 这 m ethod 在 N 平方的 O 中运行 让我们
看另一个例子 如果 我们在这里有另一个嵌套循环而不是这个循环
，那么对于数字的第三个结尾 ，你
去运行时间复杂度现在是 n 的 o 立方
你可以想象这个算法得到 远 慢于 o 的 N 平方的算法
我们要讨论的另一个增长率 是对数增长，
我们用 log n 的大 O 显示这里是对 数曲线，现在将其与线性曲线进行比较，
如您所见 线性 曲线以相同的速度增长，但对
数曲线在某些时候会变慢， 因此以
对数时间运行 的算法比
以线性或二次时间运行的算法更有效，更具可扩展性让我们 看一个真实的例子，假设我们
有一个从 1 到 10 的排序数字数组 ，我们想要找到数字 10 找到 10 的
一种方法是 使用 for 循环遍历这个数组，
直到我们找到 10 这被 称为线性搜索，因为它运行
在线性 在最坏的 情况下，如果我们要查找的数字
位于数组的末尾，我们必须 检查此数组中的每个单元格以
找到目标数字，我们拥有 的项目越多，此操作所需的时间就越长，
因此运行 这个算法的时间 线性增加并且
与我们的数组的大小成正比 现在我们有另
一种称为二分搜索的搜索算法，这个 算法在对数时间内运行它
比线性搜索要快得多， 假设我们的数组已经排序，我们
开始 查看中间项目， 它比
我们正在寻找的值更小或更大， 因此在这种情况下，我们的目标数字 10
必须位于该数组的正确分区中， 因此我们不需要检查
任何 左侧分区中的项目 ，有了这个，我们
现在可以在右侧分区中缩小或搜索一半， 我们再次查看中间
项目是否小于或大于 目标值它更小，因此我们再次
忽略上的项目 向左并专注 于右侧的项目，因此在每
一步中 ，如果
我们的数组中有 100 万个项目，那么在每
一步中我们基本上都在缩小或搜索一半 不必检查 我们数组中的每个项目 这是
对数时间的作用 我们有 爱好者遇到算法的增长，
我们将每一步的工作减少一半 你将在
本系列的第二部分中看到很多
不幸的是，谈论树和图我现在无法 在代码中向您展示此示例，因为它
有点太复杂 了 在您
准备好在代码中看到它之前，我们必须讨论一些事情，但相信我， 您会看到 在未来的代码中
，现在它会变得非常简单 我想让你带走的是，
对数时间的算法比线性时间的算法 更具可扩展性，这是
我们将要讨论的最后一个增长率 这部分是指数
增长，这是相反的 对数增长的一部分，所以对数
曲线随着输入大小的增长而变慢， 但指数曲线增长得越来越快，
显然 在指数时间内运行的算法根本无法扩展
它很快就会变得非常慢 我不能给你举个例子
在代码中，我们将不得不 在未来研究它，现在您需要
了解的是指数 增长与
对数增长相反，并且 到目前为止我们讨论的这些增长率
不是 唯一的增长率，但这些 是您大部分
时间看到的增长率 现在我们将在未来看到这些变化的一些变化
请记住这五个关心
您已经看到我们如何使用大 O 符号来描述
我们的算法在理想 世界中的运行时复杂性 我们希望我们的算法超级
快速、可扩展并占用 最少的内存但不幸的是，
如果发生这种情况，这几乎就像 要 10 美元买一辆法拉利
大多数时候它不会发生，我们必须 在节省时间
和节省空间之间进行权衡，有时 我们有更多空间，因此我们可以使用它来
优化算法并使其更快 ，更具可扩展性，但是有
有时我们的空间有限，例如在这种情况下 为小型移动设备构建应用程序时，
我们必须 针对此空间进行优化，因为
可扩展性不是一个重要因素，只有一个 用户在那一刻会使用我们的应用程序
而不是 百万用户，所以我们 需要一种方法来讨论
算法需要多少空间，这就是 再次使用大 O 表示法的地方让我们
看几个例子，我们有这个 greet 方法，它接受一个
字符串数组并为每个打印一个高消息 这个数组中的名称现在在这个
方法中我们声明和循环变量 ，这与输入的大小无关，
所以无论我们的输入数组有 10 还是 100 万个项目，这个方法
只会为这个循环变量分配一些额外的内存， 所以 现在它需要一个
空格 如果我们 像这样声明字符串数组我们称之为复制并
像这样初始化它 所以这个数组
的长度等于我们输入数组的长度所以如果我们的 输入数组有一千个项目
数组也将有 1000 项 这个方法的空间复杂度是多少
它是 n 输入数组中的所有项越多，我们的方法占用的空间就越多
，这 与
输入数组的大小成正比 为什么我们在这里有 oh of n 顺便说一下，当我们谈论
空间复杂度时，我们只考虑
相对于输入的大小应该分配的额外空间我们 总是有大小为 n 的输入，所以我们
不计算它 我们只是分析 我们需要为这个算法分配多少额外的空间，
所以这就是 本课程中的空间复杂度，我们将只
关注运行时复杂度，因为 这有点棘手，但从现在开始
考虑算法的空间复杂度， 尤其是 在西
在空间有限的情况下，看看是否 有办法保留记忆，
嘿伙计们 Marcia 我想让你 知道这个视频实际上是我
终极数据结构和算法 课程的一部分 完整的课程长达 13 个
小时，我已经划分了 它分为三个 部分，所以
如果你认真 学习数据结构和算法，你可以轻松地学习和完成每个部分
我强烈建议你参加这 门课程并从头开始学习所有基本的数据
结构和算法 它比跳跃更容易和更快
从一个教程到另一个教程，我们将 讨论各种类型的数据
结构，例如链表堆栈 队列哈希表二叉树 AVL
树堆尝试图和 各种类型的排序搜索和字符串
操作算法该课程 包含近 100 个面试
问题 这些是
谷歌、微软和亚马逊等公司被问到的面试问题，你可以 在线或离线观看课程
我可以随心所欲地去任何地方 ，您还将获得
结业证书和 30 天 退款保证 它与
本教程完全相同 如果您有兴趣，请单击
此视频下方的链接进行注册 在课程中 谢谢你，在本节中度过愉快的一天
我们将讨论我们 的第一个数据结构，
你可能很熟悉数组 数组内置于大多数编程
语言中，我们使用它们来存储 列表 在一个部分中按顺序排列项目
首先我们将看看 我们种族的各种优势和劣势
然后我将向您展示如何 在 Java 中使用数组 最后我们将
从头开始构建一个数组类 这真是太棒了 练习让
您熟悉代码并 为更复杂的数据结构做好准备
所以 即使您很了解数组也不要跳过本节 所以让我们
跳进去开始
数组是最简单的数据结构 ，我们使用它们来存储 我的名单 项目
就像一个字符串列表数字对象 和字面上任何这些项目
顺序存储在内存中的东西， 例如，如果我们分配一个包含五个整数的数组，
这些整数会 像这样存储在内存中，假设
内存中第一个项目的地址是 100 可能知道 Java 中的整数占用
4 个字节的内存，因此第二项 将存储在内存位置
104，第三项将存储 在内存位置 108，依此类推，
因此 通过索引查找数组中的项目
是 超快，我们给我们的数组一个 索引，它会弄清楚
它应该访问内存中的确切位置，现在 你认为这个操作的运行时
复杂度是多少它全部 是因为
内存地址的计算非常简单它没有 涉及任何循环或复杂的逻辑，因此如果
您需要存储项目列表并 通过它们的索引数组访问它们是
最适合您的数据结构，现在 让我们看看
Ja 中数组的局限性或弱点 va 和许多 其他语言的数组是静态的，这
意味着当我们分配它们时，我们应该 指定它们的大小，并且这个大小
以后不能改变，所以我们需要提前知道 我们想要
在一个数组中存储多少个项目，如果我们不这样做怎么办？ 不知道我们 必须做出猜测，如果我们的猜测
太大会浪费内存，因为如果我们的猜测太小，我们 将永远不会填充单元格
我们的数组很快就会被填充 然后添加另一个项目，我们将
不得不调整大小 数组，这意味着我们 应该分配一个更大的数组，然后
将旧数组中的所有项目复制 到新数组中，此操作可能
代价高昂，您能猜出此操作的运行时 复杂性吗暂停
视频并考虑一下 这里是答案 假设我们的数组
现在有 5 个项目，我们将添加第六个 项目，您必须分配一个新数组
并将所有这五个项目复制到该 新数组中，因此此操作的运行时复杂度
为 n 的 o，这意味着 复制这些项目的成本 进入新
数组 i 线性增加并且 与数组的大小成正比 现在
让我们来谈谈移除眼睛 这里我们有几种不同的
场景 如果你想移除最后 一项很容易 我们可以
通过它的索引快速查找并清除 内存，所以这里我们有 ol1，这是我们
最好的情况，但是在进行 Big O 分析时，我们应该考虑
最坏的情况，这里的最坏 情况是我们想要
从数组的开头删除一个项目 我们必须
将右侧的所有项目向左移动一步以 填补空洞，我们拥有的项目
越多，这种移动操作的 成本就越高，因此对于最坏的情况，
删除操作是 O of n 操作， 因为
在我们不知道 要在其中存储多少项
或需要从中添加或删除 大量项的情况下，数组具有固定大小，在
我们使用的这些情况下，它们表现不佳 我们稍后将讨论的链表
在课程中，现在让我们看一下 Java 中数组的快速演示，
在此视频中我们将查看 Java 中的数组 ，如果您非常了解数组，请
随意转义此视频，以便声明 一个数组，我们将从以下类型开始
数组 假设我们想声明 一个整数数组，所以我们输入 int
然后我们添加方括号来 表明这是一个数组而不仅仅是一个
常规整数 接下来我们给我们的 变量一个名字，比如数字，在这里我们
使用新的 操作符在 这里为这个数组分配内存 我们再重复
一次数组的类型 但是这次 在方括号内我们指定
了这个数组的大小 假设 3 现在 让我们在控制台上打印这个
我们得到这个奇怪的字符串 这是什么 好吧，这是数组类型的组合，
后跟 @ 符号， 然后是
基于此对象在内存中的地址生成的值，这 没有用，您想查看
此数组的内容来执行此操作 将 要使用数组类让我告诉
你，所以 h 在某种打印数字中， 您将使用我们键入数组的数组类，
正如您在该类中所看到的， Java dot util 在此包中声明，
因此我们按 ENTER 和 IntelliJ 在顶部导入此类，现在我们
使用点运算符 并在此处调用两个字符串 方法为密码数组，此
方法会将其转换为字符串， 然后我们将在控制台上打印该字符串
不让我们再运行一次程序 ，您会做得更好，
以便我们可以看到所有内容 数值 数组中的项被初始化为零 现在让我
向您展示如何更改这些项的值， 因此在我们声明我们的数组之后，
假设我们要设置 我们再次键入数字的第一项，我们使用
方括号，在这里我们指定 一个 索引 第一个项目的索引是 0
所以这里我们引用或引用 我们设置的第一个项目让我们说
10 同样我们可以将第二个项目设置 为 20，第三个项目设置为 30 现在让我们再
运行一次程序 所以这 是我们数组beautifu的内容 我现在
如果你知道你要 提前存储在你的数组中的项目
有一个更短更干净的方法来 初始化你的数组而不是做
所有这些仪式，我们可以使用花 括号来声明和初始化这个
数组，所以我们在这里 输入 10 20 和 30 这将在内存中分配一个包含 3 个项目的数组
，它将 根据我们在此处传递的值初始化每个项目
看看我们得到 与之前完全相同的结果
现在这个区域对象有一个 名为 length 的字段 这将返回
数组的大小，让我们在控制台上打印它 ，看看我们得到了什么，然后打印
数字点的长度，你去 这个数组的大小是三，我们
不能改变它，所以如果想在 这里存储四个项目，你必须 创建
另一个数组 复制所有现有 项目，然后添加第四个项目 这
是 Java 中数组的问题，因此如果 您想使用自动增长或缩小的列表，
则必须使用 您将要讨论的链表
他们在下一节 n 但在我们 到达那里之前，我会给你一个很棒的
练习，我们将在接下来研究它，
以便当你学习 Java 或静态数组时， 这意味着它们有一个固定的大小，
这个大小不能改变，但现在 我们要开始了 为了做一些非常酷的事情，
我创建了这个数组类，它 就像一个动态数组，当我们向其中添加新项目
时，它会自动增长，当 我们删除项目时，它会自动
缩小让我向您展示它是如何工作的，因此 我们创建了一个新的 数组对象我们称之为
数字然后像这样初始化它 在这里我们传递初始大小让我们说
3现在这个数字对象有一个 添加新项目的方法让我们添加10
然后20然后30我们还有一个 打印这个数组的方法 但从
技术上讲，这种打印方法不 应该在这里，因为数组不应该
关心在控制台上打印其内容 它不应该知道
关于控制台的任何信息它应该只 关心存储这些值
显示这些值是一个完全 不同的问题 d 不
应该作为这个类的一部分来实现，但在 本课程中我们希望保持
简单，这就是为什么我 在数组类中实现了 print 方法现在
让我们运行这个程序，看看我们 得到了什么 10 20 30
我们数组的初始大小是 3，但我们可以轻松 添加一个新项目，我们的数组将
自动增长，没问题我们 还有一个方法来删除项目，
remove 在那里获取索引假设 我们要删除最后一个项目 这个
项目的索引是多少？第一个项目的索引是 0
然后是 1 2 3 所以让我们删除最后一个项目 这里的结果很
漂亮你还有一个方法来 找到一个项目的索引让我告诉
你所以我 将在此处执行打印语句 并调用此数字的点
索引将返回该项目第一次 出现的索引让我们说 10 所以
因为 10 是此数组中的第一个项目 此方法将返回 0
看看 0 如果我们通过 数组中不存在的数字比方说
100 会返回负 1 好的现在这是你的练习 我希望
你构建一个数组类，它的工作原理 与你在本视频中看到的完全一样
这是一个很棒的练习，可以 让你在代码中弄脏你的手，
尤其是在处理数据 结构时 和算法并没有说
这太简单了 我已经知道如何
做到这一点 相信我，因为我们谈论更 复杂的数据结构 我们的代码
会变得更复杂 所以我希望你 把它当作一个热身练习
暂停视频并在完成后在此练习上花费 20 分钟 回来
看看我的解决方案
好吧 我们将逐步解决这个问题 这是我
希望您在想要 解决复杂问题时遵循的方法 问题 不要尝试
一次
做太多事情 尝试将问题
分解成更小 的问题
不再担心 添加新项目或 删除现有项目 我们将
在 以下视频中实现这些功能 所以让我们在这里添加一个新
类 我们将右键单击 此包并添加一个新的 Java 类，
我们现在在该类中将其称为数组 需要添加一个
构造函数，所以我们在这里输入 public array 我们需要一个参数来指定
数组的初始大小，所以 现在在这个类中我们将把
我们的项目存储在一个普通的 Java 数组中，所以 我们要声明一个 私有字段
私有 int 数组现在 在构造函数中称为 items 我们需要
根据初始大小初始化此数组，因此 我们将项目出售给长度为 a 的新
临时 a 现在让我们 实现打印方法，因此
我们需要在这里迭代 public void print 遍历 此数组中的所有项目并将
它们打印在控制台上非常容易，因此将 4 放入 I 我们将其设置为 0，只要 I
小于我们增加 I 的长度的项目， 并且在每次迭代中，我们只需在每个迭代中打印
I 的项目 迭代我们得到 一个 i 从数组中取出 tem 并将其打印
在终端上 现在让我们回到我们的 主类 我们将创建一个新的
数组对象 我们称之为数字并将其 设置为一个新的 3 数组 现在让我们
在控制台上打印这个对象 我们得到这 三个零，但从技术上讲我们不应该
看到任何东西，因为我们没有 在这个数组中插入任何项目所以让
我们回到我们的数组类 我们需要另一个字段来跟踪
我们不能依赖的这个数组中的项目数量 在那个长度的项目上，因为
这是我们 最初分配的内存，我们可能会为
50 个项目分配内存，就像你可能只 在这个数组中插入两个项目，所以每次我们
插入一个新项目时，我们需要跟踪 这个项目的数量 array
我们怎么做我们可以声明另一个 私有字段 private int 现在让我们称它为
count 回到打印方法我们 要用 count 替换长度的项目
所以最初 count 为零并且这个
循环将来不会被执行 每次我们插入一个新项目 这个
数组我们将把 count 加一， 所以现在让我们再运行一次这个程序，
因为我们的数组是空的，我们看 不到任何漂亮的东西 我们已经完成
了第一步，所以接下来让我们 实现插入方法
好了 现在让我们实现插入 方法所以 public void insert 我们给它
一个参数 int item 现在应 该做什么这个方法
如果数组已满我们需要做一些事情我们 需要调整它的大小，我们还
需要添加这个新项目 当前数组末尾的项目让我们
不要担心第一步， 而是我们要做第二步
，这更容易，所以我们想 在这个数组的末尾添加这个新项目
我们如何才能做得好我们使用 我们使用方括号的 items 字段现在我们
需要传递一个索引 这个索引是什么这个索引应该
代表这个数组中的最后一个 项目它不会是长度它
会被计数的项目所以目前我们 在这个中没有任何项目 数组所以
最后一项的索引或 下次我们添加新项目时 ，我们应该插入新项目的位置是
索引 0， 索引将是 1，然后是 2 和 3，所以
我们说计数为 2 的项目这个新项目 ，然后我们将计数增加 1，或者我们
可以简化 这段代码去掉了这一 行并在这里增加了计数，所以
用这个表达式首先我们说 计数为 2 的项目，然后计数
将增加 1 让我们测试我们的 代码到这一点，回到
主类我们' 将调用插入 方法并
在 20 nanus 上传递几个数字 10 运行程序，你会很 漂亮所以让我们回到数组
类并实现这个场景 我们如何判断它们是否有用
，这很容易我们可以编写一个 像这样的表达式如果
长度等于计数的项目现在在这种情况下 我们应该首先做什么我们需要
创建一个更大的新数组并且 比方说大小的两倍然后我们需要
将所有现有项目复制到这个 新数组中，最后我们 将把
items 字段设置为这个新数组， 因为 目前，
items 字段引用的数组是 4，所以 让我们先实现每一步，我们
需要创建一个新数组，这很 容易，我们声明一个 int 数组，我们
称其为新项目，并将其设置 为计数乘以 2 的新条目 所以这个新数组
的大小是旧数组的两倍 现在我们 需要复制所有现有的项目
我们将使用一个与我们这里的 for 循环完全一样 的 for 循环 所以我们需要
遍历所有现有的项目并 引用 他们使用他们的索引
，所以我们将它设置为零，只要 我小于计数
我们现在在每一步之后增加在每一步我们 将设置我购买的两个项目的新项目，
这非常简单，最终 我们需要 将 items 字段设置为这个
新数组， 所以我们现在将 items 设置为新项目让我们
测试一下，回到主类， 我将添加更多项目并
运行程序， 现在我们有一个动态数组，它会
自动增长 我们向其中添加了新 项目，以便您了解
所有内容 工作 我要 回到数组类并去掉这些
额外的注释 我们不需要这些 注释，因为我们的代码是干净和
直接的 我们不需要重复 它 我们应该只使用注释来
解释明智和房子 不是 代码所做的应该反映
在代码本身中所以删除删除和 删除接下来我们将实现
删除操作 你
现在好了让我们实现删除 方法所以 public void remove 我们
现在给它一个索引现在应该怎么做 我们首先在这里做 我们要验证索引并
确保它在正确的
范围内 5 个项目，如 您所知，在这种情况下，最后一个项目的索引
显示在如果有人 说删除索引 5 或 6 或 7 处的项目之前，
这没有意义，所以首先 我们要验证
第二个我们想要的索引 将项目 向左移动以填充 我们将在稍后讨论
这意味着什么让我们 逐一实现这些场景中的每
一个所以首先我们将验证 索引这很容易我们可以编写
这样的 if 语句如果索引 小于零或 我们使用两个
竖线来表示逻辑 or 或 索引大于或等于 count
如果 count 是 4 ，这意味着最后一项的索引是
3，这意味着什么，所以我们不能告诉这个数组 删除索引处的项目 4 或 5
等等，这就是为什么我们现在有大于 或等于计数的原因
在这种情况下我们应该怎么做我们不想 在控制台上打印消息，因为
此类可能 用于具有 图形用户
界面那里我们没有控制台， 所以我们应该抛出异常，
因为如果 有人传递超出范围的索引，这是一个编程错误，
因此通过抛出异常，我们 迫使程序崩溃
，程序员也因此而崩溃 知道他们 犯了错误，他们会 解决这个问题，
所以我们抛出一个类型为非法参数异常的新异常， 这是
第一步，现在让我们处理第二 部分，
假设我们有一个像这样的数组 10 20 30 和 40 然后我们想要
删除索引 1 处的项目 这是这里的 20 所以为了删除 20 我们
应该在这里复制 30 然后在这里复制 40 所以我们将每个项目
向左移动一步，换句话说 ，索引1处的项目应该设置为
我们拥有的 在索引 2 处和我们在 索引 2 处的内容应该设置为我们在索引 3 处的内容
我们如何实现这 一点很容易我们需要一个
从该索引开始的 for 循环，它 一直持续到结束 对于这个
数组，所以对于 int I，我们将它设置为索引 ，只要 I 小于计算
每一步之后的增量 I 现在在每次 迭代中，我们希望
将此索引处的项目设置为其右侧的项目， 这很容易 所以我们将 I
的项目设置为 I 的项目加上 1 ok 所以在我们 执行这个 for 循环之后，我们的数组就会去
看起来这个 30 将被复制 到这里，然后 40 将被复制
到这里但是我们在这个数组中还有 4 个项目 我们想要缩小这个数组
所以看起来像这样我们如何 在循环之后很容易地做到这一点 将
count 减 1，因为 count 表示 当前在那里的项目总数，
而不是数组的大小，所以 让我们测试我们的代码回到主
类，我们在打印数组之前在这里添加了四个项目， 让我们调用 remove add
并删除 第一个项目，所以 10 将消失，现在我们有 20 30 40 个漂亮的
让我们用不同的索引测试它 假设现在索引 1 20 消失了
让我们做另一个测试并 删除最后一个项目以便它通过索引 3
40 消失了如果 你传入 X 4 我们得到了一个类型为非法
参数异常的异常这是一个编程 错误我们不想在控制台上打印一条消息
我们想停止 程序的执行所以现在
我们已经完成了实现 在 remove 方法中让我们摆脱 t hese
不必要的注释并使我们的代码 干净接下来我们将实现
搜索操作
最后让我们实现搜索 操作所以 public int 因为我们
想要返回给定项的索引我们 调用此方法 index of 并给它一个
参数 item 现在我们应该怎么做 我们想要循环遍历
这个数组中的所有项目，如果我们找到 你想要返回索引的项目，否则我们
将返回负数，所以 我们将再次使用一个非常简单的 for 循环
因为 I 我们将它设置为零， 只要 I 小于 count
你现在要加一
等于这个项目然后我们想要返回 I 作为索引否则如果你完成
这个循环并且我们仍然在这里我们没有 从这个方法返回这意味着我们
找不到这个项目所以我们应该 返回负一个让我们测试我们的
回到主类的新方法我们添加了 这四个项目 1 0 20 30 40 让我们打印
索引为 10 的数字，这样 0
就很漂亮了 让我问你一个问题
这个方法的运行时复杂度是多少 暂停视频并
思考一秒钟 好的 这是我们 需要在
最坏情况下分析最佳情况的答案
此数组中的第一项，因此在这种情况下， 运行时复杂度为 o 为 1，但
最坏的情况是此项目 位于数组的末尾，因此如果我们的数组有 1，我们必须
遍历整个数组以找到该 项目 百万个项目
，这意味着我们将有 100 万次 比较操作，因此在最坏的
情况下，此方法的运行时复杂 度为 o
这种方法
非常适合
你 您将学习如何从头开始构建动态 数组，这是一个很好的
练习， 但是 Java 有两个
动态数组的实现，让我向您展示我们有 两个类 vector 和 array list 这
两个类都在 Java 中声明了 util 包，但是它们“ 略有
不同，victor 类 每次满时都会根据其大小
而 增长，而 ArrayList 只会增长其大小的 50%，
而且 vector 类中的所有方法都是 同步的，这是一个高级主题
，我” 我将在我即将推出的 高级 Java 课程中介绍这一点，但基本上当
我们说一个方法是同步的时，这 意味着只有一个线程可以访问
该方法，换句话说，如果您有一个 多线程应用程序，其中
多个线程将使用 这个集合 您将
无法使用 victor 类，您应该 使用 ArrayList 类，因为
ArrayList 的方法不会 再次同步我将
在我即将推出的高级课程中详细介绍 Java 课程现在让我们快速
浏览一下 ArrayList 类，让我们输入数组 列表，然后你在这里看到的尖括号
代表一个通用参数 ，这个通用参数我们指定
了这个数组列表中每个元素的类型， 例如，如果你想 有一个
整数数组列表，我们输入 integer 这个整数类是
本机或原始 int 类型的包装器，因此对于 我们拥有的每个原始时间，例如
int short white boolean 无论我们有 一个包装类，例如我们有
short 我们有 white 有布尔值 等等我们也可以有一个
字符串或学生的 ArrayList 假设我们 在这个演示中有一个学生类
我将创建一个整数数组列表 所以整数 n 项现在我们需要
导入 ArrayList 类，因为它被 声明 在一个不同的包中，所以我们
按 Alt + Enter 就可以了，它在顶部很重要，
现在让我们创建我们的 ArrayList 我们调用 这个列表并使用
new 操作符初始化它，就像这个新的
ArrayList 现在我们 可以调用 add 方法我们 可以在这里添加一个数字并复制这一
行几次我还有两个数字 现在我们可以在控制台上打印这个列表
所以这是我们数组的内容很 漂亮我们也可以删除项目
所以我们可以删除 删除特定 对象或删除给定索引处的项目，
例如我们可以删除 第一个项目，现在十个消失了我们
只有 20 和 30 我们还可以找到元素 第一次出现的
索引，因此请回忆一下该索引的列表 20 因为现在删除第一个
项目后 20 将是第一个项目， 此方法将返回零我们
还有最后一个索引，它将返回我们还包含 的项目的最后一次出现的索引，该项目
返回一个 布尔值告诉我们 如果您
的数组中是否有此项目， 最后我们可以使用 size 方法来
获取此数组中的项目数 ，最后另一个有用的方法是
真正的数组方法，它将将此 列表转换为常规数组对象，因此
有 次你 想要使用 常规数组对象，假设您有
一个只接受数组的方法， 并且不能在那里传递 ArrayList 类，
在这种情况下，我们可以轻松地将您的 ArrayList 转换为常规数组
链表可能是最 常用的数据结构 在数组之后，
它们解决了数组的许多问题 ，也用于
构建更复杂的数据结构，因此 在本节中，我们将查看
链表，我们将讨论 它们在内存中的结构，我们将
查看 对它们进行各种操作的时间复杂度 ，最后我们将再次
从头开始构建一个链表 这是一个令人难以置信的练习，
可以让您训练您的编程大脑 所以 让我们进入并开始我们使用
链表来存储对象列表 序列但与数组不同，
链表可以自动增长和收缩， 正如您在此处看到的，链表
由一组节点组成，每个节点按顺序 保存两个数据，一个
是值，另一个是地址 列表中下一个节点的 ss 所以我们说
每个节点指向或引用 下一个节点这就是为什么我们将这些
结构称为链表因为这些 节点链接在一起我们现在称
第一个节点为头，最后一个节点 为尾 让我们看看
各种操作的时间复杂度 假设你想知道我们的列表是否
包含一个给定的数字 我们必须 从头到尾遍历列表
这里的 运行时复杂度是 n 的 o，
因为 我们正在寻找的值 可能存储在最后一个节点中，这
是我们最坏的情况 ，通过索引查找怎么样 不像
数组那样按顺序存储项目 链表的注释
可以在内存中到处都是 可能并不完全相邻，
这就是为什么每个节点都需要保持 对下一个节点的引用，因为这个
原因与数组不同，我们不能通过 索引快速查找项目，我们必须
遍历列表，直到在列表中找到该 项目 最坏的情况是
item 可能位于列表的末尾，所以 再次在这里我们有 o of n
插入怎么样这取决于 我们想要插入一个 item 如果你想
在最后插入一个新 item 我们只 需要 创建一个新节点并让
最后一个节点或尾部指向它我们 应该在某处引用最后一个节点
所以我们 每次都必须遍历列表现在
我们需要让尾部引用这个 新节点所以插入一个新项目
最后是一个操作的 O 怎么样在开始插入
你认为这里的运行时 复杂性是什么暂停视频并
考虑一下
这里的答案它是一个油 因为我们应该再次
引用头部或 第一个音符，以便在列表 的开头插入一个新项目，
我们创建一个新音符，将其链接 到第一个音符，然后将
头部更改为再次指向这个新音符， 这与我们不必进行的比赛不同，速度非常快
复制或移动周围的项目，我们 只需更新链接或引用
现在如果你想 在中间的某个地方插入一个项目怎么办让我们说
在第十个音符之后首先我们必须 找到那个音符是一个 O 的 n
操作然后我们必须更新 链接这是一个操作的 O 所以
在中间插入一个项目是一个 O of n 操作 现在让我们谈谈
删除 我想让你暂停视频 并考虑三个场景
从头到尾从中间删除一个项目 在一张纸上画
链接应该更新 还计算每个场景的运行时复杂度
这很重要 确保做这个小练习
因为稍后 如果你不理解
这些概念，你将不会编写所有这些代码 能够对它们进行编码，所以暂停视频
，当你完成后做练习回来 继续
观看这里是答案 删除第一项非常快我们只需
将头部设置为指向第二个音符 ，这是一个操作的 O 现在我们
也应该 从前一个头部删除链接， 这样它就不再
引用第二个注释了， 为什么因为如果你不这样做，Java 的
垃圾收集器认为这个对象 仍在使用，所以它不会从内存中删除它，
这就是我们应该取消链接的 原因 对象从第二个对象中
删除最后一个项目怎么样 这个有点棘手我们可以很容易地
得到尾部但是我们需要知道 前一个节点所以我们可以将尾部
指向那个节点我们怎么做我们 必须遍历
一旦我们 到达最后一个节点之前的节点，我们就会将其从头一直到尾的列表
保持对它的引用作为前一个 节点，然后我们将从最后一个节点取消该节点的链接
并找到一半的尾部 指向前一个节点，所以
这里的运行时复杂度是 o MN 因为 我们必须一直遍历列表
直到最后 再次从中间删除我们必须遍历
列表以找出节点以及它的 前一个节点 我们应该将
前一个节点链接到之后的节点 这个 节点，然后删除这个链接，这样这个
对象就会被 Java 的垃圾收集器再次从内存中删除 这里我们
有一个 O 的 n 操作 接下来我们将
在这个视频中使用 Java 中的链表 我们将查看 链表 在 Java 中所以如果我们输入
链表我们可以看到这个类是 在 Java 中定义的 util 包这个
尖括号你在这里看到这些是 泛型这意味着我们可以
在这个列表中存储任何类型的对象你可以 存储整数字符串任何类型的
对象 所以让我们按 Enter 这个类被导入到顶部
漂亮 现在假设我们想 在这个链表中存储一堆整数
所以我们添加尖括号并 用大写 I 输入整数 因为这里
我们使用的是定义的整数类 在 Java 中，Lang 包
不是内置的原始类型，所以我们应该 总是在这里引用一个类，这个
整数类包装了一个原始整数， 或者我们可以有一个字符串链表，
或者如果我们在这里不指定任何内容 ，我们可以存储任何类型 的
这个列表中的对象 一个节点可以保存一个整数 另一个节点可以保存一个字符串 所以让
我们再次创建一个列表 我们必须 使用 new 运算符为
这个对象分配内存 所以一个新的链表现在我们 有一堆方法可以添加
我们可以在开头或结尾添加新项目 让我们在结尾添加 10，然后添加
20 和 30
有一个列表，所以
不要让这些方括号愚弄你， 现在我们也可以在开头添加一个项目，
所以我们调用列表，首先 让我们在这里添加 5，现在我们
有 5 10 20 或 30 我们有类似的 方法 为了删除项目，所以我们可以
调用列表来删除最后 一个项目的最后一项我们也有 remove 它
需要一个索引以及 remove first 用于删除第一个项目另一个
有用的方法是 contains 方法，我们 可以使用它来查看我们的列表
包含数字 10 所以让我们做一个打印行 语句和 把这个表达式移到
这里，
所以我们的列表肯定包含 值 10 我们有一个类似的方法，它
是列表的索引将返回这个对象 第一次出现的索引，
所以如果你在这里传递 10 这 将返回 0 因为那是 我们的第一个
项目你去另一个有用的方法 是 size 方法所以让我们打印该
列表的大小这将返回 此列表中的项目数，这是
三个漂亮的最后一个 有用的方法我想介绍的是列出那里
的 to 数组 有时您想使用
数组，以便可以将链表 转换为常规数组，让我们将其转换为
数组并将其存储在此处，现在我们可以 使用数组类将此
数组转换为字符串，然后将其打印 在 控制台到此为止，这就是
链表在 Java 中的工作方式，
现在就像上一节一样， 我们将
从头开始构建链表 这是一个很好的练习 ，可以让您练习
本课程中的所有材料，但在我们开始之前 星星 ted 我 想给你一些提示来做
这个练习 你需要两个类 一个 像这样的笔记类 这里我们有
几个字段，一个叫做 value 的整数 和一个叫做 Nick's 的节点，所以通过这个
字段，我们可以保持对 下一个注意我们还需要一个
具有这两个字段的
无链接类 first and
last 因此，当您看到我的
解决方案时，您不会对这些名称感到困惑， 您可以简单地将您的
代码与我的代码进行比较，这是我 希望您在本练习
中首先实现的金属，最后 首先删除，直到最后包含和
索引关闭 这些是 我们在链表中需要的基本方法，所以
在这个练习上花 30 到 40 分钟 不要跳过它，这是非常重要的，
因为在下一节中我将 讨论堆栈和队列，我们将
要实现它们 使用链表 so li nked list 是你需要掌握的
基本数据结构之一，你 需要掌握足够多的谈话
所以喝杯咖啡
开始吧让我们从 实现最后一个方法开始，所以
最后我们给它一个整数现在应该怎么做 我们在这里做的第一步是将
这个整数的这个值包装在一个 节点对象中，所以我们现在创建一个这样的节点对象，
因为我们可以看到我们已经重复了
两次类的名称，这是 不必要的，我们可以使用 VAR 关键字 我
让 Java 编译器检测这个变量的类型， 因为我们
在右侧有新节点，Java 编译器 会知道这个变量是一个
节点对象，现在我们需要将 这个值设置为这个项目，
但是这个字段是 声明为 私有，这就是为什么我们不能
从这个节点类的外部访问它我们 可以来这里创建一个像
public void set value 这样的 setter 它接受一个 值，在这里我们输入这个 value
等于 value 但我想向你展示一个 更好的 我认为这个节点类
是链表实现的一部分， 我们不需要直接使用
这个节点类，所以这里 不应该将它声明为一个公共类
，它可以 在我们之前的程序中的任何地方访问 使用
Java 中的链表类，如果我们看到一个 我们没有的节点类，我们只是简单地调用
链表上的各种方法， 链表会处理
引擎盖下的一切，所以这个节点类 是链表类
应该做的 在内部它是一个 实现细节，所以我们可以删除
这个 setter 并将这个类移动 到链表中，这样我们就可以将它添加
到顶部 ，你现在去那里，因为这个类是
在链表中声明的，我们可以 访问它的私有字段，所以 我们
不需要设置器，我们也应该将其更改 为私有，这样在我们的程序中我们
无法访问现在更好的笔记类 我们需要改进的另一件事
是此实现的这一行， 我们可以有一个
不做的笔记' t 有一个没有意义的值， 每当我们创建一个便笺对象时，
它应该始终存储一个值，以便我们可以 为便笺类创建自定义构造函数
并将此值传递到那里，因此 在便笺类中，我们在此输入公共节点
构造函数我们添加一个值 并将这个点值设置为 value 现在
我们可以摆脱第 18 行并简单 地将值传递到这里抱歉我让它们成为
项目所以我们的代码更短并且我们的笔记 对象将始终处于有效状态
你 如果我们的链表为空，我们不会有一个没有 值的注释，所以我们有
一个注释接下来我们应该做什么，这 取决于无链接的状态，如果
我们的链表为空，我们需要 设置第一个和最后一个注释 或者 head 和
tail 指向这个新节点，否则 我们需要将这个节点附加
到列表的末尾让我告诉你，这是 我们应该检查的第一个场景，
看看列表是否为空，我们如何 做到这一点？ 写一个像这样的 if 语句
if first 等于 no 这意味着我们 没有任何节点 这个列表
因为一旦我们在这个列表中添加一个节点 首先应该被初始化所以如果
现在是第一个我们应该首先设置这个 新节点我们也应该设置最后一个这个
新节点或者我们可以简化这两 行并初始化这两个
变量在同一行 更好，现在我们不需要这些丑陋的
花括号，所以让我们看看另 一种情况，我们的列表至少有一个
节点，否则在这种情况下，我们想 在最后一个节点之后添加这个节点，所以我们 输入
last that next equals node 我们 将最后一个节点链接到这个新节点最后
我们应该更新 last 以指向这个 新节点，因为现在我们
在这个列表中有一个新节点所以我们输入 last equals node 我们完成了
实现这个方法，所以让我们使用我们的新列表 ，看看它是否工作正常，
回到主类，我想创建一个新的 链表，或者再次调用它
，我们可以在这里使用 VAR 关键字来简化这段代码。 重新
调用列表，然后最后 10 个，然后 20 个，然后现在 30 个 目前我们
没有打印这个列表的方法， 我意识到我忘了告诉你
实现这个方法，但在这个视频中 我不想花时间
实现打印方法，而是我要向你展示 一种不同的技术 所以我们
通过点击这个区域在这一行上添加一个断点 现在它是红色的 现在我们
要使用调试器运行这段代码 所以在顶部看起来 run debug main 是
快捷键，在 Mac 上是 ctrl + D 所以 我们都在这里 前几行被
执行，但这一行不是，所以我们可以 点击这个图标，现在
所有这些行都被执行了所以让我们 检查我们的列表对象，看看它的
结构是否正确，所以在这个调试 窗口中让我展开这个好 在这里
我们有这个列表让我们看看 第一个节点所以值是 10
现在接下来这是引用另一个 节点这里这个节点是什么我们有
20 这也引用 了这个节点中的另一个节点我们有 30 但接下来
这里设置为 null 因为这 是我们列表中的最后一个节点所以 到目前为止，
我们的最后一个节点怎么样了，它 指向同一个对象，其中
我们的值是 30 美丽所以我们 完成了这一步，接下来我们将实现
另一个方法，
好吧，让我们实现广告第一个 方法，这非常相似 对于
我们在上一个视频中所做的 ，最初 public void 现在再次获取一个项目
，我们需要将此项目包装在一个 节点对象中，到目前为止，节点等于其中一个的新节点
， 如果列表为空，我们有两种情况 需要添加
第一个节点，否则我们需要 将此项目添加到列表中，因此我们检查
first 是否为 no 然后就像在我们将 first 和 last 设置为这个新节点之前一样，
否则我们希望该节点指向 我们的第一个节点，因此您的类型
下一个首先等于的节点，然后我们需要 将第一个节点设置为这个新节点，所以
第一个 EKOS 节点我们已经完成
了这个方法的实现，但我想 向你展示一种使这段
代码更具可读性和可维护性的技术 不幸的是
mos 数据结构书籍和课程 没有教你
我在这本书中说 的大部分代码示例看起来很恶心它们看起来真的很丑，就像
我们在 1980 年代编写的代码一样，那么 我们如何改进这些代码并使其
更具可读性 看看这个逻辑， 这个逻辑的意义是什么，你
想看看这个列表是否为空， 所以我们可以把它提取到一个
私有方法中，并称它为空，让 我告诉你，所以我们在这里创建一个私有
方法 它是私有的，因为这是 实现细节，我们不希望
它可以在这个类之外访问， 所以 public boolean 现在是空的，现在这里
只是 return head equals sorry first equals no
现在我们可以 通过调用来替换这个逻辑来改进这个代码 这个
新方法不是更干净 我们也修改add last方法为
空漂亮接下来我们要 实现indexof方法
好了现在让我们实现 这个项目的public int index的方法的索引
我们应该在这里做什么 我们需要 遍历这个 列表
从头开始一直到 结束，一旦我们找到具有此值的项目，
我们将返回该项目的索引 ，
但我们这里没有索引，所以 我们如何实现，我们可以
声明 一个变量索引并最初 将其设置为 0 然后当我们遍历
这个列表时我们增加这个索引所以我们 需要另一个变量让我们说 current
我们将它设置为第一个节点现在我们 需要一个 while 循环只要 current
不是 no 意味着我们还没有到达 列表的末尾，我们需要将
当前节点的值与此 项目进行比较，因此如果当前该值等
于此项目，我们希望返回当前 索引 Silver 返回索引，否则
您要将当前设置为 下一个 节点，因此我们将 current 设置为当前点
next，同时 如果到达
列表的末尾并且我们找不到 具有此值的节点，我们现在还应该增加索引，我们现在需要立即返回
负 1 让我们测试我们的 代码，回到主类，我们添加
了一些项目 现在让我们打印 10 的索引列表，
这样我们就会得到零美丽 的 30 的索引怎么样 最后一个项目我总是
寻找这个太完美的边缘情况 ，最后一个列表中不存在的项目
如此负面一个美丽的 下一个 我们将要实现
contains 方法 你
的 contains 方法很简单 所以 public boolean contains item 现在我们
应该在这里做什么 我们应该 从头到尾遍历列表
如果你 发现这个项目会 返回 true
否则我们将返回 false 但是我们 已经在我们的方法索引中构建了这个逻辑
所以我们可以重用这个没有 必要重复这个逻辑所以我们输入
项目的返回索引不等于 负值所以如果这个表达式如果
value 为 true 这意味着 我们的列表中有这个项目让我们测试一下所以
回到主类，我们将调用 包含 D 的列表，显然我们
没有这个项目，大约 10 我们得到真正的 美丽，非常 很简单，接下来我们
要imp 现在修改删除第一个方法
让我们开始删除 第一个项目所以 public void 先删除
我们不需要任何参数这里 这个有点棘手想象我们的列表
看起来像这个十点到 20 点到 30 点现在我们想要
删除第一个项目，所以我们有这个 名为 first 的字段，它当前
指向 10 我们应该把这个点指向 第二个节点，这将使我们的列表
向前看，它看起来像这样， 但是我们仍然有这个对象，
第一个注意是 引用 第二个节点，因此 Java 中的垃圾收集器
将无法 从内存中删除此对象以解决此
问题，我们现在需要删除此链接， 这是棘手的部分，
如果我们删除此链接， 我们将无法设置 首先指向
第二个节点，因为当我们删除 此链接时，我们将失去对第二个
点的跟踪，因此要解决此问题，我们首先需要 两个不同的引用，
然后让我向您展示，因此我 将把它带回来 我们要写一些代码，所以
首先我们声明一个名为 second 的变量， 我们对第一个点 next 说这个，所以
ii 指向 20 现在我们 有了这个，我们可以去删除这个链接，
而不必担心 丢失第二个点，因为我们有
第二个变量在这里作为备份所以我们 先去设置下一个知道这
将删除这个链接最后我们 需要先更新并将其设置为指向
第三个第二个节点所以我们将第一个设置为 第二个让我们测试一下然后回到
主要 添加这些项目后的类 让我们首先调用 list dot remove
就像在我们要使用调试器运行这个程序之前 那样 ctrl + D 好的，
我们在这个列表中首先 指向包含 20 的注释
，这是指向 另一个注意事项 现在很漂亮，如果我们的列表为空
并且我们调用 remove first 方法 让我们看看会发生什么
我们得到了空指针异常类型的 异常这是一个编程错误我们
不应该让这种情况发生所以让我们 看看内置的 领英客户群 ass in Java
工作，我们将 在这个类中实现相同的行为，所以暂时
我将创建另一个链表， 这次我们使用声明的类
和 util 包的 Java， 所以我们将创建一个链表
字符串列表我们称之为 X 并像这样实例化它 现在我们称之为 X EE move 首先
让我们看看会发生什么
所以我们得到了一个异常但是看看 这个异常的类型没有这样的元素
异常 这与空指针异常不同
这是故意的 错误处理，所以 我们不应该能够
从空列表中删除一个项目， 所以我们要回到我们的无链接
类，在这个逻辑之前，你想 添加一个像这样的 if 语句，如果这个
列表是空的，再看看我们' 重用这个漂亮的方法，所以如果
列表是空的，我们会抛出，你 知道这样的元素异常，这是
实现这个方法的正确方法 嘿，我只是想让你知道，
当我回顾我的视频时，我注意到 我做了 这里有一个错误我没有计算在内 对于
我们的链表只有一个项目的场景， 因为这个逻辑
适用于一个至少有两个项目的列表， 第一个和第二个所以在这里我们
需要添加一个 if 语句并检查 第一个是否等于最后一个，这意味着我们有
一个 在这种情况下，此列表中的单个项目或单个注释如果你想
删除这个项目，我们应该将这两个字段都设置 为 no 然后返回，
因为我们不想 在这里执行这个逻辑所以即使我
犯了错误，每个人也是如此 重要的是我们应该
总是检查我们的代码我们应该 用不同的输入来测试它并考虑
各种边缘情况 你
现在好了让我们修改删除最后一个 方法这是最棘手的部分所以请
密切注意我们要 在 你的方法中声明 public void remove last 所以
让我们想象我们的列表看起来像这样 10 指向 20 指向 30 并且我们现在
有指向这个节点的最后一个字段 来删除我们
需要找到前一个节点的最后一个项目这是 三角 ky 部分所以我们需要
从 我们到达这里的那一刻开始遍历这个列表我们需要保留
对这个节点的引用，以便我们可以 最后更新并将其设置为指向同一个
节点，所以让我们 一步一步地实现这个 首先，我们要找到
前一个节点，我们首先声明一个 名为 current 的变量，然后我们现在将它设置
为第一个节点，只要 current 不是 no 我们要先前进 我们
检查下一个的 current 是否 等于最后一个 请注意，如果是这种情况，我们
需要跳出这个循环，否则我们 将 current 设置为指向下一个节点，
因此此时我们有了上一个 注释，如果我们继续前进，我
想重构此代码并将此 逻辑提取到 一个单独的私有方法，
因为乍一看 可能不清楚我们在这里尝试做什么，所以
让我们声明一个返回节点对象的私有方法， 我们可以调用这个
get previous 并给它一个节点对象， 所以无论我们给什么节点 它会
返回上一个节点，所以让我们移动 它 现在这里的逻辑
而不是处理最后一个 节点你想要处理
这里传递的节点所以让我们改变它 也漂亮而不是
打破这个循环我们现在可以简单地返回 当前节点如果我们遍历
列表所有 到最后的方式但是我们 找不到这个节点之前的节点
我们应该返回 no 现在我们 在一个地方拥有所有这些逻辑我们可以
回到 remove last 方法并调用 get previous 给它最后一个节点和
将结果存储在一个名为 previous 的变量中， 因此在这种情况下，previous
将指向该节点，我们现在应该 做的事情是当前 last
指向该节点，我们应该将其更改为 last 并将其指向前一个，这样这将
缩小我们的列表，如下所示 但是 仍然有这个对象
指向另一个对象，我们应该 删除这个链接，这样
Java 中的垃圾收集器也可以 从内存中删除最后一个节点，所以我们说
前两个这将缩小我们的 列表，然后删除 lin k 我们
最后说在 nan 旁边让我们 在这一点之后测试我们的代码 所以
在添加这些项目后回到主类 让我们删除最后一个项目
现在让我们在那里启动调试器
所以这是我们的列表 让我们看看我们 在这里有什么 首先是
引用它的节点，这是 引用另一个节点，在这里我们没有
任何东西，所以我们成功 删除了最后一个节点，美丽让我们
也确保最后一个字段 引用同一个节点，美丽所以
我们要停止 调试器现在我们 需要考虑边缘情况
如果列表是空的，就像在我们 应该抛出异常之前一样，所以我
将删除这些注释并检查 列表是否为空我们想要
抛出，你知道这样 元素
异常 如果我们的列表只有一个项目， 这个逻辑将不起作用，因为
在最后一个节点之前没有节点我们 只有一个节点，所以这个逻辑
假设我们的列表至少有两个 节点，所以我们需要另一个如果 语句 if
fi rst 等于 last 这意味着我们 在这个列表中有一个节点在这种
情况下 应该将这两个字段设置为知道
然后返回所以这个其他逻辑不会 被执行所以这就是我们如何实现
删除最后一个方法 嘿伙计们我想让 你
知道这个视频实际上是我的 终极数据结构和算法
课程的一部分，完整的课程有 13 个 小时，我把它分成三个
部分，所以如果你认真学习数据结构，你可以轻松地学习和完成每个 部分
和算法 我强烈建议您参加本
课程并从头开始学习所有基本的数据 结构和算法
这比 从一个教程跳到另一个教程要容易和快捷得多 我们将
讨论各种类型的数据 结构，例如链表 堆栈
队列 哈希表二叉树 AVL 树堆 tryes 图和
各种类型的排序搜索和字符串 操作算法 该课程
包含近 100 个面试 问题，这些 ar
像谷歌、微软和亚马逊这样的公司被问到的面试问题，你可以随时随地
在线或离线观看课程 ，次数
不限，你还将获得 结业证书和 30 天
退款保证。 像 本教程一样，
如果您有兴趣，请单击 此视频下方的链接以注册课程，
谢谢您，祝您有美好的一天