上篇List接口介绍: https://blog.csdn.net/weixin_46369022/article/details/119516882.
实现类引入
List实现类在List接口基础上有增加了每个实现类独有的方法。
补：
List list = new ArrayList();
list只能可以引用List当中的方法，不能引用ArrayList中的独有方法
ArrayList list=new ArrayList();
list可以引用所有方法
ArrayList:动态数组
物理结构：数组
所以插入和删除操作比较慢，查询比较快
(1)new ArrayList()：
JDK1.8版本：发现内部初始化为了一个长度为0的空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
JDK1.7版本：也是初始化为长度为0的空数组 EMPTY_ELEMENTDATA;
JDK1.6版本：初始化为长度为10的数组
为什么要初始化为空数组呢？
因为开发中，很多时候创建了ArrayList的对象，但是没有装元素，这个时候的话，如果初始化为10的数组，就浪费空间了。
源码：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
(2)add(Object e）
JDK1.8： 第一次添加元素，扩容为长度为10的数组， 如果不够了，再扩容为1.5倍。
源码：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
// DEFAULT_CAPACITY=10
}
ensureExplicitCapacity(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);
//0右移一位还是0;10右移一位是5
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//所以第一次添加数据,扩容为10
//第二次扩容，扩容为10+5
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);
}
Vector:动态数组
物理结构：数组
（1）new Vector()：数组初始化长度为10的数组，capacityIncrement默认扩容增量是0
源码：
Vector v=new Vector();
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
（2）add(E e)：直接插入元素
默认扩容为原来的2倍
如果你手动指定了capacityIncrement的值，那么可以按照你指定增量进行扩容。
源码：
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(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;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);//**
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
（3）add(index,e)：根据索引插入元素
源码：
public void add(int index, E element) {
insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
（4）remove(index)：
①计算要移动元素的个数
②如果需要移动，调用System.arraycopy方法进行移动
③elementData[–elementCount] = null;
源码：
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
（5）remove(Object obj)
①查找obj的下标
②如果不是-1就调用remove(index)进行删除
源码：
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
（6）indexOf(Object obj)
对obj分情况讨论：（1）是null（2）不是null
源码：
public int indexOf(Object o) {
return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Stack: 栈
物理结构：数组
先进后出（FILO）或后进先出（LIFO：Last in first out）
Stack是Vector的子类，比Vector多了几个方法，它的后进先出的特征，就是通过调用这几个方法实现的。
(1)Object peek() ：访问当前栈顶元素，但是不拿走栈顶元素
返回size-1位置的元素
源码：
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
(2)Object pop()：弹出栈顶元素
①先peek()返回栈顶元素
②删除size-1位置的元素
源码：
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
(3)Object push(Object item) ：把元素压入栈顶，等价于add(item)
这里为了更形象化，单独设计了一个push。
把元素添加到[size++]位置
源码：
public E push(E item) {
addElement(item);
return item;
}
使用示例：
Stack s = new Stack();
s.push("1");//push比add可读性更好，功能是一样的
s.push("2");
s.add("3");
s.add("4");
System.out.println(s.peek());//4
System.out.println(s.peek());//4
System.out.println(s.pop());//4
System.out.println(s.pop());//3
System.out.println(s.pop());//2
System.out.println(s.pop());//1
// System.out.println(s.pop());//java.util.EmptyStackException
LinkedList:双向链表
物理结构：链表
LinkedList可以被当做单项列表双向链表、栈、队列、双端队列等数据结构使用，功能强大。但是实际运用开发很少使用
内部有一个结点的类型：
class Node{
? ??????????????? Object data;
????????????????? Node previous;
????????????????? Node next;
???????????????? }
源码：
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;
}
}
(1)new LinkedList()： 什么也没干，没有创建结点
源码：
public LinkedList() {
}
(2)add(e)
源码：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
//新结点的上一节点是刚刚的最后一个结点
//新结点的下一个结点是null，没有
final Node<E> newNode = new Node<>(l, e, null);
//新结点成为了最后一个结点
last = newNode;
if (l == null)
first = newNode;
//上一节点为空说明链表中没有节点为空，新结点是第一个结点也是最后一个节点
else
l.next = newNode;
size++;
modCount++;
}
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;
}
}
(3)remove 删除
源码：
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
//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;//被删除结点的上一个结点的next指向被删除结点的下一个结点
x.prev = null;//把被删除结点与上一个结点断开
}
if (next == null) {//被删除结点是最后一个结点
last = prev;//被删除结点的上一个结点成为了最后一个结点
} else {//被删除结点不是最后一个结点
next.prev = prev;//被删除结点的下一个结点的prev指向被删除结点的上一个结点
x.next = null;//把被删除结点与下一个结点断开
}
x.item = null;//把被删除结点的数据清空
size--;
modCount++;
return element;
}
当做双向链表使用：
(1)E getFirst()
(2)E getLast()
(3)boolean offerFirst(E e) ：添加的第一个
(4)boolean offerLast(E e) :添加到最后一个
(5)int indexOf(Object o) ：从first开始找
(6)int lastIndexOf(Object o) ：从last开始找
(7) E get(int index) 先判断index是靠前还是靠后
当做栈使用
E peek()
E pop()
void push(E e)
当做队列使用
实现了Queue接口
队列：先进先出（FIFO） 一边出
操作失败情况：
插入队头: add(e) ????? ?????offer(e)
移除队头: remove() ????????poll()
检查队头 :element() ???????peek()
LinkedList list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list.poll());//1
System.out.println(list.poll());//2
System.out.println(list.poll());//3
System.out.println(list.poll());//4
当做双端队列使用
实现了Deque（double ended queue（双端队列）的缩写）接口，
两边均能出
总结
一、 List接口的实现类们：
1、Vector：动态数组
物理结构：数组
2、ArrayList：动态数组
物理结构：数组
3、Stack：栈，它是Vector的子类
物理结构：数组
4、LinkedList：双向链表
物理结构：链表
问题：Vector和ArrayList的区别？都是动态数组有什么不同？
Vector：最早版本的动态数组（旧版），线程安全的（有线程同步的），不够后扩容为原来的2倍（造成空间浪费的可能性比较大），初始容量：10，Vector支持的遍历集合的方式有：（1）foreach（2）Iterator（3）支持旧版的Enumeration迭代器
ArrayList：相对Vector来说新一点（新版），线程不安全的（没有线程同步的），不够后扩容为原来的1.5倍（造成扩容的次数增大），初始容量：10，ArrayList支持的遍历集合的方式有：（1）foreach（2）Iterator
Vector和ArrayList的使用时，为了比较空间浪费，和扩容次数太多，如果能够预估大概的元素个数，那么可以用
ArrayList(int initialCapacity)和Vector(int initialCapacity)直接初始化为一定容量的数组。