1.什么是链表?
链表是可以将物理地址上不连续的数据连接起来,通过指针来对物理地址进行操作,实现增删改查等功能.
链表大致分为单链表和双向链表
单链表:每个节点包含两部分,一部分存放数据变量的data,另一部分是指下一节点的next指针.
双向链表:除了包含单链表的部分还增加的pre前一个节点的指针.
2.链表的优缺点
链表的优点:插入删除速度快(因为有next指针指向其下一个节点,通过改变指针的指向可以方便的增加删除元素)
内存利用率高,不会浪费内存(可以使用内存中细小的不连续空间(大于node节点的大小)),并且在需要空间的时候才创建空间
大小没有固定,扩展很灵活.
链表的缺点:不能随机查找,必须从第一个开始遍历,查找效率低.
3.什么是红黑树
红黑树是一种含有红黑节点并能自平衡的二叉查找树,他必须满足下面性质:
(1)每个节点要么是黑色,要么是红色
(2)根节点是黑色
(3)每个叶子节点(NIL)是黑色
(4)每个红色节点的两个子节点一定都是黑色
(5)任意一节点到每个叶子节点的路径都包含数量相同的黑节点
4.常用的集合类有哪些?
Map接口和Collection接口是所有集合框架的父接口:
Collection接口的子接口包括:Set接口和List接口
Map接口的实现类有:HashMap,TreeMap,Hashtable,ConcurrentashMap以及Properties等
Set接口的实现类有:HashSet,TreeSet,LinkedHashSet等
List接口的实现类主要有:ArrayList,LinkendList,Stack以及Vector等
5.那些集合类是线程安全的?
Vector:就比ArrayList多了个synchronized(线程安全),因为效率较低,现在已经不太建议使用.
hashTable:就比hashMap多了个synchronized(线程安全),不建议使用
ConcurrentHashMap:是Java5中支持高并发,高吞吐量的线程安全HashMap实现,
6.遍历一个List有哪些不同的方式?
(1)for循环遍历,基于计算器,在集合外部维护一个计算器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止
(2)迭代器遍历,Iterator,Iterator是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口,Java在Conllections中支持了Iterator模式.
(3)foreach循环遍历,foreach内部也是采用了Iterator的方式实现,使用时不需要显示声明Iterator或计数器,优点是代码简介,不易出错,缺点是只能做简单的遍历,
不能在遍历过程中操作数据集合,例如删除,替换.
7.如何实现数组和List之间的转换?
数组转List:使用Arrays,asList(array)进行转换
List转数组:使用List自带的toArray()方法
数组转set:使用构造函数,直接转入数组
new HashSet(arrays[])
8.如何把一个线程不安全的集合转化为线程安全集合?
向HashSet中add()元素时.判断元素是否存在的依据,不仅要比较hash值,同时还要结合equals方法比较,
HashSet中的add()方法会使用HashMap的put()方法.HashMap的key是唯一的,在HashMap中如果k/y相同时,会用新的V覆盖掉旧的V,然后返回旧的V,所以不会重复
9.说一下HashSet的实现原理?
HashSet是基于HashMap实现的,HashSet的值存放与HashMap的Key上,HashMap的Value统一为present,因此HashSet的实现比较简单
相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成,HashSet不允许重复的值,
10.HashSet如何检查重复?HashSet是如何保证数据不可重复的?
向HashSet中add()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles方法比较,
HashSet中的add()方法会使用HashMap的put()方法,
HashMap的key是唯一的在HashMap中如果k/v相同时,会用新的V覆盖掉旧的V,然后返回旧的V,所以不会重复
标签：面试题,遍历,Java,HashMap,HashSet,接口,Day04,链表,节点 From： https://www.cnblogs.com/carney/p/17033849.html