JavaWeek3-泛型,树和集合List接口

泛型

泛型是指在编程语言中支持类型参数化的一种机制 , 核心在于类型参数化 , 即在定义类、接口或方法时 , 使用占位符 ( 通常用大写字母表示 ) 来代表具体的类型 . 这些占位符在实际使用时会被具体的类型所替代 .

如果没有给集合指定泛型 ( ) , 则默认认为未来添加进集合的所有数据类型都是 Object 类型 , 此时可以向集合添加任意数据类型 , 但在获取类型时无法使用该类的特有方法 .

public class Box<T> { // T仅支持引用数据类型和其子类型
    private T content;

    public void setContent(T content) {
        this.content = content;
    }

    public T getContent() {
        return content;
    }
}

继承性

泛型不具有继承性 , 数据具有继承性 .

传递含泛型限制的参数的方法在调用时 , 严格接受泛型所指定的数据类型 , 不能传入该数据类型的子类 : 泛型不具有继承性 .

创建泛型限制的数据类型对象时 , 允许传入其限制泛型类型的子类 : 数据具有继承性 .

Dog 是 Animal 的子类 , 但 ArrayList 不是 ArrayList 的子类 .

通配符

程序员有时希望某方法有多个泛型限制 , 可以使用泛型通配符 ? 实现这个需求 .

<? extend E> 表示限制允许传递 E 和 E 的所有子类类型 ; <? super E> 表示限制允许传递 E 和 E 的所有父类类型 .

树

二叉树 是一种非线性数据结构 , 代表父节点和左右子节点之间的派生关系 , 体现了 分治 的思想 . 每个节点包括 左右子节点的地址 ( 若无则为 null ) , 节点字段 , 节点颜色 ( 红黑树 ) 和 <父节点的地址> 等数据 .

术语

根节点 : 位于二叉树的顶层 , 没有父节点的节点 .

叶节点 : 位于二叉树的底层 , 没有子节点的节点 .

边 : 连接两个节点的指针 .

层 : 由顶到底递增 , 根节点所在层为 1 .

度 : 节点的子节点的数量 N ∈ { 0, 1, 2 } .

高度 : 根节点到最远叶节点所经过的边的数量 .

三序遍历

树的前序 , 中序和后续遍历都属于 深度优先遍历 , 序前的 前 , 中 , 后序表示子树根节点所在的位置 , 前序即按照根节点 , 左子树 , 右子树的顺序进行遍历 .

搜索树

对于任意节点 , 左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值 .

插入节点时 , 若节点值大于当前节点的值则插入右子树 ; 若节点值小于当前节点的值则插入左子树 ; 若节点值等于节点值则不做处理 . 若当前节点为空则插入该位置 .

AVL 二叉平衡树

搜索树在最坏条件单边树的情况下搜索效率低至O(n) , 平衡树在搜索树的基础上增加了限制规则 : 任意节点左右子树高度差不超过 1 .

当插入节点破坏规则后树会进行左旋或右旋处理进行优化 .

左右旋

插入节点后向上寻找不平衡父节点 , 沿 父节点 - 根节点 - 另向 的轨迹进行旋转 , 将节点的右子树提升为新的父节点 , 将原节点作为新父节点的左子树 , 将新父节点与左子树的边接到原节点和该左子树之间 ( 左旋 ) .

左旋前：
    A
     \
      B
     / \
    C   D

左旋后：
      B
     / \
    A   D
     \
      C // 右旋同理

插入节点

根据新节点插入树的位置不同 , 采取的旋转方式也不同 :

新节点插入左子树的左子节点时 , 进行右旋即可 .

新节点插入左子树的右子节点时 , 先进行无关根节点的局部左旋 , 再整体右旋 .

新节点插入右子树的左子节点时 , 先进行无关根节点的局部右旋 , 再整体左旋 .

新节点插入右子树的右子节点时 , 进行左旋即可 .

红黑树

红黑树在每个节点中添加了颜色字段 , 使用若干限制规则 :

根节点必须为黑色 ;

边不能连接两个红色节点 ;

红黑树中叶节点的子节点定义为 Nil ( 值为 null ) , 这些 Nil 节点被视为红黑树的叶节点 ;

每个 Nil 节点是黑色的 ;

任意节点到其所有后代叶节点的简单路径均包含相同数目的黑色节点 .

插入节点

插入节点时默认加入红色字段 , 若破坏红黑规则则根据具体明细进行颜色修改和左右旋处理 .

集合

集合分为 单列集合Collection 和 双列集合Map .

Collection 接口

Collection 是单列集合的祖宗接口 , 全部单列集合都可以继承使用其功能 .

遍历

1. 迭代器 Iterator
hasNext()方法用于获取当前迭代器下一索引位置的元素 .

   Iterator<E> it = arr.iterator(); // E是数据类型
   // 迭代器由0索引枚举到尾索引的下一空位null
   // 迭代器遍历结束后不会复位,再次遍历需要重新实例化迭代器
   

2. 增强 for

   ArrayList<E> arr;
   for(E temp; arr) {
       ...
   } // 单列集合和数组允许使用增强for进行遍历
   

3. Lambda 表达式

   // ()->{}
   arr.forEach(s -> System.out.println(s));
   // 集合中的每一元素对应s,箭头指向对s的执行方法
   

List 接口

有序 , 可重复 , 有索引 .

索引方法

1. void add(int index, E element);

2. E remove(int index);
   index与数组元素参数重载时 , 优先调用实参和形参类型一致的方法 , 如1默认为int基本数据类型 , 则优先接受删除1索引的重载方法 . 程序员希望删除1元素时 , 可以通过手动装箱解决这个问题 .

   Integer i = Integer.valueOf(1);
   arr.remove(i);
   // 手动装箱:将字面量装箱赋值给包装类对象
   // remove()方法默认接受对象Object O,对字面量进行操作时需要进行拆箱操作,因此手动装箱可以强调删除指定元素
   

3. E set(int index, E element);

4. E get(int index);

ListIterator 列表迭代器

ListIterator是迭代器接口的实现接口 , 支持反向遍历和指定位置实例化迭代器 .

ListIterator<String> iterator = list.listIterator(list.size());
while(iterator.hasPrevious()) {
    System.out.println(iterator.previous());
}

Arraylist 实现类

利用空参构造的集合在底层创建一个默认长度为 0 的数组 . 添加首个元素时会创建一个新的长度为 10 的数组 elementData , 该数组存满后会扩容一半容量 ; 如果一次添加多个数据使数组元素数量达到当前容量的 1.5 倍以上 , 则新创建数组的长度以添加后数组元素数量为准 .

LinkedList 实现类

LinkedList的底层数据结构是双向链表 .