1 集合框架介绍
- 所有集合类都位于java.util包下。Java的集合类主要由两个接口派生而出:Collection和Map,Collection和Map是Java集合框架的根接口,这两个接口又包含了一些子接口或实现类。
- 集合接口:6个接口(短虚线表示),表示不同集合类型,是集合框架的基础。
- 抽象类:5个抽象类(长虚线表示),对集合接口的部分实现。可扩展为自定义集合类。
- 实现类:8个实现类(实线表示),对接口的具体实现。
- Collection 接口是一组允许重复的对象。
- Set 接口继承 Collection,集合元素不重复。
- List 接口继承 Collection,允许重复,维护元素插入顺序。
- Map接口是键-值对象,与Collection接口没有什么关系。
- Set、List和Map可以看做集合的三大类:
- List集合是有序集合,集合中的元素可以重复,访问集合中的元素可以根据元素的索引来访问。
- Set集合是无序集合,集合中的元素不可以重复,访问集合中的元素只能根据元素本身来访问(也是集合里元素不允许重复的原因)。
Map集合中保存Key-value对形式的元素,访问时只能根据每项元素的key来访问其value。
2 纯手写List框架
List集合代表一个有序集合,集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素,可以通过索引来访问指定位置的集合元素。
List接口继承于Collection接口,它可以定义一个允许重复的有序集合。因为List中的元素是有序的,所以我们可以通过使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。
List接口为Collection直接接口。List所代表的是有序的Collection,即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制,同时可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素。实现List接口的集合主要有:ArrayList、LinkedList、Vector、Stack。
3 ArrayList实现
3.1 Arraylist底层基于数组实现
3.2 Arraylist底层默认数组初始化大小为10个object数组
3.3 添加元素后大于当前数组的长度,则进行扩容,将数组的长度增加原来数组的一半。
- add方法
- 判断实际存放的容量是否大于elementData
- 判断是否需要扩容
- 扩容实现
3.4 手写Arraylist底层框架
3.4.1 自定List接口
public interface ExtList<E> {
int size();
boolean add(E e);
void add(int index, E e);
E get(int index);
E remove(int index);
boolean remove(E e);
}
3.4.2 实现List接口
public class ExtArrayList<E> implements ExtList<E> {
private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
/**
* 实际容量大小
*/
private int size;
public ExtArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ExtArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
@Override
public boolean add(E e) {
// 1.判断实际存放的容量是否大于elementData
ensureCapacityInternal(size + 1);
// 2.使用下标进行赋值
elementData[size++] = e;
return true;
}
@Override
public void add(int index, E e) {
// 1.判断实际存放的容量是否大于elementData
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 2.使用下标进行赋值
elementData[index] = e;
size++;
}
/**
* 判断实际存放的容量是否大于elementData
*
* @param minCapacity 最小为size+1
* @return void
* @throws
* @author zhouxinlei
* @date 2019-12-24 14:43:09
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
private void grow(int minCapacity) {
//原数组容量大小
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//最小扩容容量
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
} else if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
E elementData(int index) {
return (E) elementData[index];
}
@Override
public E get(int index) {
//判断数组是否越界
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
}
elementData[--size] = null;
}
@Override
public E remove(int index) {
E e = get(index);
int numMoved = elementData.length - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return e;
}
@Override
public boolean remove(Object object) {
if (object == null) {
for (int index = 0; index < elementData.length; index++) {
if (elementData[index] == null) {
fastRemove(index);
return true;
}
}
} else {
for (int index = 0; index < elementData.length; index++) {
if (object.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
}
return false;
}
@Override
public int size() {
return this.size;
}
}
3 LinkList实现
LinkedList 和 ArrayList 一样,都实现了 List 接口,但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的(通过名字也能区分开来),所以它的插入和删除操作比ArrayList 更加高效。但也是由于其为基于链表的,所以随机访问的效率要比ArrayList差。
3.1 LinkedList数据结构原理
LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:
既然是双向链表,那么必定存在一种数据结构——我们可以称之为节点,节点实例保存业务数据,前一个节点的位置信息和后一个节点位置信息,如下图所示:
3.2 数组和链表结构对比
- 数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据,很少插入和删除元素,就应该用数组。
- 链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起,每个结点包括两个部分:一个是存储 数据元素 的 数据域,另一个是存储下一个结点地址的 指针。如果要访问链表中一个元素,需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了,只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。
3.3 内存存储区别
- 数组从栈中分配空间, 对于程序员方便快速,但自由度小。
- 链表从堆中分配空间, 自由度大但申请管理比较麻烦。
3.4 逻辑结构区别
- 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。
- 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项)
3.5 总结
- 存取方式上,数组可以顺序存取或者随机存取,而链表只能顺序存取;
- 存储位置上,数组逻辑上相邻的元素在物理存储位置上也相邻,而链表不一定;
- 存储空间上,链表由于带有指针域,存储密度不如数组大;
- 按序号查找时,数组可以随机访问,时间复杂度为O(1),而链表不支持随机访问,平均需要O(n);
- 按值查找时,若数组无序,数组和链表时间复杂度均为O(1),但是当数组有序时,可以采用折半查找将时间复杂度降为O(logn);
- 插入和删除时,数组平均需要移动n/2个元素,而链表只需修改指针即可;
- 空间分配方面: 数组在静态存储分配情形下,存储元素数量受限制,动态存储分配情形下,虽然存储空间可以扩充,但需要移动大量元素,导致操作效率降低,而且如果内存中没有更大块连续存储空间将导致分配失败; 链表存储的节点空间只在需要的时候申请分配,只要内存中有空间就可以分配,操作比较灵活高效;
评论区