就业班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升序反之降序
|