【字幕】恋上数据结构与算法之015动态数组03简单接口的实现

我们先来看一下，不要着急啊大家不要着急，这些东西我肯定会一点一点会给大家去实现，最终实现到跟Java官方版本差不多，只要我们自己实现了，偶尔类似的，你会发现你倒回去看Java官方的那个源码，你会发现特别简单，跟我们写的几乎是一模一样啊。

然后我们看一下啊，那这个东西怎么去设计呢？首先一个动态数组的话，它里面应该有哪些成员变量呢？哪些成员变量呢？我们来看一下怎么去设计。我认为动态数组我们这个呃类似的应该至少包含两个成员变量，一个是size，一个是size，那成员变量肯定是弄成私有的size，这个是元素的数量，还有一个什么呢？

还有一个是用了存放元素，我叫做艾利曼斯，那既然我是数组，所以我这个艾利曼斯肯定是指向数组，比如说我申请了一段连续的存储空间，能够存放123456对吧？

这6个元素假设一开始能存放6个元素，所以我这个OMS应该会指向这个速度，那将来我们通过什么呢？我们通过这个爱的添加元素，我们就会把这个元素放到这个位置，放到这个位置一个一个往后面讲，万一空间不够怎么办呢？没关系，因为我们这个叫动态数组，将来肯定会对它进行扩容，那怎么扩容？

这个是后面的事情，我们先保证能存放元素先啊，所以我们这里面应该是有一个东西叫做应酬，还有你们然后这个类型是个速度，对吧？是个速度，所有的元素我们所有的元素都放这个地方，对吧？

那接下来呢我们再提供一个构造函数 or list，好，这个是一个构造函数，那构造函数这样子你想想我刚刚说了，一开始你看我们能存放6个元素，但是很多时候别人可能自己来指定一开始能放多少个元素，那这个事怎么办呢？

所以我觉得可以让别人传一个卡帕斯提进来，卡帕斯提就是容量，你希望你这个速度一开始容量是多少？

那这个时候我们完全该怎么样呢？首先我们的艾利曼斯，那比如说别人船的容量是10，就意味着一开始我们要开辟10个容量给他，对不对？还有一个那别人也可能不传这个容量，所以我提供一个无参的构造函数出来，那无参的构造函数但是又是多少呢？这样子假设我默认是10个，默认是存放10个，这样就解决了，对吧？

当然size默认一开始肯定是等于什么？0的，因为你里面没有存放任何东西，所以元素数量肯定是0，那这里写的不是很严谨，那怎么做呢？这样子像这个10我不建议写在这个地方，我建议写成常量，在Java里面，如果你是弄一个私有的常量，应该是privy study Guide，final games来个before，而且Java的这个编程规范里面，如果是常量，给我写成大写啪啪CT10就可以了。

Final是常量的意思，相当于别的编程语言语言里面的cost，speak是静态的意思啊，静态就静态能保证什么？静态能保证这个家伙的内存永远只有一份，这个在c加加课程里面也讲过这个静态的作用啊。

然后我们看一下这里面应该写什么呢？这个应该写这个然后这这里面呢这里面其实大家思考一下，我们这个代码是不是呃可以啊，我们这个代码的话是不是完全可以这样写？

直接diss，然后传一个capacity，相当于就是我这个无参的构造函数去调用这个有参的构造函数，注意构造函数之间相互调用是通过disc相当于将这个地方开发视频传给他了，他调用这边啊这个我不多说，这是Java语法问题，那这里写的还不是很严谨，为什么？

一边传的这个东西可能是0，可能是-10是吧？也可能是这个负很多很多很多对吧？那这个不严谨那怎么办呢？那这个时候我们做一个判断，f开发视频小于这样子，我们直接这么做吧。只要它传到这个空间，只要它传到这个空间，是小于我这个默认的，我都认为是是什么意思呢？就是它传的太小了，直接用我这个如果他比我这个大传的是11 12，甚至是20，那才用他的。

我就这样做，这样呢就代表太小的东西，太小这个数量我就不接受，我用我这个10，因为你想想如果他传的是一你一开始就按照他的做法去弄一的话，对吧？那这个很快就不够用了嘛，很快就要扩容了，那这样就比较麻烦，所以我的做法就是呃我就给他默认就是10好吧，如果你乐意的话，你也可以用他的对吧？

比如说你传的是小于0，我就给你个1，一开始从一开始那也可以随便你啊，看你怎么去设计，只不过我这里设计就弄成，只要你什么呢，只要你是小于我这个我就弄成10，这是我自己的一个设计噢这里没有说标准的写法，这个是根据你的情况而定，你想怎么写就怎么写，但是一定要做的是什么？

一定要做的是对它进行一个判断啊，如果它是小数，如果是它是个负数，如果是0你要怎么处理？一定要写一个判断，判断之后怎么处理，这个是你自己的事情啊，就这样写。

好，同学们你想想，那我们回到外面，那别new a list是不是意味着就会调用这个，然后把这个10把这个10传到这个地方，所以到时候这里写的就是10，相当于就是它另一个are list，默认就是有10个元素的存储空间，所以它的这个ed至少能加10次对不对？

等我们快速把这个代码写一下吧，那我们来看一下这个这个先看这个赛字，那size很简单，其实就返回我们成员变量size，就是他调用我这个size，调用我这个size这个方法我就返回我这个成员变量对吧？因为这个成员变量就是用来干嘛？用来存放，用来保存我们当前元素的数量的，然后这个时候再往下走，is empty。

Empty什么意思啊？判断一下是否为空，那这个其实很简单，size等于0，其实就是空这样写。

其实很多有同学有同学可能看不懂这一句啊，我我觉得真有可能啊。其实这一句等价是什么呢？这其实就是等价于如果size等于0不是疼处，对吧？如果size是空，那就代表size，size如果等于0那代表确实是空嘛。如果size不等于0，我就返回force代表不空对吧？Size的不为零说明有东西嘛。

其实这个没必要这么写，这样写比较好嘛，那我们再看一下contents，我们先不写，然后我们先想这个这个其实怎么做的，这个其实怎么做，其实是不是就是去这里面查找元素啊，其实是不是就是去我们这里面l0s里面查找元素，所以这里其实非常简单，直接是l miss，然后 address这样不就可以了吧。

但是这里面我们得对这个address做一个什么呢？应该是做一个约束是吧？应该是得做一个约束，我们得进行判断。

比如说index如果是小于0或者index你也不能说超过是吧？但不能超过什么呢？超过我这个size，比如说我现在存放了三个元素，那我的size就是三，那你能访问的下标其实就是0一，所以这个如果你大于等于这个size，比如说你有三个，那你这个索引等于3就不行，因为你索引只能是012啊，所以小于0或大于等于。

那这怎么处理呢？这个怎么处理呢？这看你想怎么处理，比如说你不想做任何处理，比如说他传错了，你也不想报错，那行吧，你直接返回一个返回一个0给他嘛，因为你传错了，你传错了我就给你0，这是一种处理方法。

在Java里面比较多的处理方法是直接抛出一个异常，叫做死肉牛，而且像这种呃数组越界的异常，它已经内置了一个东西叫做index out of boss，etc etc就是异常，抛出一个异常，那这个异常信息它是传一个字符串，那这里你就可以写你的信息，比如说一旦别人传错了，你就抛出一个错误，告诉他你为什么错了对吧？

比如说我们这里就可以降嗯为什么错呢？因为你index是这个对吧？但是我们的size是多少呢？我们的size是好，这个是在干什么？这个是在拼接字母之外，将这个字符串跟这个整数还跟这个字符串还跟这个整数拼起来，这个是Java里面的拼接字符串，非常简单啊，就这样写。

就抛出这个异常信息，那我们看一下那这个东西是否有效呢？我们来试一下。

Best点get，比如说我传一个-10，-10-10肯定有问题，对吧？我们调用get-10的话，他肯定会小于0小于0就会抛出异常，我们看一下抛出异常是什么反应啊？我们右击我们可以发现这里出现了红色，这个就是我刚刚抛出的异常，这个就是我刚刚写的提示信息，你看你的size是0，你传个-10那肯定不合理吧对吧？这肯定是不合理。

然后既然你塞子是0，说明里面什么也没有，什么也没有，其实你传什么都不对，传0也不对，因为只有你至少有一个元素的时候你才能传0，所以传0其实也是不对的，我们来右击，你看塞子是0，你怎么可以传0呢？也不对。

这个就是抛异常，大家思考一下，如果我不抛异常那也行，是不是可以直接return0告诉你，就是不做任何处理，我就不去访问他了，因为因为因为你你传错了嘛，我就不做后面的事情了，但这种可能提示不是很友善，那Java里比较友善的提示方式其实就是抛异常，就是通过错误来提醒他你错了啊就这个意思。

而且这种抛异常有个好处，你发现了吗？这里面有个而类似的7171，那这个时候我一点你看就定位到这个地方，那就知道噢你哪里错了。嗯嗯嗯。

所以你在写一个框架的时候，你在封装一个框架的时候，比如说我们现在就在封装一个动态速度对吧？呃错误的地方的话，你可真的是可以考虑采取这个抛异常的这个形式，那别人在用你的框架用错了，他就可以通过这个定位异常的这个方式定位到他哪里错了，那这样解决解决问题就比较方便啊，而且我们有一些比较友善的提示信息，这个是干好。

再看一下赛，那在这个其实也很简单，设置index这个位置的这个元素，大家想想这个怎么设置啊，比如说他传一个一给我，我是不是就是把一这个位置的元素给换掉就可以了，而且我这个语义是什么？我这个会返回一个，它原来是什么，相当于就是你传新的给我，我会先把这个位置对应的原来元素给你，同样的它传的这个index是必须跟get这个影带是一样的范围，所以我们把这个东西拿过来，把这东西先拿过来。

然后这里面怎么写，这里面首先old先取出来l miss index。我们先取出来，然后这个o的放这里，然后这个l里面是然后应该是什么？看你们对吧？所以代码逻辑其实非常简单，就这样写就可以了，对吧？把原来的取出来，然后用新的元素覆盖掉这个位置，然后返回原来的元素非常非常的这个简单。

然后的话我们再往下看，添加的话我们可能要下一个再讲啊，因为本来今天我们就讲复杂度的啊，这个先搁着，因为添加东西比较多，然后我们再看一下呃什么删除删除也不行，这个我们得得得下次，那这个呢这个什么意思？这个是看一下这个元素在我们数字中的位置。那这个怎么做很简单，其实就是什么呢？其实就是便利，怎么便利呢？

从这个位置开始便利，看一下看一下这个位置是不是那个元素，再看一下下一个位置，再看下一个位置，一旦发现这个位置是那个元素就返回这个位置，所以我们这里其实非常简单，这里非常简单，然后这里怎么做呢？这里的话由于我们是整数，整数的比较直接用等号就行了，这里不应该是这个，这里应该是直接是size就好了，对吧？比如说我们有5个元素，那我们就遍历5次遍历5次，然后这里边这里怎么写的，这里很简单，I如果等于兄弟们我们就直接返回，唉按照我的编程习惯，一般来说判断完直接返回的，我就会省略掉大括号，这是我个人的一个编程习惯。

好，这样就可以了，大家想想是不是只要找到相等的就直接返回这个索引就好了。好，如果找不到怎么办？找不到一般来说我们返回-1，返回-1对吧，像-1这个东西呢我建议大家也是一样写成常量，在拿货之前在这个位置写LV版，not found，然后这里面应该直接写一个-1对不对？这里面not found，那这个是往下走，然后这个时候翻过来。

好的杨总，好，这个我们写完，然后添加删除都放到下一节课，然后这个set我们写完了，然后这个get我们写完了，然后这个添加放的要content是否包含这个元素，那简单了，这个时候我们可以直接调用我们刚刚写的，如果不等于l里面那放着大家想一想是不是代表代表包含了对吧？

因为如果检查出来这个这个元素的这个索引，检查出来这个元素的这个索引是等于-1代表不存在，如果不等于这个-1代表就存在，代表就包含说content是代表包包不包含的意思。

好，那这几个最基础的东西我们其实已经写完了