此篇文章会讲解ArrayList和LinkedList的底层实现原理，for和foreach那个循环效率更高
List接口：public interface List<E> extends Collection <E>{}，从这段代码可以看出来，List只是一个接口，并且继承了Collection接口，具体我们常用的实现类也就是ArrayLsit和LinkedList
ArrayList
优点：读取元素效率高，是由数组实现的，值可以为NULL,允许插入重复元素，元素是有序排列的，异步
缺点：由于是用数组实现的，所以插入元素和移动元素的效率不高。
LinkedList
优点：LinkedList由双链表实现，增删由于不需要移动底层数组数据，其底层使用链表实现的，只需要修改链表节点指针，对元素的插入和删除的效率较高。
缺点：遍历的效率比较低，HashMap和双链表也有关系。
ArrayList的成员变量：
//数组默认的初始化容量
private static final int DEFAULT_CAPACITY = 10;
//用于创建一个新的空的实例
private static final Object [] EMPTY_ELEMENTDATA = {};
//用于保存List数据数组
private transient Object[] elementData;
//数组大小
private int size;
LinkedList成员变量
//用于记录集合的数量
transient int size = 0 ;
//集合的一项
transient Node<E> first;
//集合的最后一项
transient Node<E> last;
ArrayList和LinkedList添加元素的内部实现
List接口中有很多接口方法，比如说size()，isEmpty(),clear().....这里就拿add()来做例子
ArrayList添加元素
public boolean add(E e){
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
-
在执行add方法的时候，会先执行ensureCapacity()方法， 这个方法的主要作用就是确保数组的容量是否可以添加元素 ，如果没有声明容量的话，默认数组的长度为10，所以只要容量满了之后，便会将数组的容量扩大1.5倍。
-
ensureCapacity()方法详解，当（元素数量+1）大于 数组长度时，会将容量扩大1.5倍，先创建一个新的数组来存放数据，再扩大数组的容量，最后再将新的数组复制到elementData()数组中。
public void ensureCapacity(int minCapecity){
modCount++; //修改计数器
int oldCapecity = elementData.length;
//当需要的长度超过了原数组的长度，进行扩容处理
if(minCapecity > oldCapecity){
Object oldData[] = elementData;
// 新的容量 = 旧容量 * 1.5 +1;
int newCapacity = (oldCapacity * 3) / 2 + 1;
if(newCapacity < minCapacity)
//
newCapacity = minCapecity;
}
//
elementData = Arrays.copyOf(elementData,newCapacity);
}
LinkedList添加元素
public boolean add(E e){
//实际上就是调用linkLast(E e)方法，也就是在最后面追加一个元素
linkLast(e);
return true;
}
LinkedList的add()很简单，就是调用linkLast(E e);那么来看看linkLast(e);是怎么实现的
public void linkLast(E e){
//取到追加前的最后一个元素
final Node<E> l = last;
//创建一个新的节点，并且将之前的一个元素，还有新的元素传入
//由于是最后一个元素，所以其后面的元素是空的，因此后一个元素为Null
final Node<E> newNode = new Node<>(l,e,null);
last = newNode; //更新最后一个元素的引用
if(l == null)
first = newNode;
else
l.next = newNode;
size ++;
modCount++;
}
使用for循环遍历的效率高还是foreach（增强式循环）
- for的语法
for(int i = 0; i < intergers.length; i++){
System.out.println(intergers[i]);
}
- foreach的语法
for(Integer in : integers){
System.out.println(in);
}
1，使用for适合循环ArrayLIst以及数组，当大批量的循环LinkedList时程序将会卡死，for适合循环数组结构，通过下标去遍历。
2，使用foreach适合循环LinkedList，使用双链表结构实现的应当使用foreach循环。
所以ArrayList推荐使用for循环遍历，而LinkedList推荐使用foreach遍历。
网友评论