List集合是单列集合的一种,它所存储的元素是可以重复的。List是直接实现Collection接口类的一种。完整的lIst接口类定义如下。
public interface List<E>extends Collection<E>
E是指代了泛型,泛型说明了类属性。
与 set 不同,列表通常允许重复的元素。更确切地讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2,并且如果列表本身允许 null 元素的话,通常它们允许多个 null 元素。 List 接口在 iterator、add、remove、equals 和 hashCode 方法的协定上加了一些其他约定,超过了 Collection 接口中指定的约定。为方便起见,这里也包括了其他继承方法的声明。 List 接口提供了 4 种对列表元素进行定位(索引)访问方法。列表(像 Java 数组一样)是基于 0 的。注意,这些操作可能在和某些实现(例如 LinkedList 类)的索引值成比例的时间内执行。因此,如果调用者不知道实现,那么在列表元素上迭代通常优于用索引遍历列表。 List 接口提供了特殊的迭代器,称为 ListIterator,除了允许 Iterator 接口提供的正常操作外,该迭代器还允许元素插入和替换,以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。 List 接口提供了两种在列表的任意位置高效插入和移除多个元素的方法。
既然是接口,那必然需要实现类了。我们通常需要了解两种,那就是ArrayList,LinkedList。
注意ArrayList只是实现了List,但是并没有继承List接口
public class ArrayList<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, Serializable
可见ArrayList的继承自AbstractList,然后我们查看AbstractList的类定义 查询JDK API说明我们可以看到AbstractList的完整定义
public abstract class AbstractList<E>extends AbstractCollection<E>implements List<E>
溯源
public abstract class AbstractCollection<E>extends Object implements Collection<E>
这些了解就可以,没有什么疑问,Object是根。
ArrayList数据结构为数组,通过数组的特点,我们可以了解到,数组的查询是比较快的,但是增删是比较慢的。
我们来看ArrayList的几个常用的方法。
测试了大部分方法
//1:将指定的元素添加到此列表的尾部。
List l = new ArrayList<>();
//ArrayList L = new ArrayList<>();
l.add("Hello");//一次只能插入一个元素
System.out.println(l);
// 2: add(int index, E element)
l.add(0,"jgdabc");
System.out.println(l);
ArrayList l1 = new ArrayList<>();
l1.add("jgdabc01");
l1.add(20);
System.out.println(l1);
//3:add()方法,整个集合添加
l.add(l1);
l.addAll(1,l1);
System.out.println(l);
//4:addAll(Collection<? extends E> c)
l.addAll(l1);
System.out.println(l);
//5:addAll(int index, Collection<? extends E> c)
//从指定的位置开始,将指定 collection 中的所有元素插入到此列表中。
l.add(1,l1);
System.out.println(l);
//6:clear()
//移除此列表中的所有元素。
l.clear();
System.out.println(l);
//7:contains(Object o)
//如果此列表中包含指定的元素,则返回 true。
boolean flag = l1.contains("jgdabc");
System.out.println(flag);
//8:get(int index)
//返回此列表中指定位置上的元素。如果集合为空,会报异常。
l.add("jgdabc");
String s = (String) l.get(0);
System.out.println(s);
//9:indexOf(Object o)
//返回此列表中首次出现的指定元素的索引,或如果此列表不包含元素,则返回 -1。
int x = l.indexOf("jgdabc");
System.out.println(x);
//10:isEmpty()
//如果此列表中没有元素,则返回 true
boolean flag_1 = l.isEmpty();
System.out.println(flag_1);
//11:lastIndexOf(Object o)
//返回此列表中最后一次出现的指定元素的索引,或如果此列表不包含索引,则返回 -1。
int flag_2 = l.lastIndexOf("jgdabc");
System.out.println(flag_2);
//12:remove(int index)
l.remove(0);
System.out.println(l);
//13:removeRange(int fromIndex, int toIndex)
//移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素。
// removeRange()方法受保护,只提供子类使用
l.add("jgdabc");
l.add("jgdabc01");
ArrayList ll = new ArrayList<>();
ArrayList ll2 = ll;
//14:set(int index, E element)
//用指定的元素替代此列表中指定位置上的元素。
l.set(0, "zhan");
System.out.println(l);
// 15:toArray()
//按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组
l.toArray();
System.out.println(l);
// 17:trimToSize()
//将此 ArrayList 实例的容量调整为列表的当前大小。
((ArrayList<Object>) l).trimToSize();
System.out.println(l.size());
其中需要注意的就是两个方法,一个removeRange(),这个方法虽然在ArrayList中被提供,但是受到保护,只能被子类使用。也就是写一个继承类就好。 还有一个方法,可能并不常用。其实涉及到优化。那就是trimToSize()方法
ArrayList 的内部使用数组存储元素,当数组将被存满,就会创建一个新数组,其容量是当前数组的 1.5 倍。 同时,所有元素都将移至新数组,假设内部数组已满,而我们现在又添加了 1 个元素,ArrayList 容量就会以相同的比例扩展(即前一个数组的1.5倍)。 在这种情况下,内部数组中将有一些未分配的空间。 这时,trimToSize() 方法可以删除未分配的空间并更改 ArrayList 的容量,使其等于 ArrayList 中的元素个数。
先来看一个代码
package java_practice;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ListDemo {
public static void main(String args[]) {
List<String> list = new ArrayList<String>();
list.add("Hello");
list.add("world");
list.add("java");
Iterator<String> it = list.iterator();
while(it.hasNext()) {
String s = it.next();
if(s.equals("world"))
{
list.add("javaee");
}
}
// for(int i=0;i<list.size();i++)
// {
// String s = list.get(i);
// if(s.equals("world"))
// {
// list.add("javaee");
// }
//
// }
System.out.println(list);
}
}
很显然这里抛出了异常,为什么会这样呢?
下面摘录异常信息
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:907)
at java.util.ArrayList$Itr.next(ArrayList.java:857)
at java_practice.ListDemo.main(ListDemo.java:16)
我们根据checkForComodification步步跟进源码 下面是跟进和溯源处理后的关键源码信息
public interface List<E>{
Iterator<E> iterator();
boolean add(E e)
}
public abstract class AbstractList<E>
{
protected transient int modCount = 0;
}
public class ArrayList<E> extends AbstractList<E>implements List<E>
{
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!//每次调用add()会使modCount++
elementData[size++] = e;
return true;
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int expectedModCount = modCount;
//modCount为实际修改集合的次数
//expectedModCount为预期修改集合的次数
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
//modCount为修改集合的次数,exceptedModCount为预期修改集合的次数
throw new ConcurrentModificationException();
}
}
/**
}
源码很清楚了,而且我做了部分注释,可以自己捋一下。原因就是,我们采用迭代器的时候,迭代器会有一个预期的迭代次数,当我们进行在迭代的同时进行添加的时候会调用add()方法的话,就会modCount++(实际迭代次数),但是expectedModCount(预期迭代次数)没有进行处理同步,造成了数据不一致,源码也说明了,如果不一致,就会抛出异常。 提出一种解决的办法,避免数据不一致,比如for循环。
package java_practice;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ListDemo {
public static void main(String args[]) {
List<String> list = new ArrayList<String>();
list.add("Hello");
list.add("world");
list.add("java");
Iterator<String> it = list.iterator();
// while(it.hasNext()) {
// String s = it.next();
// if(s.equals("world"))
// {
// list.add("javaee");
// }
//
//}
for(int i=0;i<list.size();i++)
{
String s = list.get(i);
if(s.equals("world"))
{
list.add("javaee");
}
}
System.out.println(list);
}
}
可能在这里你可能有疑问,get()俩面不也有add()吗?为什么不报异常。上面源码也摘录出来了。原因就是我们调用了集合的add()方法,实际上会使实际迭代次数加一的,但是get()函数里面没有进行实际与预期的判断,也自然不会抛出异常,可以参考上诉源码,明明白白。
List集合特有的迭代器 接口完整定义
public interface ListIterator<E>extends Iterator<E>
JDK API说明
系列表迭代器,允许程序员按任一方向遍历列表、迭代期间修改列表,并获得迭代器在列表中的当前位置。 演示一个使用
package java_practice;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class ListDemo {
public static void main(String args[]) {
List<String> list = new ArrayList<String>();
list.add("Hello");
list.add("world");
list.add("java");
Iterator<String> it = list.iterator();
// while(it.hasNext()) {
// String s = it.next();
// if(s.equals("world"))
// {
// list.add("javaee");
// }
//
//}
//
ListIterator<String> lit = list.listIterator();
while(lit.hasNext())
{
String s = lit.next();
if(s.equals("world"))
{
lit.add("javaee");
}
}
System.out.println(list);
}
}
一个疑问就是为什么ListIterator没有报异常? 我们还是追溯源码,最终整理如下
public interface List<E>{
Iterator<E> iterator();
ListIterator<E> listIterator();
boolean add(E e)
}
public abstract class AbstractList<E>
{
protected transient int modCount = 0;
}
public class ArrayList<E> extends AbstractList<E>implements List<E>
{
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!//每次调用add()会使modCount++
elementData[size++] = e;
return true;
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
public ListIterator<E> listIterator() {
return new ListItr(0);
}
}
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
追诉到根本就是ListItr的add()方法。通过源码分析可以了解到,这里的add()方法在使用后会给预期的变量重新赋值,所以会使预期和实际的统一,这样就不会报异常了。
还是从JDK API查找资料从Collection出发
public interface Collection<E>extends Iterable<E>
追溯Iterable,有理可依。
public interface Iterable<T>实现这个接口允许对象成为 "foreach" 语句的目标。
并且Iterable给出了其可使用的迭代器
Iterator iterator() 返回一个在一组 T 类型的元素上进行迭代的迭代器。
所以可以了解到增强for循环,简化数组和Collection集合的遍历。实现Iterable的类允许其对象成为增强型for循环语句的目标。版本在JDK5之后,内部实现原理是Iterator迭代器。 使用格式如下:
举例示范
int[] arr = {1,2,3,4,5};
for(int i:arr)
{
System.out.println(i);
}
List<String> list = new ArrayList<String>();
list.add("Hello");
list.add("world");
list.add("java");
for(String s :list)
{
System.out.println(s);
}
如何验证内部实现原理是Iterator迭代器,通过Iterator迭代器迭代添加过程中的并发修改异常的特点来验证
List<String> list = new ArrayList<String>();
list.add("Hello");
list.add("world");
list.add("java");
for(String s :list)
{
if(s.equals("java")){
list.add("javaee");
}
System.out.println(s);
}
异常信息摘录: Exception in thread “main” java.util.ConcurrentModificationException at java.util.ArrayList
Itr.next(ArrayList.java:857) at java_practice.ListDemo.main(ListDemo.java:15)
这里的异常和并发修改的异常一样,所以可以验证出内部实现原理是Iterator迭代器。也可以通过异常追溯源码来验证。
基本的继承关系上,同ArrayList一样不是直接继承List接口,是一个实现类。 我们还是明确它的继承以及实现关系
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, Serializable
LinkedList的底层实现是链表,并且是双向链表。
与ArrayList相比,ArrayList的基本实现是数组,数组是便于进行查找的,而LinkedList的基本是实现双向链表是方便去进行增删改,但是不是很适合去随机查询。当然是和数组相比较。这个双向链表的顺序查找效率还是比较高的,因为是双向链表嘛!每个节点都有一个直接前驱和直接后继。前驱和后继可以认为是指针(C语言中的灵魂)。
我们来看方法说明,其实很多方法还是和ArrayList的方法一样的。 add() addAll,clear(),clone(),contains(),get(),indexof(),lastIndexof(),remove(),set(),toArray()。基本上这几个方法都和ArrayList的方法使是一样的。 具体的看一些新的方法。我们分开说明
1:removeLastOccurrence(Object o) 从此列表中移除最后一次出现的指定元素(从头部到尾部遍历列表时)。
LinkedList link = new LinkedList<>();
link.add("jgdabc");
link.add("jink");
link.add("jgdabc");
System.out.println(link);
link.removeLastOccurrence("jgdabc");
System.out.println(link);
相应的一样道理 2:removeFirstOccurrence(Object o) 从此列表中移除第一次出现的指定元素(从头部到尾部遍历列表时)。
LinkedList link = new LinkedList<>();
link.add("jgdabc");
link.add("jink");
link.add("jgdabc");
System.out.println(link);
link.removeFirstOccurrence("jgdabc");
System.out.println(link);
3:removeLast() 移除并返回此列表的最后一个元素。改方法在移除的同时会返回移除的元素。
link.removeFirstOccurrence("jgdabc");
System.out.println(link);
String s_s = (String) link.removeLast();
System.out.println("移除元素后的集合:"+link);
System.out.println("被移除的元素:"+s_s);
同样, 4:removeFirst() 移除并返回此列表的第一个元素。不再举例 5:push(E e) 将元素推入此列表所表示的堆栈。此方法就是压栈的操作。 该方法的效果等同于addFirst() 对应还有 6:pop(E e) 出栈,此方法等效于removeFirst()
link.push("jgdabc");
System.out.println(link);
link.pop();
System.out.println(link);
7:pollLast() 获取并移除此列表的最后一个元素;如果此列表为空,则返回 null 8:pollFirst() 获取并移除此列表的第一个元素;如果此列表为空,则返回 null。 9:poll() 获取并移除此列表的头(第一个元素)
String s_ = (String) link.pollLast();
System.out.println(s);
String s_1 = (String) link.pollFirst();
System.out.println(s_1);
String s_2 = (String) link.poll();
System.out.print(s_2);
10:peekLast() 获取但不移除此列表的最后一个元素;如果此列表为空,则返回 null。 11:peekFirst() 获取但不移除此列表的第一个元素;如果此列表为空,则返回 null。 12:peek() 获取但不移除此列表的头(第一个元素)。
String s_3 = (String) link.peekFirst();
System.out.println(s_3);
String s_4 = (String) link.peekLast();
System.out.println(s_4);
String s_5 = (String) link.peek();
System.out.println(s_5);
13:offerLast(E e) 在此列表末尾插入指定的元素。 14:offerFirst(E e) 在此列表的开头插入指定的元素。 15:offer(E e) 将指定元素添加到此列表的末尾(最后一个元素)。
boolean flag_f= link.offerFirst("jgdabc");
System.out.println(flag_f);
System.out.println(link);
boolean baby = link.offerLast("baby");
System.out.println(baby);
System.out.println(link);
boolean come_on = link.offer("come on");
System.out.println(come_on);
System.out.println(link);
14: Iterator descendingIterator() 返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 具体的我们举个例子,看看这个逆向迭代器的使用,后面还会总结迭代方法
Iterator iterator = link.descendingIterator();
while(iterator.hasNext())
{
System.out.println(iterator.next());
}
vector已经废弃,不再叙述。至于为什么现在基本不用了,之后会写一篇专门详细介绍