Java集合框架--List和Queue

发表于 更新于 本文字数： 23k 阅读时长 ≈ 21 分钟

Java集合框架–List和Queue

在前面的章节我们存储数据一般有两种方式：

  1. 保存在变量中，优点是简单方便，缺点是只能保存一个数据
  2. 保存在数组中，优点是可以批量保存数据，缺点是数组的长度不可变，一旦数据个数发生变化时，就得重新创建数组然后复制数组元素，并且数组只能存储相同数据类型的数据。

基于以上两点，Java为我们提供了集合类，用于存储数量不等的对象，除此以外，Java还可以用于保存具有映射关系的关联数组。

Java集合体系概述

Java集合大致可以分为List、Set、Map和Queue，其中List代表有序、可重复的集合，Set代表无序、不可重复的集合，而Map则代表具有映射关系的集合。
Java集合就像是一个容器，只不过容器里装的都是对象，在JAVA 5之前，Java集合对丢失容器中对象的数据类型，把所有对象都当做Object类型处理，从容器取出元素后，还面临着对象向下转型的问题，Java5以后新增了泛型（关于泛型，会在Java高级中讲解，此处不做深究）。Java集合可以记住容器中对象的数据类型。首先，来查看Java集合体系的全貌。

ArrayList

List集合代表一个元素有序、有索引、可重复的集合。List允许存放相同的元素，并且每个元素都有对应的索引，可以通过索引访问指定位置的集合元素。结合ArrayList的特点以及前面章节的内容很容易联想到学习过的数组， 通过查看ArrayList源码可以看到ArrayList的底层就是用数组保存数据以及对数据操作的。

1
2
3
4
5
6
7
/**
* 存储ArrayList元素的数组缓冲区。
* ArrayList的容量是此数组缓冲区的长度。任何
* 空的 ArrayList 等价于 elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* 当添加第一个元素时，将扩展到默认容量。
*/
transient Object[] elementData; // non-private to simplify nested class access

那么我们就可以先尝试手动实习自己的ArrayList。在实现ArrayList之前，先来查看ArrayList继承关系图以及主要方法：

通过继承关系图可以看出ArrayList的继承关系，下面先对各个接口进行解释：
RandomAccess:随机访问接口，因为ArrayList底层使用数组实现，所以支持在允许范围内随机访问。
Cloneable：克隆接口，说明ArrayList支持克隆
Serializable：序列化接口，说明ArrayList支持序列化（关于序列化的内容，将会在Java高级中讲解)。
List:接口提供数组的添加、删除、修改、迭代遍历等操作。
AbstractList:AbstractList 提供了 List 接口的骨架实现，大幅度的减少了实现迭代遍历相关操作的代码
了解完继承关系以后，接下来熟悉ArrayList的常用API，了解完ArrayList的基本操作以后，可以更方便的理解ArrayList的源码以及结构。

ArrayList常用API

前面的内容可以知道ArrayList在Java中通常当做容器使用，当做容器使用就需要具备基本的增删改查方法。

构造方法

首先，需要了解ArrayList常用的构造方法：

  • public ArrayList(int initialCapacity) ：创建给定容量的ArrayList，initialCapacity的值不能小于0，不能大于Integer能表示的最大值
  • public ArrayList()：创建ArrayList对象，默认创建一个空数组。
  • public ArrayList(Collection<? extends E> c)：传入一个集合，以集合中元素为初始元素创建对象

在上述3个构造方法中，前两个使用频率较高，当知道ArrayList中保存对象的个数时，通常使用第一个构造方法，这样在ArrayList创建对象时已经初始化好数组的长度了，这样也就避免了扩容的内存开销。
同理，当不确定元素个数时，通常使用第二个构造方法。
如果需要把一个集合中的元素放入ArrayList，就可以使用第三个构造方法。
下面，通过示例来学习这3个构造方法：

1
2
3
4
5
6
7
8
9
10
11
public class Demo04 {
	public static void main(String[] args) {
		//创建固定容量的集合
		List list1 = new ArrayList(10);
		//创建不固定容量的集合
		List list2 = new ArrayList();
		//传入一个集合
		List list3 = new ArrayList<>(list2);
	}

}

常用API

方法 描述
add(Object o) 添加数据
add(int index,Object o) 在制定索引处添加元素
size() 获取元素个数
get(int index) 获取索引处的元素
isEmpty() 判断集合是否为空
indexOf(Object o) 判断某个元素第一次出现的位置
E remove(int index) 移除索引处元素，并返回该元素
boolean remove(Object o) 移除元素
clear() 清空元素
set(int index ,E e) 修改索引处的元素
iterator() 获取迭代器
trimToSize() 减少容量至当前元素个数
contains(Object o) 判断是否包含某个元素
lastIndexOf(Object o) 判断某个元素最后一次出现的位置
toArray() 将集合转换为数组
addAll(Collection<? extends E> c) 集合中添加集合
addAll(int index, Collection<? extends E> c) 索引处添加集合
retainAll(Collection c) 求两个集合的交集
removeAll(Collection<?> c) 移除传入集合内的元素
subList(int fromIndex, int toIndex) 获取子集合

下面，通过示例代码来学习ArrayList的常用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package cn.bytecollege;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class AddDemo {
	public static void main(String[] args) {
		//集合当中添加元素
		List list = new ArrayList();
		list.add("张无忌");
		list.add("赵敏");
		list.add("小昭");
		//将list转成数组
		Object[] objects = list.toArray();
		System.out.println(Arrays.toString(objects));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package cn.bytecollege;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Demo {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        //添加元素
        list.add(10);
        list.add(20);
        list.add(30);
        list.add(40);
        list.add(50);
        list.add(30);
        //在索引处，添加元素
        list.add(3,100);
        //获取元素的个数
        int a = list.size();
        System.out.println(a);
        //判断集合是否为空
        System.out.println(list.isEmpty());
        //判断某个元素第一次出现的位置
        System.out.println(list.indexOf(30));
        //移除索引处的元素
        System.out.println(list.remove(1));
        list.set(5,60);
        // 迭代器
        Iterator<Integer> it = list.iterator();
        System.out.println(it.next());
        //清空元素
        list.clear();
        System.out.println(list.size());
        list.trimToSize();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package cn.bytecollege;

import java.util.ArrayList;

public class ArrayListDemo2 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(15);
        list.add(20);
        list.add(25);
        list.add(30);
        list.add(15);
        //判断是否包含某个元素
        System.out.println(list.contains(10));
        //判断某个元素最后一次出现的位置
        System.out.println(list.lastIndexOf(15));
        //将集合转换为数组
        ArrayList arr = new ArrayList();
        arr.add(1);
        arr.add(2);
        arr.add(3);
        //集合中添加集合
//        list.addAll(arr);
        //求两个集合的交集
        list.retainAll(arr);
//        集合处添加集合
        list.addAll(3,arr);
        list.toArray();
        System.out.println(list.toString());
    }
}

手动实现ArrayList

通过上一小节的学习可以发现ArrayList中主要的方法就是增、删、改、查，接下来根据ArrayList的方法，手动实现自己的ArrayList。
第一步：需要定义一个数组保存元素，其次需要定义一个变量保存数组中元素的个数。以及当前数组的长度和默认初始化的长度

第一步：需要定义一个数组保存元素，其次需要定义一个变量保存数组中元素的个数。以及当前数组的长度和默认初始化的长度

1
2
3
4
5
6
7
8
//用于保存元素个数
private int size;
//保存元素
private Object[] objects;
//保存数组的当前长度
private int length;
//保存数组的默认长度
private final int DEFAULT_LEGTH = 10;

第二步：定义构造方法，构造方法的目的主要是为了初始化数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class MyArray {	
	/**
	 * 定义数组，保存数据
	 */
	private Object[] objects = null;
	/**
	 * 默认数组长度
	 */
	private final int DEFAULT_LENGTH = 10;
	/**
	 * 数组长度
	 */
	private int length;
	/**
	 * 数组元素个数
	 */
	private int size= 0;
	/**
	 * 默认构造函数，创建数组
	 */
	private final int LOAD = 2;
	public MyArray() {
		length = DEFAULT_LENGTH;
		objects = new Object[length];
	}
	/**
	 * 构造函数，根据用户传入长度创建数组
	 * @param length
	 */
	public MyArray(int length) {
		this.length = length;
		objects = new Object[length];
	}
}

第三步：定义add()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class MyArray {	
	/**
	 * 向数组中添加元素
	 * @param o
	 */
	public void add(Object o) {
		//判断是否需要扩容
		if(size==length) {
			//元素个数等于了数组长度，需要扩容
			length = length*LOAD;
			objects = Arrays.copyOf(objects,length);
		}
		objects[size]=o;
		size++;
	}	
	public void add(int index,Object o) {
		if(index<0||index>size-1) {
			throw new ArrayIndexOutOfBoundsException("访问越界");
		}else {
			//判断是否需要扩容
			if(size==length) {
				//元素个数等于了数组长度，需要扩容
				length = length*LOAD;
				objects = Arrays.copyOf(objects,length );
			}
			//先将index位置处的元素已近后面元素向右移动
			System.arraycopy(objects, index, objects, index+1, size-index);
			objects[index] = o;
			size++;
		}
	}
}

在上述代码中重载了两个add()方法，第一个方法默认添加到数组元素尾部，从代码中可以看出添加元素时先判断元素个数是否等于数组长度，当元素个数等于数组长度时意味着数组已经满了，此时，需要扩容，我们获取到数组原长度并乘以2，然后创建新的数组长度为原数组长度的2倍，并将原数组中的元素复制到新数组，最后将新数组的引用保存在原数组，扩容完毕后将新添加的元素放置在新数组元素末尾，然后元素个数增加一。如果不需要扩容，则直接将元素添加在数组元素末尾，然后元素个数增加一。
在add(int index,Object o)方法中，因为此时涉及到数组的索引，所以先判断传入的索引是否越界，如果越界则抛出异常，没有越界则继续执行，当添加元素时也需要先判数组是否已经放满，如果已经放满则扩容，扩容以后先将原数组的元素全部复制到新数组，复制完成以后，先将索引处元素到最后一个元素依次向后移动，然后将新元素放入索引位置处，最后将元素个数加一，如果不需要扩容，则直接将索引处元素向后移动，然后将新增的元素放入索引位置处。
第二步：定义删除方法
为了保证数组中所有的元素连续，那么当删除一个元素需要对被删除元素以后的元素全部向前移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 数组移除操作
 * @param index
 */
public void remove(int index) {
	if(index<0||index>size-1) {
		throw new ArrayIndexOutOfBoundsException("访问越界");
	}else {
		objects[index]= null;
		System.arraycopy(objects, index+1, objects,index , size-index);
		size--;
	}
}

由于是要根据数组索引删除元素，因此删除之前要先判断索引是否越界，如果越界则抛出异常。
删除元素时只需将索引处的元素置为null，然后将索引处后面的元素全部往前移动1位，最后将元素个数减一即可。
第三步：修改元素

1
2
3
4
5
6
7
8
9
10
11
/**
  * 更新数组元素
  * @param index
  * @param o
  */
public void update(int index,Object o) {
	if(index<0||index>size-1) {
		throw new ArrayIndexOutOfBoundsException("访问越界");
	}
	objects[index] = o;
}

修改元素时，一般是修改某个索引处的元素，因此也要判断传入索引是否越界。如果索引没有越界，则将索引处的元素修改为新元素即可。
第四步：查看元素

1
2
3
4
5
6
7
8
9
10
/**
  * 查找某个索引处的元素
  * @param index
  */
public Object get(int index) {
	if(index<0||index>size-1) {
		throw new ArrayIndexOutOfBoundsException("访问越界");
	}
	return objects[index];
}

获取索引处元素时，也需要先判断索引是否越界，如果没有越界则直接从数组中获取数组元素即可。

ArrayList添加元素过程

在前面的章节中可以知道ArrayList的底层实现是一个数组，在ArrayList中添加元素的过程本质上就是在ArrayList底层数组添加元素的过程。
下面我们通过分析ArrayList源码来了解这个过程。

1
2
3
4
5
6
7
8
public boolean add(E e) {
    //记录ArrayList的修改次数
    modCount++;
    //调用重载的add()方法
    add(e, elementData, size);
    //从这里看出不管元素是否添加成功都返回了true
    return true;
}

从add()方法中可以看出，add方法内调用了重载的私有add(E e, Object[] elementData, int s)方法，并且返回了true，在这里需要注意的是根据此方法的返回值判断元素是否添加成功并没有任何意义，因为add()方法返回值恒为true。

1
2
3
4
5
6
7
8
9
10
private void add(E e, Object[] elementData, int s) {
    //判断元素个数是否和长度相等
    if (s == elementData.length)
        //扩容
        elementData = grow();
    //将元素放置在扩容后数组的已有元素的末尾
    elementData[s] = e;
    //元素个数增加
    size = s + 1;
}

在这个方法中首先判断元素的个数是否等于数组长度，也就是说判断数组是否已经满了，如果满了则进行扩容。不管是否扩容，都将新增的元素放在已有元素的后面，然后元素的个数加一。
那么ArrayList又是如何扩容的呢？继续查看grow()方法。

1
2
3
private Object[] grow() {
    return grow(size + 1);
}

grow()方法比较简单，只是调用了私有的重载grow(intminCapacity)方法。

1
2
3
4
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
}

从源代码可以看出，在这个grow()方法内部使用了数组复制，并且在数组复制前调用了newCapacity()方法。继续查看newCapacity()方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private int newCapacity(int minCapacity) {
    //获取数组当前长度
    int oldCapacity = elementData.length;
    //计算新长度，可以看出新长度是原长度的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //判断新容量和最小容量大小，如果新容量小于等于最小容量
    if (newCapacity - minCapacity <= 0) {
        //如果当前数组是默认容量长度为0的数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            //返回数组初始长度10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        //如果最小容量小于0则抛出异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    //如果新容量大于最小容量，判断新容量是否比数组长度的最大值小
    //如果新容量小于数组长度最大值则返回新容量
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

newCapacity()方法即ArrayList计算扩容后数组长度的核心方法，在这个方法中主要做了以下工作：

  1. 获取数组原长度并根据元长度计算新长度
  2. 判断新长度是否比原长度小，如果新长度比原长度小，判断数组是否是初始的空数组，如果是则返回默认长度10。
  3. 如果新长度大于原长度，判断新长度是否大于等于数组长度的最大值（Integer.MAX_VALUE-8）,如果不大于则返回新长度。
  4. 如果大于则调用hugeCapacity()方法。

继续查看hugeCapacity()方法。

1
2
3
4
5
6
7
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

hugeCapacity()方法较为简单，判断最小容量是否大于数组的最大长度，如果大于则返回Integer的最大值，否则返回数组最大值。

ArrayList和Vector

和ArrayList具有相同功能的类是Vector，Vector是Java早期提供的一个集合类，Vector和ArrayList的方法以及底层的实现基本相似，唯一不同的是Vector的方法都是线程安全的，打开Vector源码可以发现Vector的方法都是用synchronized修饰的（关于synchronized修饰符，会在多线程中讲解），因此Vector效率低于ArrayList。除此之外ArrayList和Vector的区别还体现在以下几个方面：

  1. ArrayList扩容后的长度是原长度的1.5倍，而Vector扩容后的长度是原长度的2倍
  2. ArrayList调用无参构造方法创建对象时，会创建一个空的Object数组，当添加第一个元素时进行扩容，初始容量为10，当Vector调用无参构造创建对象时，则会直接初始化保存数据的数组，长度为10。

LinkedList

LinkedList同样实现了List，也就是说LinkedList和ArrayList的方法基本一致。除此以外，LinkedList还实现了Deque接口。Deque接口则继承了Queue接口，因为Queue是指队列这种数据结构，换句话说就是LinkedList不但可以当做List使用，也可以当做队列使用（FIFO），并且是双端队列，根据队列的规定，队列只能从一端进入数据，另一端出数据，但是双端队列任意一端都可以进出数据。下面先来查看LinkedList继承关系图：

手动实现LinkedList

LinkedList底层结构实现和ArrayList底层数据结构实现有着本质上的区别，通过上一小节的内容可以看出ArrayList底层实现主要依赖数组，而LinkedList底层实现则是依赖链表。并且LinkedList底层数据结构是双向链表，因此，需要先定义链表数据节点。

1
2
3
4
5
6
7
8
9
10
11
class Node{
	Node pre;
	Object data;
	Node next;
	public Node(Node pre, E data, Node next) {
		super();
		this.pre = pre;
		this.data = data;
		this.next = next;
	}
}

第一步：LinkedList的实现是双向链表，因此需要定义首节点和尾结点。并且需要保存链表中元素的个数。此外，还需要提供无参构造方法，在构造方法内初始化一个空链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MyLinkedList{
	/**
	 * 链表元素个数
	 */
	private int size;
	/**
	 * 链表首节点
	 */
	private Node first;
	/**
	 * 链表尾结点
	 */
	private Node last;
	/**
	 * 默认构造创建一个空链表
	 */
	public MyLinkedList() {
		first = null;
		last = null;
		size = 0;
	}
}

第二步：添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * 链表中添加节点，默认添加在尾部
  * @param Object
  */
public void add(Object e) {
    if(first==null||last==null||size==0) {
		//说明链表为空链表
		//1.创建新节点
		//2.新节点指为first
		//3.新节点指为last
		Node newNode = new Node(null,e,null);
		first = newNode;
		last = newNode;
	}else {
		//1.创建新节点
		Node newNode = new Node(last,e,null);
		//2.将last节点指向新节点
		last.next = newNode;
			//3.将新节点改为last
		last = newNode;
	}
	size++;
}

当直接添加元素时，默认添加在链表末尾。添加元素时首先判断链表是否为空链表，如果为空链表，则新增加的节点既是首节点，也是尾结点，并且没有前置节点也没有后置节点，因此，新增的节点前置节点和后置节点都为null，当创建好新增的节点后，将首节点和为节点都指向该节点，然后元素个数加一。
当链表不为空链表时，只需要将创建的新节点的前置节点指向尾结点，然后将尾结点指向新创建的节点，然后将元素个数加一。
第二步：定义删除元素方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
	 * 删除索引处节点
	 * @param index
	 * @return
	 */
	public boolean remove(int index) {
		if(index<0||index>size-1) {
			throw new IndexOutOfBoundsException("访问越界");
		}
		if(index==0) {
			if(size==1){
                first = null;
                last = null;
            }else{
                Node removeNode = first;
				first = first.next;
				first.pre = null;
				removeNode.next=null;   
            }
          }
		}else if(index==size-1) {
        	if(size==1){
                first = null;
                last = null;
            }else{
                Node removeNode = last;
                last = last.pre;
                last.next = null;
                removeNode.pre = null;
            }
		}else {  	
            //1.找到索引处的节点
            Node indexNode = getNodeByIndex(index);
            //2.找到索引处的后置节点
            Node next = indexNode.next;
            //3.找到索引处的前置节点
            Node pre = indexNode.pre;
            //4.将索引处前置节点的next指向索引处后置节点
            pre.next = next;
            //5.将索引处后置节点的pre指向索引处前置节点
            next.pre = pre;
		}
		size--;
		return true;
	}

移除元素时，根据元素索引移除，所以要先判断索引是否越界，索引越界时抛出异常，如果没有越界。则判断删除元素的位置：
当删除的是首节点时，首先判断元素个数是否是1，如果只有一个元素，则直接将首节点和尾结点置为null即可。
如果有多个元素时，则先获取首节点，然后获取首节点的后置节点并将获取到节点的pre属性置为null以及将原来首节点的next属性置为null，并将获取到的节点置为新的首结点，最后将元素个数减一即可。
当删除的节点是尾结点时，先判断元素个数是否为1，如果只有一个元素，则直接将首节点和尾结点置为null即可。
如果有多个元素时，则先获取尾结点的前置节点，将获取到的节点的next属性和原来尾结点的pre属性置为null，并将获取到的节点置为新的尾结点。最后将元素个数减一即可。
当删除的节点是中间节点时，首先需要获取删除索引处节点的前置节点和后置节点，即获取n-1处的节点和n+1处的节点，然后将n-1处节点的next指向n+1处节点，并将n+1处的节点pre属性指向n-1处节点。最后将元素个数减一。
第三步：定义查找方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
  * 根据传入的索引找到节点
  * @param i
  * @return
  */
private Node<E> getNodeByIndex(int index){
	//判断索引越界
	if(index<0||index>size) {
		throw new IndexOutOfBoundsException("访问越界");
	}
	if(index==0) {
		return first;
	}else if(index==size-1) {
		return last;
	}else {
		Node<E> current = first;
		for (int i = 0; i < size&&current!=null; i++) {
			if(i==index) {
				return current;
			}
			current = current.next;
		}
			
	}
	return first;
}
/**
 * 根据索引获取元素
 * @param index
 * @return
 */
public E get(int index) {
	Node<E> node = getNodeByIndex(index);
	return node.data;
}

根据索引获取元素，需要判断索引是否越界，如果没有越界则根据传入索引判断获取的是哪个节点的元素。
当索引值为0时，直接返回首节点中保存的数据。
当索引的值为size-1时，直接返回尾结点中保存的数据。
当索引的值在0到size-1之间时，从首节点开始遍历，当遍历的节点索引等于index时，返回该节点中保存的数据。
第四步：定义修改方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 修改索引处的值
 * @param index
 * @param e
 */
public void set(int index,E e) {
	chcekRange(index);
	Node<E> current  = first;
	for (int i = 0; i < size&&current!=null;i++,current = current.next) {
		if(i==index) {
			current.data = e;
		}
	}
}

修改元素时，检查索引是否越界，从首节点开始遍历，直到找到索引处元素并修改值即可

ArrayList和LinkedList的区别

ArrayList和LinkedList虽然都是List接口的子类，但是在底层实现以及效率上存在以下区别

  1. ArrayList和LinkedList都实现了List接口
  2. ArrayList和LinkedList都是非线程安全的，因此在多线程环境下可能会出现出现不同步的情况
  3. ArrayList底层实现是数组，LinkedList底层实现是双向链表
  4. ArrayList因为底层实现是数组，并且支持随机访问因此查找效率高，但是ArrayList在新增元素时会扩容以及复制数组元素，并且删除时也会进行数组复制，所以增删效率低。而LinkedList不支持随机访问，获取元素时必须从首节点开始从前往后遍历查找，因此查找效率低。但是增加和删除时最多涉及到两个节点的操作，因此增删效率高。

ArrayList和LinkedList的遍历

  1. ArrayList和LinkedList都支持使用for循环遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package cn.bytecollege;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * 本例将演示使用for循环遍历ArrayList和LinkedList
 * @author MR.W
 *
 */
public class ForDemo {
	public static void main(String[] args) {
		
		List<String> arrayList = new ArrayList<>();
		arrayList.add("宋远桥");
		arrayList.add("张三丰");
		arrayList.add("张翠山");
		
		for (int i = 0; i < arrayList.size(); i++) {
			System.out.println(arrayList.get(i));
		}
		
		List<String> linkedList = new LinkedList<>();
		linkedList.add("白眉鹰王");
		linkedList.add("金毛狮王");
		linkedList.add("青翼蝠王");
		
		for (int i = 0; i < linkedList.size(); i++) {
			System.out.println(arrayList.get(i));
		}
	}
}

2.使用foreach遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package cn.bytecollege;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
 * 本例将演示使用foreach遍历ArrayList和LinkedList
 * @author MR.W
 *
 */
public class ForeachDemo {
public static void main(String[] args) {
		
		List<String> arrayList = new ArrayList<>();
		arrayList.add("宋远桥");
		arrayList.add("张三丰");
		arrayList.add("张翠山");
		
		for (String s : arrayList) {
			System.out.println(s);
		}
		
		List<String> linkedList = new LinkedList<>();
		linkedList.add("白眉鹰王");
		linkedList.add("金毛狮王");
		linkedList.add("青翼蝠王");
		
		for (String s : linkedList) {
			System.out.println(s);
		}
		
	}
}

3.因为ArrayList和LinkedList都继承了Iterable接口，因此ArrayList和LinkedList都可以使用迭代器进行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package cn.bytecollege;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class IteratorDemo {
	public static void main(String[] args) {
		List<String> arrayList = new ArrayList<>();
		arrayList.add("宋远桥");
		arrayList.add("张三丰");
		arrayList.add("张翠山");
		
		Iterator<String> it1 = arrayList.iterator();
		while(it1.hasNext()) {
			System.out.println(it1.next());
		}
		
		List<String> linkedList = new LinkedList<>();
		linkedList.add("白眉鹰王");
		linkedList.add("金毛狮王");
		linkedList.add("青翼蝠王");
		
		Iterator<String> it2 = linkedList.iterator();
		while(it2.hasNext()) {
			System.out.println(it2.next());
		}
	}
}

除了Iterator以外，List还提供了ListIterator用于遍历List，方法基本和Iterator类似。

4.Lambda表达式遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package cn.bytecollege;

import java.util.ArrayList;
import java.util.List;
/**
 * 使用Lambda遍历
 * @author MR.W
 *
 */
public class LambdaDemo {
	public static void main(String[] args) {
		List<String> arrayList = new ArrayList<>();
		arrayList.add("宋远桥");
		arrayList.add("张三丰");
		arrayList.add("张翠山");
		
		arrayList.forEach(str->{
			System.out.println(str);
		});
	}
}

Queue

Queue 用于模拟队列这种数据结构，队列通常是指”先进先出”（FIFO）的容器。队列的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。
Queue 接口中定义了如下几个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface Queue<E> extends Collection<E> {
    //队列末尾添加元素
    boolean add(E e);
    //将指定的元素添加到队列尾部
    boolean offer(E e);
    //移除队列头部的元素
    E remove();
    //获取队列头部的元素，并删除该元素
    E poll();
    //获取队列头部的元素
    E element();
    //获取队列头部的元素，但是不删除
    E peek();
}
  • boolean add(Object e)∶将指定元素加入此队列的尾部。
  • Object element()∶获取队列头部的元素，但是不删除该元素。
  • boolean offer(Object e)∶将指定元素加入此队列的尾部。当使用有容量限制的队列时，当使用有容量限制的队列时使用offer方法，比使用 add(Object e)方法更好。
  • Object peek()∶获取队列头部的元素，但是不删除该元素。如果此队列为空，则返回 null。
  • Object poll()∶获取队列头部的元素，并删除该元素。如果此队列为空，则返回 null。
  • Object remove()∶获取队列头部的元素，并删除该元素。

Queue 接口有一个PriorityQueue 实现类。除此之外，Queue 还有一个 Deque 接口，Deque 代表一个”双端队列”，双端队列可以同时从两端来添加、删除元素，因此 Deque 的实现类既可当成队列使用，也可当成栈使用。Java 为 Deque提供了ArrayDeque 和 LinkedList 两个实现类。

add()和offer()区别:

add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断！

poll()和remove()区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，但是新的 poll() 方法在用空集合调用时只是返回 null。因此新的方法更适合容易出现异常条件的情况。

element() 和 peek() 区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

下面是Java中Queue的一些常用方法：

add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素 如果队列为空，则返回null
peek 返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素

PriorityQueue实现类

PriorityQueue是一个标准的队列实现，需要注意的是PriorityQueue并不是绝对标准的队列实现，这是因为PriorityQueue保存队列元素的顺序并不是按照加入的顺序，在PriorityQueue内部会对元素的大小进行重新排序。因此，当调用peek()方法或者poll()方法取出队列中的元素时。并不是取出最先进入队列的元素，而是取出队列中最小的元素，从这个意义上来看，PriorityQueue已经违反了队列先进先出的规则。下面，通过示例来查看PriorityQueue的用法.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class PriorityQueueDemo {
	public static void main(String[] args) {
		Queue<Integer> queue = new PriorityQueue<Integer>();
		queue.offer(5);
		queue.offer(-1);
		queue.offer(10);
		queue.offer(30);
		//①打印queue
		System.out.println(queue);
		//获取队列头部的元素并删除
		System.out.println(queue.poll());
	}
}

运行上述程序打印PriorityQueue队列时，发现队列中的元素顺序并不是按照存放的顺序排列的，而是从小到大排列。
PriorityQueue不允许插入null元素，它还需要对队列元素进行排序，PriorityQueue的元素有两种排序方式：

  1. 自然排序：采用自然顺序的PriorityQueue队列中的元素必须实现Comparable接口，并且应该是同一个类的多个示例，否则可能导致转型异常
  2. 定制排序：创建PriorityQueue队列是，传入一个Comparator对象，该对象负责对队列中的所有元素进行排序。采用定制排序时不要求队列元素实现Comparator接口。

Deque接口与ArrayDeque

在上一小节学习的PriorityQueue是一个单向队列，也就是入口和出口是由明显划分的，不能从入口取出元素，反之也不能在出口放入元素。
Deque是Queue的子接口，它代表的了一个双端队列，Deque接口中定义了一些双端队列的方法，这些方法允许从队列两端来操作队列中的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
    boolean addAll(Collection<? extends E> c);
    void push(E e);
    E pop();
    boolean remove(Object o);
    boolean contains(Object o);
    int size();
    Iterator<E> iterator();
    Iterator<E> descendingIterator();
}

下面对接口中的方法进行简要介绍：

  • void addFirst(Object e)：将指定元素插入该双端队列的开头。
  • void addLast(Object e)：将指定元素插入该双端队列的末尾。
  • Iterator descendinglterator()：返回该双端队列对应的迭代器，该迭代器将以逆向顺序来迭代队列中的元素。
  • Object getFirst()：获取但不删除双端队列的第一个元素。
  • Object getLast()：获取但不删除双端队列的最后一个元素。
  • boolean offerFirst(Object e)：将指定元素插入该双端队列的开头。
  • boolean offerLast(Object e)：将指定元素插入该双端队列的末尾。
  • Object peekFirst()：获取但不删除该双端队列的第一个元素;如果此双端队列为空，则返回 null。
  • Object peekLast()：获取但不删除该双端队列的最后一个元素;如果此双端队列为空，则返回 null。
  • Object pollFirst()：获取并删除该双端队列的第一个元素;如果此双端队列为空，则返回 null。
  • Object pollLast()：获取并删除该双端队列的最后一个元素;如果此双端队列为空，则返回 null。
  • Object pop()(栈方法)：pop 出该双端队列所表示的栈的栈顶元素。相当于removeFirstO。
  • void push(Object e)(栈方法)：将一个元素 push 进该双端队列所表示的栈的栈顶。相当于addFirst(e)。
  • Object removeFirst()：获取并删除该双端队列的第一个元素。
  • Object removeFirstOccurrence(Object o)：删除该双端队列的第一次出现的元素 o。
  • Object removeLast()：获取并删除该双端队列的最后一个元素。
  • boolean removeLastOccurrence(Object o)：删除该双端队列的最后一次出现的元素o。

从上面方法中可以看出，Deque 不仅可以当成双端队列使用，而且可以被当成栈来使用，因为该类里还包含了pop（出栈）、push（入栈）两个方法。
Deque接口提供了一个典型的实现类：ArrayDeque，从类名就可以看出，这个队列是基于数组实现的双端队列，创建Deque时可以指定一个numElement参数，该参数用于指定Object[]数组的长度，如果不指定该参数，则ArrayDeque底层数组的默认长度为16。
由于ArrayDeque既可以当做队列使用，又可以当做栈使用，下面的示例首先示范将ArrayDeque使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ArrayDequeDemo {
	public static void main(String[] args) {
		ArrayDeque<String> stack = new ArrayDeque<String>();
		stack.push("Java");
		stack.push("HTML");
		stack.push("Spring");
		//输出stack:[Spring, HTML, Java]
		System.out.println(stack);
		//peek第一个元素，但是并不出栈,输出Spring
		System.out.println(stack.peek());
		//pop第一个元素，出栈并删除
		System.out.println(stack.pop());
		//再次打印stack,输出[HTML, Java]
		System.out.println(stack);
	}
}

上面的示例演示了ArrayDeque作为栈使用，当程序中需要使用栈这种数据结构时，推荐使用ArrayDeque，尽量避免使用Stack，这是因为Stack是一个比较古老的集合，并且性能方面也不尽人意。
当然ArrayDeque也可以当做队列使用，ArrayDeque会按照“先进先出”的方式操作集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ArrayDequeDemo {
	public static void main(String[] args) {
		ArrayDeque<String> queue = new ArrayDeque<String>();
		queue.offer("Java");
		queue.offer("HTML");
		queue.offer("Spring");
		
		//打印queue，输出[Java, HTML, Spring]
		System.out.println(queue);
		//访问队列头部元素，但不出队列输出Java
		System.out.println(queue.peek());
		//poll出第一个元素，输出Java
		System.out.println(queue.poll());
		//再次打印队列，输出[HTML, Spring]
		System.out.println(queue);	
	}
}

LinkedList实现类

LinkedList类时List接口的实现类，也就是说LinkedList可以根据索引来随机访问放入其中的元素，除此以外LinkedList也可以被当做栈和队列使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LinkedListDemo {
	public static void main(String[] args) {
		LinkedList<String> linkedList = new LinkedList<String>();
		//将字符串加入队列末尾
		linkedList.offer("Java");
		//将一个字符串加入栈的顶部
		linkedList.push("Spring");
		//将字符串添加到队列头部（相当于栈的顶部）
		linkedList.offerFirst("HTML");
		//当做list遍历
		for (int i = 0; i < linkedList.size(); i++) {
			System.out.println(linkedList.get(i));
		}
		//访问并不删除栈顶的元素
		System.out.println(linkedList.peekFirst());
		//访问并不删除队列的最后一个元素
		System.out.println(linkedList.peekLast());
		//将栈顶的元素弹出栈
		System.out.println(linkedList.pop());
		//输出[Spring, Java]
		System.out.println(linkedList);
		//访问并删除队列中的最后一个元素
		System.out.println(linkedList.pollLast());
		//输出[[Spring]]
		System.out.println(linkedList);
	}
}

上面的代码分别演示了LinkedList作为List，双端队列及栈的使用，所以LinkedList是一个功能非常强大的类，但是需要注意的是，虽然LinkedList功能强大，开发中如果要当做队列使用，就不要调用栈和list相关的方法，这样做会引起不必要的麻烦以及代码难以维护。