Java

双向链表 Doubly Linked List 前面介绍过的单向链表有几个缺点. 第一个就是它的addLast操作非常慢。单向链表只有一个变量保存列表头的地址, 以及每个节点对后面节点的单向引用(链接). 对于很长的列表，addLast方法必须遍历整个列表, 直到找到列表末尾才能执行插入操作. 最直观的优化方案就是加个’车尾’ 这样我们就可以直接通过last.next引用末尾位置. 不过另一个问题并没有解决, 就是删除列表最后一项removeLast这个操作还是很慢。因为在目前的结构设计下, 我们需要先找到倒数第二项，然后将其下一个指针设置为null。而要找到倒数第二节点, 我们就得先找到倒数第三个节点…… 以此类推。也就是说，对于删除末尾的操作，还是要几乎遍历整个列表。 反方向的链接 基于前面单向链表构建双向链表, 一个比较有效的方法是额外为每个节点添加一个指向前面节点的链接 - 指针. public class OneNode { public OneNode prev; //指向前 public int item; public OneNode next; //指向后 } 增加这些额外的指针会导致额外的代码复杂度, 以及额外的内存开销, 这就是追求时间效率的代价. Sentinel 与尾节点 双向链表的一个设计初衷，就是为了解决单向链表针对列表末尾位置的操作效率不高的问题，除了sentinel和反方向的链接还不够，我们还需要一个节点（指针）能够直接帮我们定位到列表末端。可以考虑添加一个的尾节点last 这样的列表就可以支持O(1)复杂度的addLast,getLast 和 removeLast操作了。 循环双端队列 Circular double ended queue 上面的尾节点设计虽然没什么错误，但有点瑕疵：最后一个尾节点指针有时指向前哨节点，有时指向一个真正的节点。更好的方法是使双向链表首尾相连, 构成一个循环，即前后节点共享唯一的一个前哨节点。 这样的设计相对更整洁，更美观(主观上的), sentinel的prev就指向列表最后一个节点, sentinel的next指向列表第一个节点. public class LinkedListDeque<GType> { private class OneNode { public OneNode prev; public GType item; public OneNode next; public OneNode(OneNode p, GType i, OneNode n) { prev = p; item = i; next = n; } } } Sentinel’s forward link always points to the last element....

链表 Linked List 前面有介绍以array为基础搭建的列表，支持自动扩容, 各种插入，删除速度都很快. 这里再介绍另一种方案, 链表, 也可以实现列表自动扩容. 带链接的节点 链表的核心组成是带链接的节点, 每个节点就像火车车厢, 有钩子连接下一节车厢. 以int节点为例: public class IntNode { public int item; public IntNode next; public IntNode(int i, IntNode n) { item = i; next = n; } } next就是这个链接, 每一个节点就是其上一个节点的next. 使用嵌套类 这个节点作为一个相对独立的数据结构, 我们更希望让他单独作为一个类来维护. 再另外创建一个名为LinkedList的class与用户进行交互. 这样还有另一个好处就是提供一个命名为LinkedList的类给用户交互，用户更直观地知道自己是在调用链表。如果直接与node类交互，用户可能会困扰. 但同时考虑到这个node类只有LinkedList会调用，所以我们可以把node类嵌套进LinkedList中。 public class LinkedList<XXX> { private class OneNode { public XXX item; public OneNode next; public OneNode(XXX i, OneNode n) { item = i; next = n; } } private OneNode first; private int size; public LinkedList(XXX x) { first = new OneNode(x, null); size = 1; } //下面是各种方法....

列表 List 前面说到Java的数组无法更改长度，那么也就无法实现插入或者删除数组成员。Java提供了功能更丰富的数据结构 - 列表（list）。所谓列表，即有序的集合（序列），用户可以精确地控制每个元素插入到列表中的哪个位置。用户可以通过整数索引（列表中的位置）来访问元素，并搜索列表中的元素（详细可进一步参考oracle官网）。 这里我们尝试以java的array为基础实现一个列表，目标是实现自动扩容 (Java中的ArrayList不仅仅有自动扩容, 也继承了[List]的其他功能)。在探索的过程中, 可以顺带学习很多相关的内容. 使用自上而下的设计思想搭建一个框架: 先写出最基础的部分, 也就是一个构造器，前面学过了整数数组，我们直接拿来用 /** Array based list. */ // index 0 1 2 3 4 5 6 7 // items: [6 9 -1 2 0 0 0 0 ...] // size: 5 public class AList { private int[] items; private int size; /** 构造一个初始容量100的数组，初始有效数据成员为0. */ public AList() { items = new int[100]; size = 0; } /** 下面添加其他方法 */ } 然后思考我们需要什么功能，把功能需求转化为实例方法instance method的形式，先把方法的外壳描绘出来，注释上该方法的功能（目的），输入值，返回值是什么之类的。具体的功能实现可以先空着，之后一步步丰富。...

数组（Array） 数组是一种特殊的对象，有一个固定的数组长度参数N，由一连串（N个）连续的带编号的内存块组成，每个都是相同的类型(不像Python可以包含不同类型)，索引从0到N-1编号。A[i]获得数组A的第i个元素。这与普通的类实例不同，类实例有具体变量名命名的内存块。 数组实例化，包含对象的数组 Array Instantiation, Arrays of Objects 要创建最简单的整数数组, 有三种方式: x = new int [3]; //创建一个指定长度的数组，并用默认值（0）填充每个内存块。 y = new int [] {1，2，3，4，5}; //创建一个合适大小的数组，以容纳指定的初始值 int [] z = {9，10，11，12，13}; //省略了new，只能结合变量声明使用。 创建一组实例化对象: public class DogArrayDemo { public static void main(String[] args) { /* Create an array of two dogs. */ Dog[] dogs = new Dog[2]; dogs[0] = new Dog(8); dogs[1] = new Dog(20); /* Yipping will result, since dogs[0] has weight 8. */ dogs[0]....

数据类型 数据类型是程序设计语言描述事物、对象的方法。Java数据类型分为基本类型（内置类型）和引用类型(扩展类型）两大类。基本类型就是Java语言本身提供的基本数据类型，比如，整型数，浮点数，字符，布尔值等等。而引用类型则是Java语言根据基本类型扩展出的其他类型，Java要求所有的引用扩展类型都必须包括在类定义里面，这就是Java为什么是面向对象编程语言的原因… 上面的定义有点抽象，要理解数据类型，需要先理解一个问题: 神秘的海象问题 尝试预测下面的代码运行时会发生什么。b的变化是否会影响a？提示：类似Python。 Walrus a = new Walrus(1000, 8.3); Walrus b; b = a; b.weight = 5; System.out.println(a); System.out.println(b); 同样尝试预测下面的代码运行时会发生什么。x的改变是否影响y？ int x = 5; int y; y = x; x = 2; System.out.println("x is: " + x); System.out.println("y is: " + y); 答案是b的变化会影响a, 但x的改变不影响y，具体见可视化过程. 这里的差别虽然微妙, 但其背后的原理对于数据结构的效率来说是非常重要的，对这个问题的深入理解也将引导我们写出更安全，更可靠的代码。 基本类型 Primative Types 计算机中的所有信息都以一系列1和0的形式存储在内存中，这些二进制的0和1就是比特位（bits）。比如72和“H”在内存一般以01001000的形式存储，对他们的形式是一样的。一个引申问题就是：Java代码如何解释01001000，怎么知道应该解释为72还是“H”？ 通过类型types，预先定义好类型即可, 以下代码 char x = 'H'; int y = x; System.out.println(x); System.out.println(y); 会分别得到“H”和72. 在这种情况下，x和y变量都包含几乎相同的bits，但是Java解释器在输出时对它们进行了不同的处理。 Java有8种基本类型：byte，short，int，long，float，double，boolean和char。 变量声明 Declaring Variables...

嵌套类 我们经常需要在某个类A中使用另一个类B，如果设计时我们知道类B只有在类A中有被使用的可能性, 那么我们可以把类B定义在类A中, 作为类A的嵌套类, 类A就称之为外部类. 这样做可以隐藏类名，减少全局的标识符，从而限制用户能否使用该类建立对象。这样可以提高类的抽象能力，并且强调了两个类(外围类和嵌套类)之间的主从关系。 A nested class is any class whose declaration occurs within the body of another class or interface. A top level class is a class that is not a nested class. 嵌套类分为两类：静态和非静态。声明为static的嵌套类简称为静态嵌套类。非静态嵌套类称为内部类(inner class)。 class OuterClass { ... static class StaticNestedClass { ... } class InnerClass { ... } } 作为OuterClass的成员，嵌套类可以声明为private，public，protected或package private。外部类只能声明为public或package private。更多详情参考官网. 内部类 内部类可以直接访问外部类的方法和变量(即使是private的也可以)。如果从外部类程序代码中初始化内部类, 此内部对象会绑在该外部对象上. 一个内部类的实例作为成员存在于所属外部类的实例中。 public class Outer { private int outVar; class Inner { public int inVar; void go() { outVar += inVar; } } Inner myInner = new Inner(); public void do() { myInner....

Class 类的方法和变量细分为静态的和非静态的. 静态就是可以被类调用，所以静态方法/变量也称之为类方法/变量；非静态只能由实例调用，所以也称之为实例方法/变量。 静态变量 类变量 Class Variables 有static声明(静态变量). 静态变量一般是类本身固有的属性, 被该类所有实例共享。例如，我们可能需要用狗类的另一种生物学的统称“犬科”来作为类的说明， 这个时候可以用public static String binomen = "犬科";，这个变量理论上是由类来访问的。静态方法也类似. 以下代码定义了一个类来模拟狗，包含一个类变量作为这个类的说明，一个类方法用于发出叫声： public class Dog { public static String instruction = "狗类实例"; //类变量, 说明 public static void makeNoise() { System.out.println("汪!"); } } 这里没有定义main(), 在这种情况下如何直接运行这个类(java Dog), 程序是会报错的 错误: 在类 Dog 中找不到 main 方法, 请将 main 方法定义为: public static void main(String[] args) 否则 JavaFX 应用程序类必须扩展javafx.application.Application. 你可以选择在里面添加一个main()方法. 但这次我们选择不定义具体的main(). 具体要如何运行, 我们可以另写一个类定义一个main()方法来调用这个类. public class DogLauncher { public static void main(String[] args) { Dog....

Class Java的语法是为了更容易地模拟真实世界而设计的. 比如用程序实现一只狗, 可以用定义一个类class来描述它. 类class里面包括变量Variable，方法method（可以理解为Python的函数function）。变量可以储存数据，方法可以处理数据。变量必须在类中声明(即不能离开类独立存在)，不像Python或Matlab这样的语言可以在运行时添加新的变量。 构造对象的过程: 声明(declaration)引用变量: Dog smalldog; 创建对象：实例化 new Dog(20), 如果没有把它作为值赋给一个类声明变量, 那么这个实例化的值会被垃圾回收. 连接对象和引用：赋值对象给引用Dog smalldog = new Dog(5) 创建对象这一步，调用了Dog(), 不是普通的方法, 而是类的构造函数 Constructors. 构造函数 构造函数在初始化一个对象时执行, 构造函数与类名同名且没有返回类型, 而且可以带参数： /** 注意：构造函数与class类同名 但没有返回类型 */ public Dog(int w) { weight = w; } 然后在DogLauncher里实例化一只狗时, 直接Dog d = new Dog(20);即可. 在以上代码的基础上, 后续当我们想使用new和参数创建一只狗时，可以随时调用public Dog(int w)构造函数。对于熟悉Python的人来说，你可以理解java的构造函数为Python的__init__。 Java可以有与类同名的方法，只是要指明返回类型。 构造函数无法被继承 如果类有一个以上的构造函数，则参数一定要不一样，包括参数顺序和类型 构造函数链 执行new指令会启动构造函数的连锁反应(Constructor Chaining), 首先会执行其父类的构造函数, 依此类推连锁反应到Object类为止. 就算是抽象类, 也会有构造函数, 虽然不能被直接实例化, 但也会被唤醒. 理论上，每个类的构造函数需要先调用其父类的构造函数super()，依次入栈 public class Duck extends Animal { int size; public Duck(int newSize) { super(); // 调用父类构造函数, 且必须是在函数中的第一行 size = newSize; } } 如果明确写了super();, 则必须位于构造函数第一行....

代码风格与注释 努力保持代码可读性。良好的编码风格的一些最重要的特点是： 一致的风格（间距，变量命名，缩进风格等） 大小（线不太宽，源文件不要太长） 描述性命名（变量，函数，类），例如变量或函数名称为年份或getUserName而不是x或f。让代码本身提供可解读性。 避免重复的代码：若有两个重要的代码块及其相似，应该想办法合并。 适当的评论, 使其他读者也能轻松理解你的代码 行注释: //分隔符开头行被当做注释。 Block（又名多行注释）注释: /*, */ , 但我们更推荐javadoc形式的注释。 Javadoc Javadoc: / **，*/, 可以（但不总是）包含描述性标签。 借助javadoc工具可以生成HTML格式的API文档。 第一段是方法的描述。描述下面是不同的描述性标签, 比如参数 @param， 返回值 @return， 可能抛出的任何异常 @throws /** * @author 名字，邮箱<address @ example.com> * @version 1.6 版本 * @param * @return */ public class Test { // class body }

Java基本语法 public class HelloWorld { public static void main(String[] args) { System.out.println("Hello world!"); } } 上面的程序由一个类声明组成，该声明使用关键字public class声明。 Java所有的代码都应该包含在class里面。 真正负责运行的代码，是一个名为main的method，它声明为public static void main(String[] args)。 public：公共的，大部分方法都是以这个关键字开始的，后面会进一步解释。 static：这是一个静态方法，不与任何特定的实例关联，后面会解释。 void：它没有返回类型。 main：这是方法的名称。 String [] args：这是传递给main方法的参数。 使用大括号{ }来表示一段代码的开始和结束。 声明必须以分号结尾 静态分类 Static Typing 程序语言静态与动态的分类，可以参考oracle的说明文件，它解释了动态和静态类型之间的区别, 帮助你理解由程序的错误提示信息。 两个主要区别: 1. 动态类型语言在运行时执行类型检查，而静态类型语言在编译时执行类型检查。这意味如果以静态类型语言（如Java）编写的脚本包含错误，则在编译错误之前将无法编译. 而用动态类型语言编写的脚本可以编译，即使它们包含会阻止脚本正常运行（如果有的话）的错误。 2. 静态类型语言要求你在使用它们之前声明变量的数据类型，而动态类型语言则不需要。 考虑以下两个代码示例： // Java int num; num = 5; # Python num = 5 这两段代码都创建一个名为num的变量并赋值为5. 不同之处在于Java需要将num的数据类型明确定义为int。因为Java是静态类型的，因此它期望变量在被赋值之前被声明。 Python是动态类型的，不需要定义类型, Python根据变量的值确定其数据类型。动态类型语言更加灵活，在编写脚本时可以节省时间和空间。但是，这可能会导致运行时出现问题。例如： # python number = 5 numbr = (number + 15) / 2 #注意错字 上面的代码本应创建一个值为5的可变数字，然后将其加上15并除以2以得到10....