arraylist扩容,ArrayList 和LinkList的区别

arraylist扩容,ArrayList 和LinkList的区别详细介绍

本文目录一览： ArrayList与LinkedList的扩容

我们都知道数组不能扩容，ArrayList可以扩容，但ArrayList的底层是数组，他是怎么进行扩容的呢？

一、ArrayList扩容实现步骤

1.扩容：?把原来的数组复制到另一个内存空间更大的数组中；

?2.添加元素：?把新元素添加到扩容以后的数组中。

二、源码分析

关键属性：

解析ArrayList的三个构造方法：

分析常用方法：

LinkedList的扩容机制又是怎么样的呢？

1.LinkedList是一个继承于AbstractSequentialList的双向链表。

2.由于他的底层是用双向链表实现的，没有初始化大小，所以没有油扩容机制，就是一直在前面或者是后面新增就好。

二者区别：

二者的顶层接口都是Collection，

ArrayList是基于数组实现的，查询速度较快，LinkedList是双向链表，可以从头插入也可以从末尾插入，所以在增加和删除的时候比较快，是基于链式存储结构的。

LinkedList是离散空间所以不需要主动扩容，而ArrayList是连续空间，内存空间不足时，会主动扩容。

两者都不是线程安全的

参考资料：

【Java基础】ArrayList 扩容原理

ArrayList详解，看这篇就够了

ArrayList详解，自动扩容原理

ArrayList

：说明ArrayList支持泛型。 extends AbstractList

：继承了AbstractList。AbstractList提供List接口的骨干实现，以最大限度地减少“随机访问”数据存储（如ArrayList）实现Llist所需的工作。 implements List

：实现了List。实现了所有可选列表操作。 implements RandomAccess：表明ArrayList支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。 implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。 implements java.io.Serializable：表明该类具有序列化功能。有序列化功能 下面来看一些比较重要的参数：

ArrayList的实际大小（数组包含真正的元素个数）

执行完构造方法时还是一个空数组，等到add方法执行的时候则会初始化容量为10；

自己穿入想要的容量参数，对容量进行判断如果容量小于零，则会抛出异常，否则会创建一个容量为initialCapacity的空ArrayList

构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

先来看其中的add（）方法：

add方法首先会调用ensureCapacityInternal（size+1）方法，

ensureCapacityInternal（size+1）方法是用来进行容量检查，决定扩容的想要的最小容量，举个例子，第一次扩容的时候，size默认为0则minCapacity（即想要的最小容量）为1，执行完Math.max语句minCapacity就变为10，这个时候也就是进行空构造第一次add的情况，当ensureCapacityInternal（size+1）传入的参数小于默认参数的时候，就把默认参数当做想要的最小容量，如果大于默认参数就把你想要的参数当做想要的最小容量

这个方法是用来判断是否扩容，如果你想要的最小容量大于数组长度则会调用grow方法进行扩容

通过grow方法可以看到新容量为当前数组容量的1.5倍，然后进行判断，如果理论扩容后新的容量小于小于你想要的最小容量（但我觉得这种情况不太可能会出现，因为为了节省空间，假如当前容量为10，只会传入11来和扩容后的进行比较因此我自己认为不会出现if为真的情况）真正的实现扩容其实是Arrays.copy方法，就是复制数组实现扩容，

但是如果出现了if为真的情况，从这个方法中可以看到数组的理论最大值为Integer的最大值减去8，但是如果你想要的最小容量已经大于数组的理论最大值，则会进行大容量分配为Integer的最大值至此扩容结束，

下面粗略的谈一下快速失败机制（因为对线程还没有一个好的认识）

fail-fast是怎么产生的。步骤如下：

新建了一个ArrayList，名称为arrayList。 向arrayList中添加内容 新建一个“线程a”，并在“线程a”中通过Iterator反复的读取arrayList的值。 新建一个“线程b”，在“线程b”中删除arrayList中的一个“节点A”。 这时，就会产生有趣的事件了。 在某一时刻，“线程a”创建了arrayList的Iterator。此时“节点A”仍然存在于arrayList中，创建arrayList时，expectedModCount = modCount(假设它们此时的值为N)。 在“线程a”在遍历arrayList过程中的某一时刻，“线程b”执行了，并且“线程b”删除了arrayList中的“节点A”。“线程b”执行remove()进行删除操作时，在remove()中执行了“modCount++”，此时modCount变成了N+1！

“线程a”接着遍历，当它执行到next()函数时，调用checkForComodification()比较“expectedModCount”和“modCount”的大小；而“expectedModCount=N”，“modCount=N+1”,这样，便抛出ConcurrentModificationException异常，产生fail-fast事件。

至此，我们就完全了解了fail-fast是如何产生的！ 即，当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

方法1 在单线程的遍历过程中，如果要进行remove操作，可以调用迭代器的remove方法而不是集合类的remove方法。看看ArrayList中迭代器的remove方法的源码：

可以看到，该remove方法并不会修改modCount的值，并且不会对后面的遍历造成影响，因为该方法remove不能指定元素，只能remove当前遍历过的那个元素，所以调用该方法并不会发生fail-fast现象。该方法有局限性。 例子：

方法2 使用java并发包(java.util.concurrent)中的类来代替ArrayList 和hashMap。 比如使用 CopyOnWriterArrayList代替ArrayList，CopyOnWriterArrayList在是使用上跟ArrayList几乎一样，CopyOnWriter是写时复制的容器(COW)，在读写时是线程安全的。该容器在对add和remove等操作时，并不是在原数组上进行修改，而是将原数组拷贝一份，在新数组上进行修改，待完成后，才将指向旧数组的引用指向新数组，所以对于CopyOnWriterArrayList在迭代过程并不会发生fail-fast现象。但 CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。 对于HashMap，可以使用ConcurrentHashMap，ConcurrentHashMap采用了锁机制，是线程安全的。在迭代方面，ConcurrentHashMap使用了一种不同的迭代方式。在这种迭代方式中，当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException，取而代之的是在改变时new新的数据从而不影响原有的数据 ，iterator完成后再将头指针替换为新的数据 ，这样iterator线程可以使用原来老的数据，而写线程也可以并发的完成改变。即迭代不会发生fail-fast，但不保证获取的是最新的数据。

ArrayList(20)扩容几次

List<> list = new ArrayList<>(20);
问：扩容几次？

ArrayList list=new ArrayList();
这种是默认创建大小为10的数组，每次扩容大小为1.5倍
ArrayList list=new ArrayList(20);
使用的ArrayList的有参构造函数，直接扩容，所以为零次

这种是指定数组大小的创建，创建时直接分配其大小，没有扩充。
一次性为创建了传入的数字的长度的数组
所以，扩充为0次

java Arraylist扩容为什么是1.5倍+1

// ArrayList类的源码：对内部数组扩容 public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1;// 计算新容量 if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }}

ArrayList

Q：ArrayList底层实现是什么？
A：底层实现是数组，ArrayList内部定义了一个数组来存储对象

Q：ArrayList默认的容量是多少？new ArrayList<>()时，指定容量与不指定容量有什么区别？
A：默认容量是10。调用默认构造函数时，只是把一个size为0的空数组赋值给elementData，当第一次添加元素时，数组会扩容到DEFAULT_CAPACITY（10）

指定容量初始化ArrayList时，会创建一个大小为initialCapacity的数组赋值给elementData，在添加第一个元素时，如果initialCapacity小于DEFAULT_CAPACITY，数组将会扩容到DEFAULT_CAPACITY

Q：ArrayList的扩容机制是什么？什么时候会进行扩容？
A：分两种情况

Q：1.7与1.8版本的区别
A：1.7版本在初始化时就创建一个容量为10的数组；1.8版本在初始化时创建一个空数组，当第一次add元素时才扩容到10

Q：ArrayList线程安全吗？
A：不安全，如果需要线程安全，则使用Vector，CopyOrWriteArrayList，Collections.synchronizedList()

Q：ArrayList在增删时的效率如何？
A：看情况，尾插时，如果不扩容，效率高； 非尾插或者尾插需要扩容时，效率会变低，因为这两种情况都会涉及到数组的拷贝

Q：ArrayList与LinkedList区别
A：基本等同于数组与链接的区别，数组是固定大小，需要一片连续的内存空间，查找快，增删慢；链接不需要连续内存空间，在逻辑上是连续的，查找慢，增删快。二都都是线程不安全的。
遍历性能ArrayList比LinkedList好，因为CPU内部的缓存结构会缓存连续的内存片断，可大幅降低读取内存的性能消耗。

Q：ArrayList适合做队列吗？
A：不适合。队列是FIFO，先进先出，使用数组做队列，需要头插尾出或者头出尾插，这都会涉及到数组的复制，很耗性能。

Q：ArrayList初始化时是否需要指定初始容量
A：容量小于10不需要，大于10时指定容量较好。

ArrayList底层数据结构

ArrayList底层使用的数组这个基本的数据结构，我们看下它的初始化及添加数据时的扩容策略。

我们可以看的默认的构造函数，直接将存储数据的数组进行初始化，DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个初始化为空的数组

DEFAULT_CAPACITY为默认容量是10，因为首次调用add此时minCapacity为10而数组长度为0，因此会调用grow进行扩容设置当前数组长度为10，如果当前capacity达到初始容量，则之后扩容会按之前的1.5倍进行扩容。
扩容方式是调用Arrays.copyof（elementdata,newCapacity）方法这个方法底层调用了native方法System.arraycopy

java简答题 简述ArrayList的实现原理 。求帮忙

自动扩容数组
实现原理 。
ArrayList的实现原理总结如下：
1、数据存储是基于数组实现的，默认初始容量为10；
2、添加数据时，首先需要检查元素个数是否超过数组容量，如果超过了则需要对数组进行扩容；插入数据时，需要将插入点k开始到数组末尾的数据全部向后移动一位。
3、数组的扩容是新建一个大容量（原始数组大小+扩充容量）的数组，然后将原始数组数据拷贝到新数组，然后将新数组作为扩容之后的数组。数组扩容的操作代价很高，我们应该尽量减少这种操作。
4、删除数据时，需要将删除点+1位置开始到数组末尾的数据全部向前移动一位。
5、获取数据很快，根据数组下表可以直接获取。

ArrayList用法

ArrayList就是动态数组，用MSDN中的说法，就是Array的复杂版本，它提供了动态的增加和减少元素，实现了ICollection和IList接口，灵活的设置数组的大小等好处。
List 接口的大小可变数组的实现，位于API文档的java.util.ArrayList

。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行，也就是说，添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行（大体上讲）。与用于 LinkedList 实现的常数因子相比，此实现的常数因子较低。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。

简单讲几个常用的用法，其它的用法最好还是查阅api

1。ArrayList实现List接口，

可以这样实例化：List list=new ArrayList();

2。list.add(obj);可以在list的最后插入一个实例，obj可以是任意类型的实例；

3。list.get(index);可以获得list中下标为index的元素，例如list.get(0);就是获得第一个，这样也可以遍历list，list.size()返回list的大小；

4。也可以用迭代器遍历：list.iterator();获得迭代器；

存的时候

ArrayList al = new ArrayList();

User user = new User();

user.setname("张三");

user.setage(21);

user.setsex("男");

User user1 = new User();

user1.setname("李四");

user1.setage(31);

user1.setsex("男");

al.add(user);

al.add(user1);

取出来的时候可以用一个迭代器Iterator拿出来,OK,到此结束

List list = Collections.synchronizedList(new ArrayList(...));

补充个同步的

ArrayList用法：

ArrayList是接口List的实现类，所以推荐以List接口来使用。

1、创建ArrayList的List接口

例：

List books = new ArrayList();

Java支持泛形后，创建的同时可以指定元素的类型。

例：

Class Book {

......

}

List

books = new ArrayList

();

为避免容器自动扩容的次数而影响性能，可以指定创建时的元素大小。

例：

// 创建可容纳100个Book对象的ArrayList，超过100个将自动扩容

List

books = new ArrayList

(100);

2、添加元素

添加在末尾

例：

Book book1 = new Book();

Book book2 = new Book();

Book book3 = new Book();

books.add(book1);

books.add(book2);

books.add(book3);

添加在指定索引处

例：

// 虽然加book1后直接加book3了，但book2是被加在索引1的地方

// 所以效果同上，是book1、book2、book3的顺序

books.add(book1);

books.add(book3);

books.add(1, book2);

3、 获取ArrayList中元素的个数

例：

int count = books.size();

4、读取元素

利用普通的for循环：

例：

for (int i = 0; i < books.size(); i++ {

Book newBook = books.get(i);

// 不带泛形的注意要转型

Book book = (Book) books.get(i);

System.out.println(book.getName());

}

利用for循环的新特性：

例：

for (Book book : books) {

// 用book就能访问了

System.out.println(book.getName());

}

利用枚举：

例：

Iterator

iter = books.iterator();

while (iter.hasNext()) {

Book book = iter.next();

System.out.println(book.getName());

}

5、移除元素

移除指定索引处的元素

例：

books.remove(0); // 移除book1

books.remove(1); // 移除book2

books.remove(2); // 移除book3

移除指定对象的所在元素

例：

Book delBook = books.get(1);

books.remove(delBook); // 移除book2

移除所有元素

例：

books.clear();

6、判断ArrayList是否为空（没有元素）

原方法：

if (books.isEmpty()) {

}

直接判断大小：

if (books.size() == 0) {

}

7、判断ArrayList中是否已经存在了某对象

例：

// 判断是否已经存在book2对象

if (books.contains(book2)) { // 已经存在

}

8、根据对象反查询它的索引位置

从前住后查询，反回第一个符合条件的位置

例：

list.indexOf(book2); // 查询book2对象的索引位置

从后住前查询，反回第一个符合条件的位置

例：

list.lastIndexOf(book2); // 查询book2对象的索引位置

以上这些掌握后，基本就没问题了。

ArrayList 和LinkList的区别

一.ArrayList 底层维护的是一个Object数组，默认的元素个数为10，ArrayList的特点是增删慢查询快

1.增加慢的原因：是因为在添加数据的时候，有可能会导致ArrayList底层维护的数组的元素个数不够用，这时候就会调用数组的grow方法进行扩容,而扩容的方法是创建一个新的数组，然后把老数组中的信息复制到新的数组当中，这个拷贝的过程很浪费时间和内存

2.删除慢的原因：因为删除某一个元素，会导致该元素后面的元素进行整体前移，也是一个拷贝的过程，这个拷贝过程非常的浪费时间

3.查询快的原因：ArrayList底层维护的是一个数组，可以通过数组的下标直接查询到数组中的内容，这种方式非常的快。

二.LinkList底层维护的是一个链表，所以LinkList的特点是增删快，查询慢

1.增删快的原因：因为LinkList底层维护的是一个链表，在增删的时候可以直接添加到要添加的位置或者直接删除要删除的部分，对其他部分没有影响，速度非常的快。

2.查询慢的原因：因为LinkList底层维护的是一个链表，查询的时候必须一个一个的进行查询，知道找到匹配的数据为止，这个过程非常的浪费时间。