【每日一学】Java数据结构探秘:队列与List的强大应用与性能优化

学习总目标

本次学习目标

1 数据结构

数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

（1）数据的逻辑结构指反映数据元素之间的逻辑关系，而与他们在计算机中的存储位置无关：

?散列结构：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

?线性结构：数据结构中的元素存在一对一的相互关系；

?树形结构：数据结构中的元素存在一对多的相互关系；

?图形结构：数据结构中的元素存在多对多的相互关系。

（2）数据的物理结构/存储结构：是描述数据具体在内存中的存储（如：数组结构、链式结构、索引结构、哈希结构）等，一种数据逻辑结构可表示成一种或多种物理存储结构。

?数组结构：元素在内存中是连续存储的，即元素存储在一整块连续的存储空间中，此时根据索引的查询效率是非常高的，因为可以根据下标索引直接一步到位找到元素位置，如果在数组末尾添加和删除元素效率也非常高。缺点是，如果事先申请足够大的内存空间，可能造成空间浪费，如果事先申请较小的内存空间，可能造成频繁扩容导致元素频繁搬家。另外，在数组中间添加、删除元素操作，就需要移动元素，此时效率也要打折。

?链式结构：元素在内存中是不要求连续存储的，但是元素是封装在结点当中的，结点中需要存储元素数据，以及相关结点对象的引用地址。结点与结点之间可以是一对一的关系，也可以一对多的关系，比如：链表、树等。遍历链式结构只能从头遍历，对于较长的链表来说查询效率不高，对于树结构来说，查询效率比链表要高一点，因为每次可以确定一个分支，从而排除其他分支，但是相对于数组来说，还是数组[下标]的方式更快。树的实现方式有很多种，无非就是在添加/删除效率 与 查询效率之间权衡。

?索引结构：元素在内存中是不要求连续存储的，但是需要有单独的一个索引表来记录每一个元素的地址，这种结构根据索引的查询效率很高，但是需要额外存储和维护索引表。

?哈希结构：元素的存储位置需要通过其hashCode值来计算，查询效率也很多，但是要考虑和解决好哈希冲突问题。

数据结构和算法是一门完整并且复杂的课程。

Java的核心类库中提供很多数据结构对应的集合类型，例如动态数组、双向链表、顺序栈、链式栈、队列、双端队列、红黑树、哈希表等等。

2 List集合

Collection 层次结构中的根接口。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接实现：它提供更具体的子接口（如 Set 和 List、Queue）实现。我们掌握了Collection接口的使用后，再来看看Collection接口中的子接口，他们都具备那些特性呢？

2.1 List接口介绍

java.util.List接口继承自Collection接口，是单列集合的一个重要分支，习惯性地会将实现了List接口的对象称为List集合。

List接口特点：

?List集合所有的元素是以一种线性方式进行存储的，例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）

?它是一个元素存取有序的集合。即元素的存入顺序和取出顺序有保证。

?它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。

?集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

List集合类中元素有序、且可重复。这就像银行门口客服，给每一个来办理业务的客户分配序号：第一个来的是“张三”，客服给他分配的是0；第二个来的是“李四”，客服给他分配的1；以此类推，最后一个序号应该是“总人数-1”。

注意：

List集合关心元素是否有序，而不关心是否重复，请大家记住这个原则。例如“张三”可以领取两个号。

2.2 List接口中常用方法

List作为Collection集合的子接口，不但继承了Collection接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法，如下：

List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来操作集合元素的方法。

1、添加元素

?void add(int index, E ele)

?boolean addAll(int index, Collection eles)

2、获取元素

?E get(int index)

?List subList(int fromIndex, int toIndex)

3、获取元素索引

?int indexOf(Object obj)

?int lastIndexOf(Object obj)

4、删除和替换元素

?E remove(int index)

?E set(int index, E ele)

在JavaSE中List名称的类型有两个，一个是java.util.List集合接口，一个是java.awt.List图形界面的组件，别导错包了。

2.3 ListIterator迭代器

List 集合额外提供了一个 listIterator() 方法，该方法返回一个 ListIterator 列表迭代器对象， ListIterator 接口继承了 Iterator 接口，提供了专门操作 List 的方法：

?void add()：通过迭代器添加元素到对应集合

?void set(Object obj)：通过迭代器替换正迭代的元素

?void remove()：通过迭代器删除刚迭代的元素

?boolean hasPrevious()：如果以逆向遍历列表，往前是否还有元素。

?Object previous()：返回列表中的前一个元素。

?int previousIndex()：返回列表中的前一个元素的索引

?boolean hasNext()

?Object next()

?int nextIndex()

2.4 List接口的实现类们

List接口的实现类有很多，常见的有：

ArrayList：动态数组

Vector：动态数组

LinkedList：双向链表

Stack：栈

当然，还有很多List接口的实现类这里没有列出来，基础阶段先了解这几个。

2.5 动态数组

1、动态数组的特点

逻辑结构特点：线性结构

物理结构特点：

?申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。

?存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。

例如：整型数组

例如：对象数组

2、自定义动态数组

package com.atguigu.list;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyArrayList<E> implements Iterable<E>{
private Object[] all;
private int total;

public MyArrayList(){
all = new Object[10];
}

public void add(E e) {
ensureCapacityEnough();
all[total++] = e;
}

private void ensureCapacityEnough() {
if(total >= all.length){
all = Arrays.copyOf(all, all.length + (all.length>>1));
}
}

public void insert(int index, E value) {
//是否需要扩容
ensureCapacityEnough();
//添加元素的下标检查
addCheckIndex(index);
if(total-index > 0) {
System.arraycopy(all, index, all, index+1, total-index);
}
all[index]=value;
total++;
}

private void addCheckIndex(int index) {
if(index<0 || index>total){
throw new IndexOutOfBoundsException(index+"越界");
}
}

public void delete(E e) {
int index = indexOf(e);
if(index==-1){
throw new NoSuchElementException(e+"不存在");
}
delete(index);
}

public void delete(int index) {
//删除元素的下标检查
checkIndex(index);
if(total-index-1 > 0) {
System.arraycopy(all, index+1, all, index, total-index-1);
}
all[--total] = null;
}

private void checkIndex(int index) {
if(index<0 || index>total){
throw new IndexOutOfBoundsException(index+"越界");
}
}

public void update(int index, E value) {
//更新修改元素的下标检查
checkIndex(index);
all[index] = value;
}

public void update(E old, E value) {
int index = indexOf(old);
if(index!=-1){
update(index, value);
}
}

public boolean contains(E e) {
return indexOf(e) != -1;
}

public int indexOf(E e) {
int index = -1;
if(e==null){
for (int i = 0; i < total; i++) {
if(e == all[i]){
index = i;
break;
}
}
}else{
for (int i = 0; i < total; i++) {
if(e.equals(all[i])){
index = i;
break;
}
}
}
return index;
}

public E get(int index) {
//获取元素的下标检查
checkIndex(index);
return (E) all[index];
}


public int size() {
return total;
}

public Iterator<E> iterator() {
return new Itr();
}

private class Itr implements Iterator<E>{
private int cursor;

@Override
public boolean hasNext() {
return cursor!=total;
}

@Override
public E next() {
return (E) all[cursor++];
}

@Override
public void remove() {
MyArrayList.this.delete(--cursor);
}
}
}

测试类：

package com.atguigu.list;

import java.util.Iterator;

public class TestMyArrayList {
public static void main(String[] args) {

MyArrayList<String> my = new MyArrayList<>();
my.add("hello");
my.add("java");
my.add("java");
my.add("world");
my.add(null);
my.add(null);
my.add("atguigu");
my.add("list");
my.add("data");

System.out.println("元素个数：" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------");
System.out.println("在[1]插入尚硅谷后：");
my.insert(1, "尚硅谷");
System.out.println("元素个数：" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("--------------------------");
System.out.println("删除[1]位置的元素后：");
my.delete(1);
System.out.println("元素个数：" + my.size());
for (String s : my) {
System.out.println(s);
}

System.out.println("删除atguigu元素后：");
my.delete("atguigu");
System.out.println("元素个数：" + my.size());
for (String s : my) {
System.out.println(s);
}

System.out.println("删除null元素后：");
my.delete(null);
System.out.println("元素个数：" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("------------------------------");
System.out.println("替换[3]位置的元素为尚硅谷后：");
my.update(3, "尚硅谷");
System.out.println("元素个数：" + my.size());
for (String s : my) {
System.out.println(s);
}

System.out.println("替换java为JAVA后：");
my.update("java", "JAVA");
System.out.println("元素个数：" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("------------------------------------");
System.out.println("是否包含java：" +my.contains("java"));
System.out.println("java的位置：" + my.indexOf("java"));
System.out.println("haha的位置：" + my.indexOf("haha"));
System.out.println("[0]位置元素是：" + my.get(0));

System.out.println("------------------------------------");
System.out.println("删除字符串长度>4的元素后：");
Iterator<String> iterator = my.iterator();
while(iterator.hasNext()) {
String next = iterator.next();
if(next != null && next.length()>4) {
iterator.remove();
}
}
System.out.println("元素个数：" + my.size());
for (String string : my) {
System.out.println(string);
}
}
}

3、Java核心类库中的动态数组

Java的List接口的实现类中有两个动态数组的实现：Vector和ArrayList。

（1）ArrayList与Vector的区别？

它们的底层物理结构都是数组，我们称为动态数组。

?ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。

?动态数组的扩容机制不同，ArrayList扩容为原来的1.5倍，Vector扩容增加为原来的2倍。

?数组的初始化容量，如果在构建ArrayList与Vector的集合对象时，没有显式指定初始化容量，那么Vector的内部数组的初始容量默认为10，而ArrayList在JDK1.6及之前的版本也是10，JDK1.7之后的版本ArrayList初始化为长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。

?Vector因为版本古老，支持Enumeration 迭代器。但是该迭代器不支持快速失败。而Iterator和ListIterator迭代器支持快速失败。如果在迭代器创建后的任意时间从结构上修改了向量（通过迭代器自身的 remove 或 add 方法之外的任何其他方式），则迭代器将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就完全失败，而不是冒着在将来不确定的时间任意发生不确定行为的风险。

（2）Vector部分源码分析

public Vector() {
this(10);//指定初始容量initialCapacity为10
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);//指定capacityIncrement增量为0
}
public Vector(int initialCapacity, int capacityIncrement增量为0) {
super();
//判断了形参初始容量initialCapacity的合法性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//创建了一个Object[]类型的数组
this.elementData = new Object[initialCapacity];//默认是10
//增量，默认是0，如果是0，后面就按照2倍增加，如果不是0，后面就按照你指定的增量进行增量
this.capacityIncrement = capacityIncrement;
}

//synchronized意味着线程安全的
public synchronized boolean add(E e) {
modCount++;
//看是否需要扩容
ensureCapacityHelper(elementCount + 1);
//把新的元素存入[elementCount]，存入后，elementCount元素的个数增1
elementData[elementCount++] = e;
return true;
}

private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
//看是否超过了当前数组的容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);//扩容
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//获取目前数组的长度
//如果capacityIncrement增量是0，新容量 = oldCapacity的2倍
//如果capacityIncrement增量是不是0，新容量 = oldCapacity + capacityIncrement增量;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);

//如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;

//如果新容量超过了最大数组限制，那么单独处理
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);

//把旧数组中的数据复制到新数组中，新数组的长度为newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}

public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
//查找obj在当前Vector中的下标
int i = indexOf(obj);
//如果i>=0，说明存在，删除[i]位置的元素
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
public int indexOf(Object o) {
return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {
if (o == null) {//要查找的元素是null值
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)//如果是null值，用==null判断
return i;
} else {//要查找的元素是非null值
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))//如果是非null值，用equals判断
return i;
}
return -1;
}
public synchronized void removeElementAt(int index) {
modCount++;
//判断下标的合法性
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}

//j是要移动的元素的个数
int j = elementCount - index - 1;
//如果需要移动元素，就调用System.arraycopy进行移动
if (j > 0) {
//把index+1位置以及后面的元素往前移动
//index+1的位置的元素移动到index位置，依次类推
//一共移动j个
System.arraycopy(elementData, index + 1, elementData, index, j);
}
//元素的总个数减少
elementCount--;
//将elementData[elementCount]这个位置置空，用来添加新元素，位置的元素等着被GC回收
elementData[elementCount] = null; /* to let gc do its work */
}

（3）ArrayList部分源码分析

JDK1.6：

public ArrayList() {
this(10);//指定初始容量为10
}
public ArrayList(int initialCapacity) {
super();
//检查初始容量的合法性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//数组初始化为长度为initialCapacity的数组
this.elementData = new Object[initialCapacity];
}

JDK1.7

private static final int DEFAULT_CAPACITY = 10;//默认初始容量10
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;//数组初始化为一个空数组
}
public boolean add(E e) {
//查看当前数组是否够多存一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {//如果当前数组还是空数组
//minCapacity按照 默认初始容量和minCapacity中的的最大值处理
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//看是否需要扩容处理
ensureExplicitCapacity(minCapacity);
}
//...

JDK1.8

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//初始化为空数组
}
public boolean add(E e) {
//查看当前数组是否够多存一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!

//存入新元素到[size]位置，然后size自增1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果当前数组还是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//查看是否需要扩容
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//修改次数加1

// 如果需要的最小容量 比 当前数组的长度 大，即当前数组不够存，就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//当前数组容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组容量是旧数组容量的1.5倍
//看旧数组的1.5倍是否够
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//看旧数组的1.5倍是否超过最大数组限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);

//复制一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

public boolean remove(Object o) {
//先找到o在当前ArrayList的数组中的下标
//分o是否为空两种情况讨论
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {//null值用==比较
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {//非null值用equals比较
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;//修改次数加1
//需要移动的元素个数
int numMoved = size - index - 1;

//如果需要移动元素，就用System.arraycopy移动元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);

//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
elementData[--size] = null; // clear to let GC do its work
}

public E remove(int index) {
rangeCheck(index);//检验index是否合法

modCount++;//修改次数加1

//取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素
E oldValue = elementData(index);

//需要移动的元素个数
int numMoved = size - index - 1;

//如果需要移动元素，就用System.arraycopy移动元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

public E set(int index, E element) {
rangeCheck(index);//检验index是否合法

//取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最后返回被替换的元素
E oldValue = elementData(index);
//用element替换[index]位置的元素
elementData[index] = element;
return oldValue;
}
public E get(int index) {
rangeCheck(index);//检验index是否合法

return elementData(index);//返回[index]位置的元素
}

public int indexOf(Object o) {
//分为o是否为空两种情况
if (o == null) {
//从前往后找
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
//分为o是否为空两种情况
if (o == null) {
//从后往前找
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

2.6 链表

1、链表的特点

逻辑结构：线性结构

物理结构：不要求连续的存储空间

存储特点：数据必须封装到“结点”中，结点包含多个数据项，数据值只是其中的一个数据项，其他的数据项用来记录与之有关的结点的地址。

例如：以下列出几种常见的链式存储结构（当然远不止这些）

2、自定义双链表（选讲）

package com.atguigu.list;

import java.util.Iterator;

public class MyLinkedList<E> implements Iterable<E>{
private Node first;
private Node last;
private int total;

public void add(E e){
Node newNode = new Node(last, e, null);

if(first == null){
first = newNode;
}else{
last.next = newNode;
}
last = newNode;
total++;
}

public int size(){
return total;
}

public void delete(Object obj){
Node find = findNode(obj);
if(find != null){
if(find.prev != null){
find.prev.next = find.next;
}else{
first = find.next;
}
if(find.next != null){
find.next.prev = find.prev;
}else{
last = find.prev;
}

find.prev = null;
find.next = null;
find.data = null;

total--;
}
}

private Node findNode(Object obj){
Node node = first;
Node find = null;

if(obj == null){
while(node != null){
if(node.data == null){
find = node;
break;
}
node = node.next;
}
}else{
while(node != null){
if(obj.equals(node.data)){
find = node;
break;
}
node = node.next;
}
}
return find;
}

public boolean contains(Object obj){
return findNode(obj) != null;
}

public void update(E old, E value){
Node find = findNode(old);
if(find != null){
find.data = value;
}
}

@Override
public Iterator<E> iterator() {
return new Itr();
}

private class Itr implements Iterator<E>{
private Node node = first;

@Override
public boolean hasNext() {
return node!=null;
}

@Override
public E next() {
E value = node.data;
node = node.next;
return value;
}
}

private class Node{
Node prev;
E data;
Node next;

Node(Node prev, E data, Node next) {
this.prev = prev;
this.data = data;
this.next = next;
}
}
}

自定义双链表测试：

package com.atguigu.list;

public class TestMyLinkedList {
public static void main(String[] args) {
MyLinkedList<String> my = new MyLinkedList<>();
my.add("hello");
my.add("world");
my.add(null);
my.add(null);
my.add("java");
my.add("java");
my.add("atguigu");

System.out.println("一共有：" + my.size());
System.out.println("所有元素：");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("查找java,null,haha的结果：");
System.out.println(my.contains("java"));
System.out.println(my.contains(null));
System.out.println(my.contains("haha"));

System.out.println("-------------------------------------");
System.out.println("替换java,null后：");
my.update("java","JAVA");
my.update(null,"chai");
System.out.println("所有元素：");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("删除hello，JAVA,null，atguigu后：");
my.delete("hello");
my.delete("JAVA");
my.delete(null);
my.delete("atguigu");
System.out.println("所有元素：");
for (String s : my) {
System.out.println(s);
}
}
}

3、核心类库中LinkedList源码分析

Java中有双链表的实现：LinkedList，它是List接口的实现类。

int size = 0;
Node<E> first;//记录第一个结点的位置
Node<E> last;//记录最后一个结点的位置

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;
}
}

public boolean add(E e) {
linkLast(e);//默认把新元素链接到链表尾部
return true;
}
void linkLast(E e) {
final Node<E> l = last;//用l 记录原来的最后一个结点

//创建新结点
final Node<E> newNode = new Node<>(l, e, null);
//现在的新结点是最后一个结点了
last = newNode;

//如果l==null，说明原来的链表是空的
if (l == null)
//那么新结点同时也是第一个结点
first = newNode;
else
//否则把新结点链接到原来的最后一个结点的next中
l.next = newNode;
//元素个数增加
size++;
//修改次数增加
modCount++;
}

public void add(int index, E element) {
checkPositionIndex(index);//检查index范围

if (index == size)//如果index==size，连接到当前链表的尾部
linkLast(element);
else
linkBefore(element, node(index));
}

Node<E> node(int index) {
// assert isElementIndex(index);

//如果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;
}
}

5、链表与动态数组的区别

动态数组底层的物理结构是数组，因此根据索引访问的效率非常高。但是非末尾位置的插入和删除效率不高，因为涉及到移动元素。另外添加操作时涉及到扩容问题，就会增加时空消耗。

链表底层的物理结构是链表，因此根据索引访问的效率不高，但是插入和删除不需要移动元素，只需要修改前后元素的指向关系即可，而且链表的添加不会涉及到扩容问题。

2.7 栈

堆栈是一种先进后出（FILO：first in last out）或后进先出（LIFO：last in first out）的结构。

栈只是逻辑结构，其物理结构可以是数组，也可以是链表，即栈结构分为顺序栈和链式栈。

核心类库中的栈结构有Stack和LinkdeList。Stack就是顺序栈，它是Vector的子类。LinkedList是链式栈。

体现栈结构的操作方法：

?peek：查看栈顶元素，不弹出

?pop：弹出栈

?push：压入栈

3 队列

队列（Queue）是一种（但并非一定）先进先出（FIFO）的结构。

队列是逻辑结构，其物理结构可以是数组，也可以是链表。队列有普通队列、双端队列、并发队列等等，核心类库中的队列实现类有很多（后面会学到很多），LinkdeList是双端队列的实现类。

==Queue==除了基本的 Collection操作外，==队列==还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。Queue 实现通常不允许插入 元素，尽管某些实现（如 ）并不禁止插入 。即使在允许 null 的实现中，也不应该将 插入到 中，因为 也用作 方法的一个特殊返回值，表明队列不包含元素。

==Deque==，名称 deque 是“double ended queue==（双端队列）==”的缩写，通常读为“deck”。此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。Deque接口的实现类有ArrayDeque和LinkedList，它们一个底层是使用数组实现，一个使用双向链表实现。

此接口扩展了 Queue接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

结论：Deque接口的实现类既可以用作FILO堆栈使用，又可以用作FIFO队列使用。