二:Collection顶级接口讲解
- Collection
- List (有序集合,允许相同元素和null)
- LinkedList (非同步,允许相同元素和null,遍历效率低插入和删除效率高)
- ArrayList (非同步,允许相同元素和null,实现了动态大小的数组,遍历效率高,用的多)
- Vector(同步,允许相同元素和null,效率低)
- Set (无序集合,不允许相同元素,最多有一个null元素)
- HashSet(无序集合,不允许相同元素,最多有一个null元素)
Collection是最基本的集合接口(也可以称为顶级接口)
在Collection的实例中,有些实例允许相同的元素,有些则不允许,还有一些能内置实现排序功能,所以 根据存储数据的方式(数据结构)各有不同,所以存储的容器也就有多种,从而形成了集合框架这一体 系
同时,在Java中不提供直接继承自Collection的类,Java所提供的类都是继承自Collection的“子接口”:
List和Set 常用的方法:| boolean add(Object o) | 添加对象到集合 |
| boolean remove(Object o) | 删除指定的对象 |
| int size() | 返回当前集合中元素的数量 |
| boolean contains(Object o) | 查找集合中是否有指定的对象 |
| boolean isEmpty() | 判断集合是否为空 |
| Iterator iterator() | 返回一个迭代器 |
| boolean containsAll(Collection c) | 查找集合中是否有集合c中的元素 |
| boolean addAll(Collection c) | 将集合c中所有的元素添加给该集合 |
| void clear() | 删除集合中所有元素 |
| void removeAll(Collection c) | 从集合中删除c集合中也有的元素 |
| void retainAll(Collection c) | 从集合中删除集合c中不包含的元素 |
- 集合中如果没有元素了 就会为true
- 在之前学习的el表达式中 ${empty ls} 如果ls中没有任何元素,得到的也是一个true
三:关于Collection的遍历操作:Iterable接口与Iterator接口
查看Collection的源代码:
得出结论:
Collection下的集合都间接继承了Iterable
观看Iterable接口源码
因为Collection继承了Iterable,所以它以下的实现类也都会具备 iterator()这个方法
我们可以通过这个方法来获得一个iterator(),也就是一个迭代器
关于迭代器中的方法,我们可以通过查看iterator()的源码
通过画图法来理解迭代器的运行原理
- 当Iterator对象创建完成时,这时的指针其实指向的是第一个元素的上方,即指向一个空
- 调用hasNext方法时,判断当前箭头的下一个是否存在(集合是否到了末尾,然后返回boolean类 型)
- 调用next方法时,箭头向下移动一位,并且返回箭头所在的元素
- 调用remove方法时,移除当前箭头所在的元素
使用ArrayList来演示迭代器的使用
ArrayList
结果:
四:讲解List集合与其实现类
Collection的子接口,这个接口所具备的特征: 可重复 , 有序
可重复:在集合内部,一个元素可以出现多次,也就是在集合中可以占有多个位置 Person p=new Person(); List这里 有序 要讲解清楚,ls=new ArrayList (); ls.add(p); ls.add(p); ls.add(p); 集合的长度 size=3 得出结论: p这个元素在集合中重复了三次,占了三个位置,这就是可重复
List中的有序指的不是内部的元素会以某种格式排序,而是指其中的每个元素在进入集合时都是有添加顺序的 先添加的在前面,后添加的在后面,这些位置是有序的 也就是 0,1,2,3,4.... (我们称之为下标) List在添加元素的时候,集合的长度是随着元素的增多而随之增多的,但是不会每次都 +1,而是有着自己的扩容机制 以 ArrayList 而言:ls=new ArrayList (); ls.add("jack"); ls.add("mary"); ls.add("eason"); jack的下标是1 mary的下标是2 eason的下标是3 add这个方法是在集合的最后一位添加元素,下标也就会随着变大 在add的时候还可以指定当前添加的元素的位置 -> ls.add(2,"asong"); 将 asong 放入集合的第2位 未添加 asong 时: [jack, mary, eason] 添加了 asong 后: [jack, mary, asong, eason] 需要注意的是,指定的位置必须小于当前集合的最大下标 同时,因为List是有序的,我们除了可以按照顺序(下标)插入之外,也可以按照顺序(下标)来读取与删除 读取: ls.get(0),根据下标来读取的方式我们一般称为随机读取 删除: ls.remove(0) 根据下标移除第0位 ls.remove("jack") 移除集合中的 jack ,集合中是使用equals来判断的
当集合实例化的时候,默认的大小为10,我们也可以在实例化的时候调用对应的构造来创建响应的大小
List因为无参实例集合的初始长度为 10 ,当我们添加的元素超过 10位的时候,集合的大小就不够了,需要扩容 每次添加的时候,都调用 grow 方法判断是否需要扩容ls=new ArrayList (15)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
让我们查看
grow
方法 :
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
- ArrayList的扩容因子是1.5 : 原容量的0.5倍
- ArrayList的容量为10,一次扩容后是容量为15
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
Vector :
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
基于对象数组的集合最大的好处就是读取非常快,因为是随机读取,但是修改的速度比较慢,如果在项目中遇到了需要非常频繁的对集合中的元素进行修改的操作,可以使用链表结构的集合
- 链表结构
- LinkList的使用
LinkedListls=new LinkedList (); ls.add("jack"); ls.add("jack1"); ls.add("jack2"); ls.add("jack3"); System.out.println(ls.get(1));//jack1 虽然我们是通过下标来取值,但是在内部,还是得从链表开头一直查,查询到链表的对应位置
- LinkList特有方法
addFirst(); 添加在第一个 addLast(); 添加在最后一个 getFirst(); 得到第一个 getLast(); 得到最后一个 removeFirst(); 移除第一个 removeLast(); 移除最后一个
- List常见面试题
①:List,Set都是继承自Collection接口。List特点:元素有放入顺序,元素可重复 。Set特点:元素无放入顺序,元素不可重复。注意,元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的。
②、其实,有序或无序是指是否按照其添加的顺序来存储对象。List 是按照元素的添加顺序来存储的。而 Set 的实现类都有一套自己的排序算法,每添加一个元素,都会按照其内部算法将元素添加到合适的位置,所以Set集合不能有重复的元素,也不能保证内部存储是按元素添加的顺序而存储的。
vector和数组类似,它拥有一段连续的内存空间,并且起始地址不变,因此它能非常好的支持随机存取(即使用[]操作符访问其中的元素),但由于它的内存空间是连续的,所以在中间进行插入和删除会造成内存块的拷贝(复杂度是O(n)),另外,当该数组后的内存空间不够时,需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。
list是由数据结构中的双向链表实现的,因此它的内存空间可以是不连续的。因此只能通过指针来进行数据的访问,这个特点使得它的随机存取变的非常没有效率,需要遍历中间的元素,搜索复杂度O(n),因此它没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除和插入。
ArrayList:
在动态数组中,存储数据用的是一段连续的大内存,所以如果我们要在某一个位置添加或者删除一个元素,剩下的每个元素都要相应地往前或往后移动。
如果该动态数组中的元素很多,那么,每当我们添加或删除一个元素后,需要移动的元素就非常多,因此,效率就比较低。
而查找的时候,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。
这就是为什么ArrayList的查找效率高,而增删操作的效率低了。
LinkedList:
LinkedList是基于双向链表的数据结构实现的,链表是可以占用一段不连续的内存空间的,
双向链表有前驱节点和后驱节点,里面存储的是上一个元素和后一个元素所在的位置。
当我们需要执行插入的任务,只需要改变他们的前驱节点和后驱节点的指向就可以了,不要像动态数组那么麻烦,删除也是同样的操作,
但是因为是不连续的内存空间,当需要执行查找,需要从第一个元素开始查找,直到找到我们需要的数据。
arraylist扩容就是根据旧数组和计算出的新长度copyof出新数组返回给elementData,arraylist初始是final修饰空数组长度0,当添加第一个元素时默认创建长度10的数组,之后扩容就是1.5倍进行扩容
5.ArrayList和LinkedList的区别?分别用在什么场景?ArrayList使用在查询比较多,但是插入和删除比较少的情况,LinkedList使用在查询比较少而插入和删除比较多的情况。
ArrayList底层使用是数组,LinkedList使用的是链表。
数组查询具有所有查询特定元素比较快。而插入和删除和修改比较慢(数组在内存中是一块连续的内存,如果插入或删除时需要移动内存)
链表不要求内存是连续的,在当前元素中存放下一个或上一个元素的地址,查询时需要从头部开始,一个一个的找,所以查询效率低。插入时不需要移动内存,只需要改变引用指向即可。所插入或者删除的效率高。
7.ArrayList、LinkedList、Vector区别
ArrayList:以连续的数组结构存储数据,查询快(下标)、增删改慢
LinkedList:以链表的结构存储数据,查询慢、增删改快
Vector:增删改查都慢,已过时



