数据结构之ArrayList
首先：讲述ArrayList之前先来说下List,List是java重要的数据结构之一，我们经常接触到的有ArrayList、Vector和LinkedList三种，他们都继承来自java.util.Collection接口
List 是一个接口，它是继承于Collection的接口。它代表着<有序>的队列
下面是Java中的集合类的关系图。从中可以大致了解集合类之间的关系
本篇主要讲述 Arraylist
Arraylist初始化方法，最简短的
List<String> strings = new ArrayList<String>(asList("foo", "bar", "baz"))Java
COPY
比较常用的
List<String> demo= new ArrayList<>();
demo.add("瞎子");
demo.add("盲僧");
demo.add("李青");
demo.add("扫地僧");Java
COPY
ArrayList是Java一个很常用的集合类，它相当于一个动态数组，内部的数组大小可以根据元素实际情况自动分配，也可以自己分配大小。
在使用ArrayList的时候，应注意ArrayList并不是线程安全的，如果需要多线程并发操作应当使用CopyOnWriteArrayList(读远大于写的情况)，或者使用Collections工具类的synchronizedList方法将其包装。
ArrayList 中常用的方法
add(E e): 在数组末尾添加元素
size(): 数组中实际元素个数，并不是数组容量
add(int index, E e): 在数组指定位置添加元素
clear(): 将数组中元素清空
contains(E e): 判断数组中是否含有某个元素
get(int index): 返回数组指定位置的元素
indexOf(E e): 返回数组指定元素第一次出现的位置
set(int index, E e): 替换数组指定位置的值
remove(int index): 移除数组指定位置的元素
remove(E e): 移除数组中第一次出现的指定元素
addAll(Collection<? extends E> c): 在数组末尾添加另一个数组
addAll(int index, collection<? extends E> c): 在数组指定位置添加另一个数组
removeAll(Collection<?>c): 将数组中属于数组 c 中的元素全部删除Java
COPY
上述方法举例说明：
import java.util.ArrayList;
import java.util.Arrays;
public class ArrayListTest {
class Human{
}
class Male extends Human{
}
public static void main(String[] args) {
ArrayList<Integer> list1=new ArrayList<Integer>();
list1.add(1); // Appends the specified element to the end of this list
list1.add(2);
list1.add(3);
System.out.println(list1.size());
System.out.println(list1);
list1.add(2,4); // Inserts the specified element at the specified position in this list
System.out.println(list1);
list1.clear(); // Removes all of the elements from this list
System.out.println(list1);
list1.add(5);
ArrayList<Integer> list2=new ArrayList<Integer>();
list2.add(1);
list2.add(2);
list2.add(3);
list2.addAll(list1); // Appends all of the elements in the specified collection to the end of this list
System.out.println(list2);
System.out.println(list2.contains(5)); // Judge if this list contains the specified element
System.out.println(list2.get(2)); // Returns the element at the specified position in this list
System.out.println(list2.indexOf(5)); // Returns the index of the first occurrence of the specified element, or -1 if this list doesn't contain
list2.set(2, 10); // Replaces the element at the specified position in this list with the specified element
System.out.println(list2);
list2.remove(2); // Removes the element at the specified position in this list
System.out.println(list2);
list2.remove(Integer.valueOf(1)); // Removes the first occurrence of the specified element from this list, if it is present
System.out.println(list2);
list2.removeAll(Arrays.asList(5)); // Removes from this list all of its elements that are contained in the specified collection
}
}Java
COPY
一、基本实现
❤️❤️❤️1、ArrayList和Vector使用了数组实现，可以认为它们封装了对内部数组的操作；它们两个底层的实现基本可以认为是一致的，主要的一点区别在于对多线程的支持上面。ArrayList没有对内部的方法做线程的同步，它不是线程安全的，而Vector内部做了线程同步，是线程安全的。
❤️❤️❤️2、LinkedList使用了双向链表数据结构，与基于数组实现的ArrayList和Vector相比，这是一种不同的实现方式，这也决定了他们不同的应用场景。LinkedList链表由一系列列表项构成，一个表项包含三个部分：元素内容、前驱表项和后驱表项，如下图所示
在JDK的实现中，增加了两个节点指针first、last分别指向首尾节点
二、不同之处
我们拿经常使用ArrayList与LinkedList，以增加和删除元素，比较下不同之处
1、增加元素到列表尾端：
❤️在ArrayList中增加元素到列表尾端
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保内部数组有足够的空间
elementData[size++] = e; //将元素加入到数组的末尾，完成添加
return true;
}Java
COPY
在这个过程当时，add的性能主要是由ensureCapacityInternal方法的实现，我们继续往下跟踪源码
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
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);
}Java
COPY
calculateCapacity方法会根据你对ArrayList初始化的不同，对elmentData这个对象数组进行非空判断。如果它是一个空数组，则返回ArrayList默认容量和新容量比较的最大值，如果不为空则直接返回新容量。接下来在ensureExplicitCapacity方法中判断如果新容量大于elmentData对象数组的长度则调用grow方法对数组进行扩容。
在这里我们可以看到如果ArrayList容量满足需求时，add()其实就是直接对数组进行赋值，性能很高。而当ArraList容量无法满足要求扩容时，需要对之前的数组进行复制操作。因此合理的数组大小有助于减少数组的扩容次数，如果使用时能够预估ArrayList数组大小，并进行初始化，指定容量大小对性能会有所提升。
❤️在LinkedList中增加元素到列表尾端
//尾端插入，即将节点值为e的节点设置为链表的尾节点
void linkLast(E e) {
final Node<E> l = last;
//构建一个前驱prev值为l,节点值为e,后驱next值为null的新节点newNode
final Node<E> newNode = new Node<>(l, e, null);
//将newNode作为尾节点
last = newNode;
//如果原尾节点为null，即原链表为null，则链表首节点也设置为newNode
if (l == null)
first = newNode;
else //否则，原尾节点的next设置为newNode
l.next = newNode;
size++;
modCount++;
}Java
COPY
LinkedList由于使用了链表结构，因此不需要维护容量的大小，这是相比ArrayList的优势。但每次元素的增加都需要新建一个node对象，并进行更多的赋值操作。在大数据量频繁的调用过程中，对性能会有所影响。
2、增加元素到任意位置：
void add(int index, E element)Java
COPY
由于实现上的不同，ArrayList和LinkedList在这个方法上存在存在一定的性能差异。由于ArrayList是基于数组实现的，而数组是一块连续的内存空间，如果在数组的任意位置插入元素，必然导致在该位置后的所有元素需要重新排列，因此效率会比较低。
❤️ArrayList代码实现如下：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//数组复制
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}Java
COPY
可以看到，ArrayList每次插入操作，都会进行一次数组复制。并且插入的元素在List中位置越靠前，数组重组的开销也越大。
❤️再看LinkedList代码实现
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { //元素位于前半段
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //元素位于后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//指定节点的前驱prev
final Node<E> pred = succ.prev;
//当前节点的前驱为指点节点的前驱，后继为指定的节点
final Node<E> newNode = new Node<>(pred, e, succ);
//更新指定节点的前驱为当前节点
succ.prev = newNode;
//更新前驱节点的后继
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}Java
COPY
LinkedList中定位一个节点需要遍历链表，如果新增的位置处于List的前半段，则从前往后找；若其位置处于后半段，则从后往前找。因此指定操作元素的位置越靠前或这靠后，效率都是非常高效的。但如果位置越靠中间，需要遍历半个List，效率较低。因此LinkedList中定位一个节点需要遍历链表，所以下标有关的插入、删除时间复杂度都变为O(n) ；
3、删除任意位置元素
public E remove(int index) Java
COPY
对ArrayList来说，remove()方法和add()方法是相同的，在删除指定位置元素后，都要对数组进行重组。代码如下
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//移动数组
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}Java
COPY
可见，在进行一次有效删除后，都要进行数组的重组。并且跟add()指定位置的元素一样，删除元素的位置越靠前，重组时的开销就越大，删除的元素位置越靠后，开销越小
❤️再看LinkedList中代码的实现如下
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { //位置位于前半段
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //位置位于后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next; //当前节点的后继
final Node<E> prev = x.prev; //当前节点的前驱
if (prev == null) {
first = next;
} else {
prev.next = next; //更新前驱节点的后继为当前节点的后继
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev; //更新后继节点的前驱为当前节点的前驱
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
} Java
COPY
可见跟之前的插入任意位置一样，LinkedList中定位一个节点需要遍历链表，效率跟删除的元素的具体位置有关，所以删除任意位置元素时间复杂度也为O(n) ；
4、随机访问
public E get(int index)Java
COPY
首先看ArrayList的实现代码如下
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}Java
COPY
可见ArrayList随机访问是直接读取数组第几个下标，效率很高。 LinkedList实现代码如下
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}Java
COPY
相反LinkedList随机访问，每次都需要遍历半个List确定元素位置，效率较低。
优雅的去除list外层两端的 [ ],直接显示列表内容
[1,2,3,4,5,6]
StringUtils.strip(list.toString(), "[]")
1,2,3,4,5,6本文系转载，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文系转载，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
