arraylist的底层,arraylist和linkedlist的底层
arraylist底层原理jdk11和1.8区别
arraylist底层原理jdk11和1.8区别是
jdk11表述有误,应为jdk1.7
【1】JDK1.7中的ArrayList底层
package zhai.list;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
public class ArrayListDemo1 {
public static void main(String[] args) {
// 多态实现 使用前两种方式进行创建集合的话
// 扩展性很高 (建议使用前两种方式进行创建,因为由于Collection接口中没有get方法)
// 使用集合中最大的父接口进行指向 ArrayList 实现类 Collection ArrayList(爷--孙级)
Collection c = new ArrayList();
// 使用父接口进行创建 List--ArrayList(父子级)
List l = new ArrayList(); // 所以 使用父子级进行创建是最佳选择
// 直接使用 ArrayList 类进行创建实体对象 (不建议直接使用该类进行创建 扩展性低)
ArrayList list = new ArrayList();
}
}
注意:1.7中默认创建一个ArrayList集合的时候,默认长度为10,也就是size=10;
package zhai.list;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
public class ArrayListDemo1 {
public static void main(String[] args) {
// 多态实现 使用前两种方式进行创建集合的话
// 扩展性很高 (建议使用前两种方式进行创建,因为由于Collection接口中没有get方法)
// 使用集合中最大的父接口进行指向 ArrayList 实现类 Collection ArrayList(爷--孙级)
Collection c = new ArrayList();
// 使用父接口进行创建 List--ArrayList(父子级)
List l = new ArrayList(); // 所以 使用父子级进行创建是最佳选择
// 直接使用 ArrayList 类进行创建实体对象 (不建议直接使用该类进行创建 扩展性低)
ArrayList list = new ArrayList();
list.add("zhangsan");
list.add("lisi");
System.out.println(list);
}
}
输出:
[zhangsan, lisi] // 默认使用ArrayList中的toString方法进行输出
注意:调用add方法向底层数组中添加元素,最开始size为0,添加元素以后size+1操作,添加成功返回true.
当数组中的10个位置都满了的时候就开始进行数组的扩容,使用add方法中的ensureCapacityInternal约束中的grow()方法进行扩容,将老数组中的内容赋值给新数组返回新数组,长度为原数组的1.5倍(也就是15),15要是满了就以此类推可以有无限长度。
1.7中的ArrayList中最主要的就是new一个ArrayList时,长度默认初始化为10.
【2】DK1.8中的ArrayList底层
最主要的是:在JDK1.8中newArrayList时,会给出一个空的数组,当调用add方法时,这时候才会把数组的长度设置为10,要是满了,会自动扩容。
JDK1.7:只要newArrayList时,就会给数组默认值为10,这样其实没必要,浪费资源,影响性能。
JDK1.8:newArrayList时候会给出一个空的数组,但是当调用add方法时,这时才会给出长度为10的数组。
ArrayList 和LinkList的区别
一.ArrayList 底层维护的是一个Object数组,默认的元素个数为10,ArrayList的特点是增删慢查询快
1.增加慢的原因:是因为在添加数据的时候,有可能会导致ArrayList底层维护的数组的元素个数不够用,这时候就会调用数组的grow方法进行扩容,而扩容的方法是创建一个新的数组,然后把老数组中的信息复制到新的数组当中,这个拷贝的过程很浪费时间和内存
2.删除慢的原因:因为删除某一个元素,会导致该元素后面的元素进行整体前移,也是一个拷贝的过程,这个拷贝过程非常的浪费时间
3.查询快的原因:ArrayList底层维护的是一个数组,可以通过数组的下标直接查询到数组中的内容,这种方式非常的快。
二.LinkList底层维护的是一个链表,所以LinkList的特点是增删快,查询慢
1.增删快的原因:因为LinkList底层维护的是一个链表,在增删的时候可以直接添加到要添加的位置或者直接删除要删除的部分,对其他部分没有影响,速度非常的快。
2.查询慢的原因:因为LinkList底层维护的是一个链表,查询的时候必须一个一个的进行查询,知道找到匹配的数据为止,这个过程非常的浪费时间。
Arraylist底层如何实现的
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}//arraylist的java底层实现
arraylist的add方法底层实际就是一个数组如果这个数组满了就将创建新数组比旧数组大的然后复制旧数组到新数组去
ArrayList和LinkedList底层实现的区别
ArrayList和LinkedList都实现了List接口,ArrayList的实现用的是数组,LinkedList是基于链表,ArrayList适合查找,LinkedList适合增删。
ArrayList与LinkList两者的区别:
ArrayList是基于索引的数据接口,它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。
相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者是更新索引。
LinkedList比ArrayList更占内存,因为LinkedList为每一个节点存储了两个引用,一个指向前一个元素,一个指向下一个元素。
但是要删除数据却是开销很大的,因为这需要重排数组中的所有数据。
2) 相对于 ArrayList , LinkedList 插入是更快的。因为 LinkedList 不像 ArrayList 一样,不需要改变数组的大小,也不需要在数组装满的时候要将所有的数据重新装入一个新的数组,这是 ArrayList 最坏的一种情况,时间复杂度是 O(n) ,而 LinkedList 中插入或删除的时间复杂度仅为 O(1) 。 ArrayList 在插入数据时还需要更新索引(除了插入数组的尾部)。
3) 类似于插入数据,删除数据时, LinkedList 也优于 ArrayList 。
4) LinkedList 需要更多的内存,因为 ArrayList 的每个索引的位置是实际的数据,而 LinkedList 中的每个节点中存储的是实际的数据和前后节点的位置 ( 一个 LinkedList 实例存储了两个值: NodeE first 和 NodeE last 分别表示链表的其实节点和尾节点,每个 Node 实例存储了三个值: E item,Node next,Node pre) 。
什么场景下更适宜使用 LinkedList,而不用ArrayList
1) 你的应用不会随机访问数据 。因为如果你需要LinkedList中的第n个元素的时候,你需要从第一个元素顺序数到第n个数据,然后读取数据。
2) 你的应用更多的插入和删除元素,更少的读取数据 。因为插入和删除元素不涉及重排数据,所以它要比ArrayList要快。