泛型与链表

泛型

泛型，即“参数化类型”。就是将类型由原来的具体的类型参数化，类似于方法中的变量参数，此时类型也定义成参数形式（可以称之为类型形参），然后在使用/调用时传入具体的类型（类型实参）

泛型类：

定义一个泛型类：

Public classClassName{

private T data;

public T getData(){

return data;

}

Public void setData(T

data) { this.data = data; }

}

泛型接口

Public interface InterfaceName<T>{

TgetData();

}

实现接口时可选择是否指定泛型类型

实现的话将T给予一个基本数据类型：

public class Interface1 implements

IntercaceName<String>

泛型方法

private static <T> T 方法名(T a, T b) {}

泛型限制类型：

在使用泛型时，可以指定泛型的限定区域：

例如：必须是某某类的子类或某某接口的实现类，格式：

<T extends 类或接口1

& 接口2>

泛型中的通配符？

[if !supportLists]1 [endif]<? extends Parent> 指定了泛型类型的上届

[if !supportLists]2 [endif]<? super Child> 指定了泛型类型的下届

[if !supportLists]3 [endif]<?> 指定了没有限制的泛型类型

通配符？与object的区别：

Object可以传输任何类型的数据，通配符？也能传输任何数据类型，但是后续的数据必须与第一个数据的类型相同

注意

[if !supportLists]1 [endif]在编译之后程序会采取去泛型化的措施，也就是说Java中的泛型，只在编译阶段有效

[if !supportLists]2 [endif]在编译过程中，正确检验泛型结果后，会将泛型的相关信息擦出，并且在对象进入和离开方法的边界处添加类型检查和类型转换的方法。也就是说，泛型信息不会进入到运行时阶段。

Objects:

checkIndex(int index): 检查 index是否在 0 （含）到 length （不包括）范围内。

deepEquals(Object a, Object b):返回 true如果参数是深层相等，彼此false其他。

链表：

链表是由一组不必相连的内存结构，按特定的顺序链接在一起的抽象数据类型

数组和链表的区别和优缺点：

数组是一种连续存储线性结构，元素类型相同，大小相等。

数组的优点：存取速度快

缺点：须事先知道数组长度；

插入删除慢；

空间有限制；

需要大块连续的内存块；

插入删除效率低。

链表是离散存储线性结构：n个节点离散分配，通过指针相连，每个节点只有一个后驱节点

优点：空间无限制；

插入删除快。

缺点：存储慢

链表分三类：单链表、双向链表、循环链表。

核心操作：插入、删除、遍历’

二叉树：是树的一种，每个节点最多可具有两个子树，即结点的度最大为 2

包括：斜树、满二叉树、完全二叉树

二叉树性质：

二叉树第 i 层上的结点数目最多为2^(i-1) (i≥1) ；

深度为 h 的二叉树至多有 2^h-1个结点(h≥1)；包含 n 个结点的二叉树的高度至少为 log2 (n+1)；

在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则n0=n2+1。

二叉树的遍历方式，一般分为先序遍历（根->左->右），中序遍历（左->根->右），后序遍历(左->右->根)。