在Project 1中，Deque只给了一些API，而具体的实现代码交由我们处理，由此产生了ArrayDeque和LinkedListDeque。还有就是之前课上讲的List61B接口，只声明一些方法，具体实现为AList和SLList准确来说,Java的interface并不是ADT，因为interface允许存在一些default的方法。

并查集是一种数据结构，可以很方便地判断两个元素是否属于同一集合，关于并查集的演示demo，可以参考slides或其他途径，本次课Josh老师循序渐进地从并查集的数据结构选择开始一步步优化，最终使并查集得到相对较好的性能表现。简单来讲，并查集需要拥有两个功能:

记其执行次数为 c(N) ,枚举N从1 到 N，C(N)的值，用以下表格表示:观察上下两个图可知当N = 1时， i = 1, j = 0;当N = 2时， i = 1 , 2, j = 0, 1;N = 2,已知i = 1的结果，只需再求i = 2的结果再将前面算得的i = 1的结果相加,即 3 = 1 + 2当N = 3时， 由于i的变化是每次变为 2i，即当N = 2时， 2i = 4，3比4小，循环仍然...

算法1:逐项比较，比如A[0]分别与A[1],A[2],A[3]......A[n]比较，之后再从A[1]开始，与A[2],A[3]....A[n]比较，A[2]与A[3],A[4]....比较，以此类推。

包名与文件夹路径的对应关系:ug.joshh.animal 对应 ug/joshh/animal使用Packages的好处是支持不同包内可以有同名的class文件，而不会混淆

(在2020后的版本把2018写的ArrayMap改成了ArraySet，因此下面的案例基于ArraySet)所有的类都隐式地继承了Object，且包含Object的以下方法:

依据报错信息我们可以得知在ArrayMap.java代码第38行与ExceptiomDemo.java第6行出错，出错原因是数组越界。当遇到错误时，Java能够自动抛出异常并停止程序的运行。有时候，Java给出的报错信息并不明显，不容易得出错误，我们可以手动添加报错信息，也就是抛出一些异常。使用关键字 throw 我们可以抛出自定义的异常,具体...

正如我们前面所学的，我们能定义泛型类，比如LinkedListDeque<Item>和ArrayDeque<Item>当我们想去实例化一个使用泛型类的对象时，则必须把泛型替换为一种具体的类型。回想一下，Java有8种初始类型，初始类型之外的其他类型均是引用类型。对于泛型而言，我们并不能将<>中的generic type替换为初始类型...

List: 有序元素集合，包含 ArrayList 和 LinkListSet: 无序元素集合，无重复元素，包含HashSet和TreeSetMap: key/values键值对型元素的集合包含HashMap和TreeMap

(注:本篇文章有点难理解，所以我直接大部分翻译原文了......标题:Subtype Polymorphism vs. Explicit Higher Order Functions)

前面我们学习的继承是从interface继承，使用implements关键字来定义与接口的层次关系，现在我们希望可以继承class，使用extends关键字定义类的层次关系。比如现在有一个class RotatingSLList,是继承class SLList我们可以在class声明中设置这种继承关系，使用extends关键字如下：

1.接口继承 Interface Inheritance回想上周我们所实现的SLList类和AList类，其中包含很多相似的method，比如addLast()addFirst()removeLast().....假设我们在某个类中调用SLList，当需要调用AList的时候要么把代码中的SLList改为AList，要么把AList的class全部搬过来。事实上，这两者包含很多重复的method，可见它们来自...

但是使用循环和.equals()方法逐项比对非常繁琐，org.junit library可以帮助我们更好地完成此项评测工作，只需一行，即可代替循环的整段，使用的是

之前我们实现了双端队列，这是一种比较完美的数据结构，在两端进行插入和删除都非常迅速，然而，当我们需要访问队列中的第i项时，总是需要从哨兵结点开始，先遍历前i-1项，才能找到第i项，最坏的情况是i位于中间，此时我们需要遍历链表长度n的一半n/2，假设n非常大时，时间的耗费就会比较大( O(n) )，考虑到数组可以直接...

方式1：创建一个大小为3的int型数组，x为对该数组的引用，默认初始值均为0方式2：创建一个int数组，里面的值为{1,2,3,4,5}，Java会自动计算出该数组的长度，y为对该数组的引用

这样做之后对于新增末尾结点addLast()与求末尾结点的值getLast()的时间复杂度都可以优化到O(1)，但是对于removeLast()，也就是删除末尾结点来说，复杂度仍是O(n),因为当我要删除末尾结点时，我需要找到倒数第二个结点并将其next赋值为NULL,这依然需要从头遍历整个链表

每次都需要这样写，IntList()的参数，第一个是数据项，第二个是结点的指针指向，使用以上语句，当前新结点的指针每次都指向上一个结点，从而完成头插。但是以可读性来说，对于Java新手非常不友好。

java语言不提供让你知道变量具体内存地址的方法，与C不同，这节省了我们对内存的管理，就好比你知道你的心脏在时刻跳动，但你无法在某一确切时刻优化其跳动速度，以免犯错误直接将其关闭。java声明一个变量后，并不赋初值（primitive type），因此当你想使用你所声明的变量时，必须先赋予其初值。java的赋值操作是将y的b...

类比c++的const type关键字，在类内，java则用static final,本次作业中用的是private static final G =6.67e-11

这是Dog.java，里面有一个method,makeNoise(),然后我们可以实现在DogLauncher.java文件中调用它，代码是

那么你的filename应该是hellow.java3.当年声明一个函数，必须使用public static作为signature,比如上面代码中的triangle就是public static int ，而main函数是public static void型

使用命令行运行java程序，首先进入到你创建的.java文件夹，然后打开cmd，依次输入1.javac filename.java(你所命名的java文件的名字，不要忘记后缀.java)之后应该会生成一个filename.class文件。2.java filename(这次不需要加.java)视频里面应该是说javac是complier,java是interpreter之后就可以看到程序输出了.视频中出...