Java集合类解析

Java集合工具包位于java.util包下面，包含了很多常用的数据结构，如: 数组、栈、队列、集合、哈希表等。集合框架大致可以分为五个部分: List列表，Set集合，Map映射，迭代器(Iterator、Enumeration)、工具类(Arrays、Collections)等。

下面从一些常用的集合类开始，步步为营的去总结一下集合框架，加深理解。

一、ArrayList

1、简介

ArrayList基于数组实现，相当于一个动态数组。能动态扩容，继承关系如下图:

基本特性:

• 实现了List接口，提供相关的增删改查功能
• 实现了RandmoAccess接口，提供随机访问功能
• 实现了Cloneable,能被克隆
• 实现了Serializable接口，支持序列化功能
• 所有操作非线程安全，在多线程中可选择Vector或者CopyOnWriteArrayList

2、构造器

ArrayList存在属性transient Object[] elementData;，用来存保存ArrayList实际元素

• ArrayList()： 默认构造器,初始elementData数组为空
• public ArrayList(int initialCapacity): 初始化elementData长度，initialCapacity如果为0，则elementData等于EMPTY_ELEMENTDATA, 如果小于0，则抛出参数异常
• public ArrayList(Collection<? extends E> c): 通过集合初始化

3、源码分析

• ArrayList实际上是通过一个数组去保存数据的。当我们用默认构造器构造ArrayList，则默认容量大小是10
• 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量。
• 克隆函数即时将全部元素克隆到一个数组中

4、遍历

ArrayList支持3种不同的遍历方式。

1、通过Iterator遍历

Integer val = null;
Iterator<Integer> iterator = list.iterator();

while (iterator.hasNext()) {
    val = iterator.next();
}

此种遍历方式在遍历的同时删除元素会抛出异常ConcurrentModificationException

2、随机访问遍历

由于ArrayList实现了RandomAccess接口，支持通过索引随机访问。

Integer val = null;
for (int i = 0; i < list.size(); i++) {
    val = list.get(i);
}

这种遍历方式在遍历的同时删除元素不会抛出ConcurrentModificationException异常

3、for循环遍历

for (Integer integer : list) {
}

遍历改变长度会抛出异常ConcurrentModificationException

4、forEach遍历

JDK1.8之后的方法

list.forEach(item -> {
    System.out.println(item);
});

遍历改变长度会抛出异常ConcurrentModificationException

二、LinkedList

继承关系如下图:

介绍:

• LinkedList是一个继承自AbstractSequentialList的双向链表。可以被当成堆栈、队列或双端队列进行操作
• LinkedList实现List接口，能对他进行操作
• LinkedList实现Deque接口，即能将LinkedList当成双端队列使用
• LinkedList实现Cloneable接口，即能被克隆
• 实现java.io.Serializable接口，以为着LinkedList支持序列化，能通过序列化传输
• LinkedList非同步，非线程安全的

1、LinedList数据结构

LinkedList的本质是双向链表, 每一个节点是一个LinkedList的内部类，类定义如下。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

每个Node包含下一个节点next和上一个节点prev

• LinkedList继承自AbstractSequentialList，并且实现了Dequeue接口，包含内部类Node,是双向链表节点所对应的数据结构，他包含的属性有：当前节点所包含的上一个节点和下一个节点
• LinkedList的用链表实现，所以不存在容量不足的问题
• LinkedList实现了Deque，定义了双向队列两端访问元素的方法，提供插入、移除、检查元素的方法，每种方法都存在两种形式: 一种形式会在操作失败时抛出异常，另一种形式返回特殊值(null或false，具体取决于操作).

2、操作方法

LinkedList是可以存储null值的

(1)、添加元素

• public boolean add(E e)： 在链表末尾添加元素
• public void addFirst(E e): 在链表头部添加元素
• public void addLast(E e): 在链表末尾添加元素
• public void push(E e): 相当于入栈操作，调用的是addFirst方法
• public boolean offer(E e): 在链表末尾添加元素,调用add方法实现的
• public boolean offerFirst(E e): 在首部添加元素，调用的是addFirst方法实现的
• public boolean offerLast(E e): 在末尾添加元素，调用的是addLast方法实现的

(2)、获取并删除元素

• public E removeFirst(): 删除首个元素
• public E remove(): 删除首个元素，调用removeFirst方法实现
• public E removeLast(): 删除尾部元素
• public E pop(): 删除首个元素，调用的removeFirst方法

注意: 上面这四个方法在数据为空时候会抛出NoSuchElementException运行时异常

• public E pollFirst(): 删除并返回首个元素，如果数据为空，返回null
• linkedList.pollLast(): 删除并返回最后一个元素，数据为空返回null
• public E poll(): 删除并返回首个元素，如果数据为空，返回null

这三个方法获取元素不会抛出异常，但是数据不存在会返回null

(3)、获取元素

• public E peek(): 获取首个元素，不会删除
• public E peekFirst(): 获取首个元素
• public E peekLast(): 获取最后一个元素，不会删除元素

上面这三个方法获取元素时间复杂度为O(1),速度较快，可以使用

• public E get(int index): 获取特定元素

此方法获取元素会遍历链表，最好不要使用