Skip to content

003.md

Latest commit

 

History

History
211 lines (121 loc) · 6.74 KB

003.md

File metadata and controls

211 lines (121 loc) · 6.74 KB
Raw

数据结构

栈

一种运算受限的线性表，只允许在一端进行插入和删除操作，不允许在任何其他位置进行添加、查找、删除的操作。

特点：

  • 先进后出

  • 栈的入口、出口都是栈的顶端位置

img

队列

一种运算受限的线性表，只允许在表的一端进行插入操作，在表的另一端进行删除操作。

特点：

  • 先进先出
  • 队列的入口、出口各占一侧

img

数组

一种有序的元素序列，在内存中开辟一段连续的空间并在此空间存放元素

特点：

  • 查找元素快（通过索引）
  • 增删元素慢（需要创建新数组，复制数据）

链表

由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是指针域。常用的链表结构有单向链表与双向链表。

特点：

  • 多个结点之间，通过地址进行连接
  • 查找元素慢（通过连接的结点依次向后查找，每次查询元素必须从头开始）
  • 增删元素快（修改指针，对链表的总体结构没有影响）

红黑树

树有多个节点，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。

  • 二叉树：二叉树是一种特殊的树，二叉树的每个节点最多只能有2个子节点。

    img

  • 排序树/查找树：在二叉树的基础上，元素是有大小顺序的，左子树小、右子树大。

    img

  • 平衡树：左右子树的高度相差不超过 1 的树为平衡二叉树。

    img

  • 红黑树

    特点：趋近于平衡树，查询速度非常的快，查询叶子结点最大次数与最小次数不超过2倍

    约束条件

    1. 结点可以是红色或黑色

    2. 根结点是黑色

    3. 叶子结点是黑色

    4. 每个红色结点的子结点都是黑色

    5. 任何一个结点到每一个叶子结点的所有路径上黑色结点数量相同

      An example of a red-black tree

List接口

java.util.List接口继承自Collection接口，是单列集合的一个重要分支

  • 特点：

    1. 有序的集合，存储元素和取出元素顺序一致
    2. 有索引，包含了一些带索引的方法
    3. 允许存储重复的元素

  • 特有方法：

    1. public void add(int index, E element):将指定的元素添加到指定的位置上
    2. public E get(int index):返回集合中指定位置的元素
    3. public E remove(int index):移除集合中指定位置的元素
    4. public E set(int index, E element):用指定元素替换集合中指定位置的元素（返回值为替换前的元素）

  • 注意：防止IndexOutOfBoundsException异常

  • List的实现类

    1. ArrayList：大小可变的数组实现，此实现不是同步的

    2. LinkedList：链表结构，方便元素添加、删除的集合，此实现不是同步的

      特有方法：

      public void addFirst(E e):将指定元素插入链表开头

      public void addLast(E e):将指定元素插入链表结尾

      public void push(E e):将指定元素插入此列表所表示的堆栈

      public E getFirst():返回链表开头元素

      public E getLast():返回链表结尾元素

      public E removeFirst():移除链表开头元素

      public E removeLast():移除链表结尾元素

      public E pop():从此列表所表示的堆栈弹出一个元素

      public boolean isEmpty():判断链表是否为空

      注意：防止NoSuchElementException异常

    3. Vector：可以实现可增长的对象数组，此实现是同步的

Set接口

java.util.Set接口继承自Collection接口，是单列集合的一个重要分支

  • 特点：

    1. 不允许存储重复的元素
    2. 没有索引，也没有带索引的方法

  • Set的实现类

    1. HashSet：是一个无序的集合，底层是一个哈希表结构（查询速度非常快）

      哈希值：是一个整数，由系统直接给出，在Object类中int hashCode()可以获取对象的哈希值

      哈希表结构：JDK1.8+之后数组+红黑树，把元素进行分组（相同哈希值是一组），红黑树把一组元素连接到一起

      add方法会调用hashcode和equals方法，存储自定义元素时，必须重写hashcode和equals方法

    2. LinkedHashSet：继承了HashSet类，具有可预知迭代顺序的Set接口的哈希表和链表的实现

      多了一重链表（记录元素的存储顺序），保证元素有序

  • 可变参数

    JDK1.5+之后出现的新特性

    修饰符 返回值类型 方法名(参数类型... 形参名){
    方法体
}

    等价于

    修饰符 返回值类型 方法名(参数类型[] 形参名){
    方法体
}

    注意事项：

    1. 一个方法的参数列表只能有一个可变参数

    2. 如果一个方法的参数有多个，可变参数必须写在参数列表的末尾

    3. 可变参数的特殊写法

      public static void method(Object... obj){
    方法体
}

Collections

java.utils.Collections是集合工具类，用来对集合元素进行操作，常用方法如下：

  • public static <T> boolean addAll(Collection<T> c, T... elements):往集合中添加一些元素
  • public static void shuffle(List<?> list):打乱集合顺序
  • public static <T> void sort(List<T> list):将集合中元素按照默认规则排序（升序）
  • public static <T> void sort(List<T> list, Comparator<? Super T>):将集合中元素按照指定规则排序

注意：

  1. sort方法的使用前提：被排序的集合里存储的元素，必须实现Comparable接口，重写compareTo方法定义排序的规则

  2. 排序规则：this-参数->升序；参数-this->降序

  3. Comparator可以写成匿名内部类

    Collections.sort(list,new Comparator<Student>(){
    @Override
    public int compare(Student o1,Student o2){
        方法体
    }
})

​