A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

就业班Day03数据结构及数组简记

数据结构_栈
        先进后出(入口出口在同一侧)
        入栈:将元素入栈
        出栈:将元素取出
        使用场景:
        栈内存(main方法先进栈,只有在main方法中的命令运行完毕之后,main方法才出栈)
        反转内容(先进入后取出的特性,反转集合的元素)
数据结构_队列
        先进先出(入口出口在集合的两侧)
        使用场景:
        秒杀,抢购
        在线售票
        处于高并发场景
数组结构_数组
        查询快:数组的地址是连续的,我们通过数组的首地址可以找到数组,通过数组的索引可以快速查找某一个元素
        增删慢:数组的长度是固定的,我们想要删除/增加一个元素,必须创建一个新数组,把原数组的数据复制过来
        要把数组中的元素删除,必须创建一个新数组,长度是源数组的长度-1,把源数组的其他元素复制到新数组中,在新数组的地址赋值给变量arr,源数组会在内存中被销毁(垃圾回收)
数据结构_链表
        查询慢:链表中地址不是连续的,每次查询元素,都必须从头开始查询
        增删快:链表结构,增加/删除一个元素,对链表的整体结构没有影响,所以增删快
        单项链表:只能从头向后查,只有一根链条(本身存储数据和下一个地址值)
        双向链表:可以从前向后查,也可以从后向前查,是双向的,但其本身还是一根链条(本身存储数据,下一个地址值,以及上一个地址值)
        双重链表:两根链条,真正能够保证元素有序的结构,其中一根链条专门存储数据的存储顺序
        链表中的每一个元素也称之为一个节点,一个节点包含了一个数据源(存储数据)两个指针域(存储地址)
数据结构_红黑树
        二叉树:分支不能超过两个
排序树/查找树
        在二叉树的基础上,元素是有大小顺序的,左子树小,右子树大
平衡树
        左子树个右子树相等
        不平衡树:左孩子不等于右孩子
红黑树:
        特点趋近于平衡树,查询的速度非常快,查询叶子节点最大次数和最小次数不能超过2倍
        约束:
        1.节点可以是红色的或者黑色的
        2.根节点是黑色的
        3.叶子节点(空节点)是黑色的
        4.每个红的节点的子节点都是黑色的
        5.任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
List集合
        List接口的特点:
        1.有序集合,存储元素和取出元素的顺序是一致的(存储123取出123)
        2.有索引,包含了一些带索引的方法
        3.允许存储重复的元素
        (注意:set只能在集合存在的索引中进行元素的替换,不能在末尾进行添加)
        List接口中带索引的方法(特有)
        public void  add ( int index,E element);将制定的元素,添加到该集合指定的位置上
        public E remove (int index):移除列表中指定位置的元素,返回的是被移除的元素
        public E set (int index ,E element):用指定元素替换集合中指定位置的元素,返回值为更新前的元素
        public E get (int index):返回集合中指定位置的元素
        注意:操作索引时,一定要防止索引越界异常
        IndexOutOfBoundsExpections索引越界异常
ArrayList集合
        集合数据存储结构是数组结构.元素增删慢,查找快,线程不安全,效率高
LinkedList集合
        集合数据存储的结构是链表结构(双向链表).方便元素的添加,删除的集合
        LinkedList集合的特点
        1.底层是一个链表结构:查询慢,增删快,线程不安全,效率高
        2.里边包含了大量操作首尾元素的方法
        注意:使用LinkedList集合特有的方法,不能使用多态
        public void addFirst(E e) :将制定元素插入此列表的开头
        public void addLast(E e) :将指定元素添加到此列表的结尾
        public void push(E e):将元素推入此列表所表示的堆栈(此方法等效于addFitst)
        public E getFirst():返回此列表的第一个元素
        public E getLast():移除并返回此列表的最后一个元素
        public E removeFirst():移除并返回此列表的第一个元素
        public E removeLast():移除并返回此列表的最后一个元素
        public E pop():从此列表所表示的堆栈处弹出一个元素(此方法等效于removeFirst)
        public boolean isEmpty():如果列表不包含元素,则返回true.
Set接口
        特点:
        1.不允许存储重复的元素
        2.没有索引,没有带索引的方法,也不能使用普通的for循环遍历
        HashSet集合implement Set接口
        HashSet特点
        1.不允许存储重复的元素
        2.没有索引,没有带索引的方法,也不能使用普通的for循环遍历
        3.是一个无序集合,存储元素和取出元素的顺序有可能不一致(有序,无序:存入和取出的顺序;排序:从小到大,从大到小)
        4.底层是一个哈希表结构(查询速度很快)
哈希值
        定义:哈希值是一个十进制的整数,由系统随机给出 (就是对象的地址值,是一个逻辑地址,是模拟出来的地址,不是数据实际存储的物理地址)
        在object类有一个方法,可以获取对象的哈希值
        int hashCode()返回该对象的哈希码值.
        hashCode方法的源码:
        public native int hashCode();
        native:代表该方法调用的是本地操作系统的方法
        由于Objcet为所有类的父类,所以任何类都可以调用hashCode方法
HashSet集合存储数据的结构(哈希表)
        jdk1.8版本之前:哈希值=数组+ 链表
        jdk1.8版本之后:
                哈希表=数组+链表
                哈希表=数组+红黑树(提高查询速度)
        哈希表的特点:速度快
        在HashSet中,元素不同,但是哈希值相同,这种情况被誉为哈希冲突
        数组结构:把元素进行分组,(相同哈希值的元素是一组)链表/红黑树结构把相同哈希值的元素连接在一起,如果链表的长度超过了8位,那么就会把链表转为红黑树(提高查询结构)
Set集合不允许存储重复元素的原理
        Set集合在调用add方法的时候,add方法会调用元素的hashCode方法个equals方法,判断元素对否重复,重复则不添加到存储集合中,不同则将元素加入到存储集合之中
HashSet存储自定义类型元素
        set集合保存元素唯一
         存储的元素(String,Interer.....Student,Person..必须重写hashCode方法和equals方法)
LinkedHashSet集合
        LinkedHashSet集合extends HashSet集合
        LinkedHashSet集合特点:
        底层是一个哈希表(数组+链表/红黑树)+链表:多了一个链表(记录元素的存储顺序)保证元素有序
        HashSet
                无序,不重复
        LinkedHashSet
                有序,不重复
        LinkedHashCode没有索引
可变参数
        使用前提:
        当方法的参数列表数据类型已经确定,但是参数的个数不确定,就可以使用可变参数
        使用格式:
        修饰符 返回值类型 方法名(数据类型...变量名){}
        可变参数原理:
        可变参数底层就是一个数组,根据传递参数个数不同,会创建不同长度的数组,来存储这些参数传递的参数个数,可以是0个(不传递),1.2....多个
        可变参数的注意事项:
        1.一个方法的参数列表,只能有一个可变参数
        2.如果方法的参数有多个,那么可变参数必须写在参数列表的末尾
        可变参数的终极写法
        public static void method(object.....obj){}
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):将集合中元素按照默认规则排序
        注意:
        sort(List<T>list)使用前提
        被排序的集合里边存储的元素,必须实现Comparable,重写接口中的方法compareTo定义排序的规则
        Compareable接口排序规则
        自己(this)-参数:升序,反之为降序
        public static <T> void sort(List<T> list,Comparator<?super T):将集合中元素按照指定规则排序.
        Comparator与Comparable的区别
        Comparable:自己(this)和别人(参数)比较,自己需要实现Comparable接口,重写比较的规则Compareto方法
        Comparator的排序规则
        o1-o2升序反之降序
       


0 个回复

您需要登录后才可以回帖 登录 | 加入黑马