前言:
此刻大家对“链表的实现之增删功能”大体比较关怀,小伙伴们都想要剖析一些“链表的实现之增删功能”的相关内容。那么小编同时在网络上网罗了一些对于“链表的实现之增删功能””的相关文章,希望大家能喜欢,朋友们快快来了解一下吧!ArrayList是我们使用频率非常高的一个集合,也是集合中相对比较简单的集合。是List接口的主要实现类。一般面试的时候经常会问到ArrayList和LinkedList的区别。
ArrayList: 底层是数组实现的,查找快,增删慢。
LinkedList: 底层是链表实现的,增删快,查找慢。
一.类结构
ArrayList是集合的一种,集合的最顶端抽象接口为Collection, Collection下面又有两个子接口,一个是List,一个是Set, List和Set的区别也经常别被问到。
List: 数据是有序的,可以根据序号获取元素,List中的数据是可以重复的
Set: 数据是无序的,并且数据是不可重复的(是否重复是根据hashCode和equals方法结果决定)
List下的常用子类为: ArrayList, LinkedList, Vector.
Set下的常用子类: HashSet.
上面说的结构只是对List结构的一个简单描述。一个相对完成的类结构图如下:
这里可以更加清晰的看出ArrayList的结构,其中最主要的就是实现了List接口。那么我们简单的列一下List接口中 都有哪些方法。
int size(); boolean isEmpty(); boolean contains(Object o); Iterator<E> iterator(); Object[] toArray(); <T> T[] toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean addAll(int index, Collection<? extends E> c); boolean removeAll(Collection<?> c); void clear(); boolean equals(Object o); int hashCode(); E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index); int indexOf(Object o); int lastIndexOf(Object o); ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); List<E> subList(int fromIndex, int toIndex);
这你我把一些默认方法去掉了,因为看起来有点乱,其余的就是ArrayList中需要实现的方法了。这里边的大部分方法,我相信大家应该都使用过。而由于List是有序的,有序的意思就是我们可以通过编号来操作集合中的元素,所以上面有很多的方法都是可以传入 index参数的,就是直接根据编号来操作集合。
二. 构造方法
ArrayList中的构造方法总共有三个。其中两个应该是我们经常使用的。
public ArrayList(int initialCapacity); public ArrayList(); public ArrayList(Collection<? extends E> c);复制代码
这相当于我们可以通过三种方式来构建一个ArrayList集合
public class Test{ public static void main(String[] args){ // 无参构造 List<String> list1 = new ArrayList<>(); // 传入初始化容量 List<String> list2 = new ArrayList<>(3); // 传入一个集合 List<String> list3 = new ArrayList<>(list1); }}
这里边第一种方式应该是我们最长使用的,当然也是最不负责任的。第二种方式是编码规范的要求我们这么写的,传入一个初始化的容量。这么做的目的主要是防止向集合中添加数据时,由于集合扩容导致的性能下降问题。所以建议我们在创建集合的时候,最好就根据我们的需求,合理分配出集合的容量大小。第三种是直接传入一个Collection ,要注意,是一个Collection ,也就是List也行,Set也行,这种方法会把Collection直接转为数组,存储到创建的集合中。
三. ArrayList原理
介绍完了这几个构造方法,我们先来讲讲ArrayList的原理。
Q1:ArrayList为什么可以存储元素?
其实他的本质就是一个Object[] , 我们每次向List中添加一个元素,他都会把元素存储到他的一个Object[] 中。那么问题是,我创建一个多大的数组合适呢? 这就涉及到了一个概念叫做 容量 (Capacity) ,所以刚刚的第二种构造方法,传入一个初始化的数组容量,就是代表我的Object[] 的初始化大小是多少。比如我传入了一个10, 那就代表创建了一个10个长度的Object[].
Q2: 如果存储的数据超出了Object[]的长度范围改怎么办?
假设我们通过List list = new ArrayList(10); 指定了集合的初始化长度,那我们向里边添加的元素个数可以超过10个么。答案是肯定的,也就是我们添加超过10个元素的时候,集合也不会报错,原因是什么的,就是ArrayList的自动扩容原理。当我们向集合中添加元素的时候,集合首先会判断当前的数组容量能否容纳得下所需添加的元素,如果容纳不下,就会触发自动扩容机制。而自动扩容机制的核心原理就是创建一个更大的Object[] ,然后将原来的数组中的元素拷贝到这个更大的数组中来,而往往这个过程是比较影响性能的,尤其是集合中的数据量很大的时候,所以我们前面提到了,尽量直接指定数据的容量(在我们可以判断所需大小的时候),目的就是为了减少他的自动扩容,提升效率。
Q3: capacity和size的区别?
这个概念很重要,大家一定要搞清楚这两个概念的区别,才能够更好地理解集合。
先说capcity, 我们上面提到了,他指的就是我用来存储数据的数组的大小。而size只的是集合中存入的元素个数。
什么意思呢,比如我capacity是10,就代表我的集合中数组的长度是10个,然后我向集合中add一个元素,那么size就是1。 size代表的是集合中存储的元素的真正个数。 当集合中的size即将超过capacity的时候,就会出发集合的扩容操作,capacity会继续增大。
Q4: ArrayList的扩容机制*
这个也是面试中会经常别问到的话题,集合的默认容量是多少,什么时候触发扩容,扩成了多大等等,接下来我们就来详细的分析一下。
1. 首先介绍一下ArrayList类中的五个核心成员变量。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ private static final long serialVersionUID = 8683452581122892189L; // 默认容量 private static final int DEFAULT_CAPACITY = 10; // 空数组,当capacity = 0是使用的 private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组,无参构造方法使用 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 核心数组,用于存储数据 transient Object[] elementData; // non-private to simplify nested class access // 集合中实际元素个数 private int size;}
这几个成员变量都是非常重要的。首先我们先来介绍一下这里有两个空的Object数组。一个是EMPTY_ELEMENTDATA,还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
2. EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA区别
这两个都是空数组,为什么要定义两个呢,有什么区别的?其实在注解中已经给出了解释。
这里在解释一下。其实主要区别就是这样的两个集合。
List list1 = new ArrayList(0); List list2 = new ArrayList();复制代码
这两种集合,第一种情况,集合中的数组使用的就是EMPTY_ELEMENTDATA, 第二种情况使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。 我们也可以通过代码清晰的看出来。
主要就是对应有参构造方法中的0,和无参构造方法。
那么为什么非要用两个集合呢。主要原因在于,使用无参构造的集合(上述示例中的list2)是要扩容为默认长度(10)的数组,而指定长度的数组是不需要默认长度的。所以要用两个集合。详见计算容量的方法:
这里要注意一下,我是用的JDK8的代码和JDK7略有区别。就是数组在什么时候开辟空间。从jdk8开始,集合不是你new完了就把空间创建出来的,从代码也可以看出来,我们new完的集合(0参和无参),实际上就给了一个空数组,只有当我们向集合中添加元素的时候,才会根据长度初始化数组的长度。这样做的目的实际就是一个懒加载的思想,避免内存的浪费。
3. 扩容到底扩多大
那么接下来我们就来研究下,扩容到底扩成多大。先总结下我们创建数组的构造方法:
// 初始化了一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATAList list1 = new ArrayList(); // 初始化了一个空数组: EMPTY_ELEMENTDATAList list2 = new ArrayList(0); // 初始化了一个10个长度的数组List list3 = new ArrayList(10);复制代码
而当我们向list1中添加元素的时候,就会将其初始化成默认的长度,也就是10.
// 默认容量private static final int DEFAULT_CAPACITY = 10;复制代码
那么什么时候扩容呢: 看源码:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true;}复制代码
添加元素的时候,会使用size+1的值去计算是否需要扩容:
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
此时的minCapacity 的值就是 size + 1; 调用calculateCapacity 得出所需容量
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;}
这个时候就比较重要了, 当我们的集合是通过无参构造初始化的时候,他的容量是当前size+1 和默认长度的最大值。也就是当我们向集合中添加元素的时候,如果元素个数小于10,那么这个结果就是10, 如果元素个数大于10了,就取当前的最大值。
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);}
如果通过上面得到的值已经大于数组的长度了,就代表数组已经装不下了,这时候就会调用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);}
怎么扩的呢,新的容量为 :oldCapacity + (oldCapacity >> 1); 其实就是原长度的1.5倍,如果你原来是默认的10个长度,扩容后会变为15个。但是也不是最终结果。如果扩完的长度还不够,那么就要多长给多长了。如果扩完的长度大于 MAX_ARRAY_SIZE(这个值是int的最大值-8),就将数组扩容为int的最大值,如果minCapacity为负就代表内存溢出了。这里可能有人想不通,就是扩容后的长度怎么可能不够呢,要注意我们的集合操作不一定都是一个一个添加的,可以通过addAll方法添加一堆元素,那么此时就可能导致你扩容后还是装不下,那就直接初始化为所需长度。
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}
最后再把原来的数组中数据拷贝到新的数组里即可。扩容操作完毕。有点复杂,没懂的多读几遍。
这里基本上就已经是ArrayList中最核心的方法了。剩下的就是一下常用的api都比较好理解了。
四. 常见Api解读
掌握了核心原理,我们就再来读读其他的方法。就比较好理解了。
1. size() 方法,获取集合中元素个数,这里一定注意和capacity的区别。
// 就是一个get方法 public int size() { return size; }
2. get方法和set方法
public E get(int index) { rangeCheck(index); return elementData(index);} public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;}
这里注意一下: 凡是跟index相关的方法,都会先校验一下index是否合法,否则会出现一个我们非常眼熟的异常:
private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));} private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
3. addAll方法: 这个方法也涉及到扩容问题。跟上面的差不多:
public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0;}
这里注意下,判断是否扩容的长度就是size + numNew; 单个的时候用的是 size + 1去判断是否扩容。
4. modCount解释:
我们在代码中会随处发现一个变量modCount,比如扩容的时候,remove的时候,set,clear等方法被调用的时候,都有一个modCount++;
这个变量是干什么用的呢,其实就是用来记录集合被操作的次数。记录这个东西有啥用的,主要就是在做序列化的时候,也就是往出写的时候。在ArrayList中有一个writeObject方法:
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); }}
写的时候会判断前后的modCount是否一致,如果不一致代表对象被操作过,就会报ConcurrentModificationException。
5.indexOf方法: 返回对象在数组中的位置,这里是使用equals方法比较的:
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1;}
这个应该比较好理解,就是遍历数组,查找对象,返回索引值。
6. clear方法:
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
将数组中所有元素置为null, size改为0
剩下的方法就不一一过了。 全篇代码中没有出现 synchronized关键字,也间接证明该类线程不安全
标签: #链表的实现之增删功能