List集合
List集合代表一个元素有序，可重复的集合，集合中每个元素都有其对应的顺序索引.List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引，例如第一次添加的元素索引为0，第二次添加的元素索引为1.
1.List接口和ListIterator接口
List作为Collection的子接口，当然可以使用Collection接口里的全部方法，而且由于List是有序集合，因此List集合中添加了一些根据索引来操作集合元素的方法。
void add(int index,Object element):将元素element插入到List集合的index处。
boolean addAll(int index,Collection c):将集合c所包含的所有元素都插入到List集合的index处。
Object get(int index):返回集合index索引处的元素。
int indexOf(Object o):返回对象o在List集合中第一次出现的位置索引。
int lastIndexOf(Object o):返回对象o在List集合中最后一次出现的位置索引。
Object remove(int index):删除兵返回index索引处的元素
Object set(int index,Object element):将index索引处的元素替换成element对象，返回被替换的旧元素。
List subList(int fromIndex,int toIndex):返回从索引fromIndex到索引toIndex处所有集合元素组成的子集合。
void replaceAll(UnaryOperator operator):根据operator指定的计算规则重新设置List集合的所有元素。
void sort(Comparator c):根据Comparator参数对List集合的元素排序。
import java.util.*; public class ListTest { public static void main(String[] args) { List<String> books = new ArrayList<String>(); //向books集合中添加三个元素 books.add(new String("龙珠")); books.add(new String("犬夜叉")); books.add(new String("网球王子")); books.add(null); System.out.println(books); //将新字符串对象插入在第二个位置 books.add(1, new String("海贼王")); for(int i = 0; i < books.size(); i++){ System.out.println(books.get(i)); } //删除第三个元素 books.remove(2); System.out.println(books); //判断指定元素在List集合中的位置:输出1，表明位于第二位 System.out.println(books.indexOf(new String("海贼王"))); //将第二个元素替换成新的字符串对象 books.set(1,new String("海贼王")); System.out.println(books); //将books集合的第二个元素(包括)到第三个元素(不包括)截取成子集合 System.out.println(books.subList(1,2)); } }
测试结果：
注意：List判断两个对象是否相等的标准，只要两个对象通过equals()方法返回true即可。
import java.util.*; class A{ public boolean equals(Object obj) { return true; } } public class ListTest2{ public static void main(String[] args) { List<Object> list = new ArrayList<Object>(); list.add(new String("龙珠")); list.add(new String("棋魂")); list.add(new String("游戏王")); System.out.println(list); //list删除一个A对象，将list中的第一个元素删除 list.remove(new A()); System.out.println(list); //将再次删除第一个元素 list.remove(new A()); System.out.println(list); } }
测试结果：
通过上面这段代码可以看出，List集合是通过equals()方法判断两个元素是否相同。
Java8为List集合增加了sort()和repalceAll()两个常用的默认方法，其中sort()方法需要一个Comparator对象来控制元素排序，程序可使用Lambda表达式来作为参数；而replaceAll()方法则需要一个UnaryOperator来替换所有集合元素，UnaryOperator也是一个函数式接口，因此程序也可使用Lambda表达式作为参数。
import java.util.*; public class ListTest3{ public static void main(String[] args) { List<Object> list = new ArrayList<Object>(); list.add("死神"); list.add("海贼王"); list.add("灌篮高手"); list.add("进击的巨人"); list.add("钢之炼金术师"); list.add("棋魂"); //将list按字符串长度顺序排序 list.sort((o1,o2) -> ( ((String)o1).length() - ((String)o2).length())); System.out.println(list); //将list集合中的字符串替换成对应的字符串长度 list.replaceAll(ele -> (((String)ele).length())); System.out.println(list); } }
测试结果：
上面程序对List集合进行了排序，传给sort()方法的Lambda表达式指定的排序规则是：字符串长度越长，字符串越大。
与Set只提供了一个iterator()方法不同，List还额外提供了一个listIterator()方法，该方法返回一个ListIterator对象，ListIterator接口继承了Iterator接口，提供了专门操作List的方法。ListIterator接口在Iterator接口基础上增加了如下方法：
boolean hasPrevious():返回该迭代器关联的集合是否还有上一个元素
Object previous():返回该迭代器的上一个元素。
void add(Object o):在指定位置插入一个元素。
import java.util.*; public class ListIteratorTest{ public static void main(String[] args) { String[] arr = {"龙珠","犬夜叉","游戏王","海贼王","死神","灌篮高手"}; List<String> list = new ArrayList<String>(); for(int i = 0; i < arr.length; i++) { list.add(arr[i]); } ListIterator lit = list.listIterator(); while(lit.hasNext()) { System.out.println(lit.next()); } //开始反向遍历 System.out.println("==================="); while(lit.hasPrevious()) { System.out.println(lit.previous()); } } }
测试结果：
2.ArrayList和Vector实现类
ArrayList和Vector作为List类的两个典型实现，完全支持前面介绍的List接口的全部功能。ArrayList和Vector类都是基于数组实现的List类，所以ArrayList和Vector类封装了一个动态的，允许再分配的Object[]数组。ArrayList或Vector对象使用initialCapacity参数来设置该数组的长度，当向ArrayList或Vector中添加元素超过该数组的长度时，它们的initialCapacity会自动增加。
ArrayList和Vector在用法上几乎完全相同，但有Vector是一个古老的集合（从JDK1.0就有了），那时候Java还没有提供系统的集合框架，所以Vector里提供了一些方法名很长的方法，例如addElement(Object obj)，实际上这个犯法和add(Object obj)没有任何区别。从JDK1.2以后，Java提供了系统的集合框架，就将Vector改为实现List接口，作为List的实现之一，从而导致Vector里有一些功能重复的方法。
实际上，Vector有很多缺点，通常尽量少用Vector实现类。
除此之外，ArrayList和Vector的显著区别是：ArrayList是线程不安全的，当多个线程访问同一个ArrayList集合时，如果有超过一个线程修改了ArrayList集合，则程序必须手动保证该集合的同步性；但Vector集合则是线程安全，无须程序保证该集合的同步性。因为Vector是线程安全的，所以Vector的性能比ArrayList的性能要低。实际上即使需要保证List集合线程安全，也同样不推荐使用Vector实现类。后面会介绍一个Collections工具类，它可以将一个ArrayList变成线程安全的。
固定长度的List
Arrays类是一个操作数组的工具类，它提供了一个方法:asList(Object...a)方法，该方法可以把一个数组或指定个数的对象转换成一个List集合，这个List集合既不是ArrayList实现类的实例，也不是Vector实现类的实例，而是Arrays的内部类ArrayList的实例。
Arrays.ArrayList是一个固定长度的List集合，程序只能遍历访问该集合里的元素，不可增加、删除该集合里的元素。
import java.util.*; public class FixedSizeList{ public static void main(String[] args) { List<String> fixList = Arrays.asList("死神","海贼王","火影"); System.out.println(fixList.getClass()); fixList.forEach(System.out::println); } }
3.Queue集合
Queue用于模拟队列这种数据结构，队列通常是指"先进先出"(FIFO)的容器。队列中的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入到队列的尾部，访问元素(poll)操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。
Queue接口中定义了如下几个方法：
void add(Object e):将指定元素加入此队列的尾部。
Object element():获取队列头部的元素，但是不删除该元素。
boolean offer(Object e):将指定元素加入此队列的尾部，当使用有容量限制的队列时，此方法通常比add(Object e)方法更好。
Object peek():获取该队列头部的元素，但是不删除该元素，如果此队列为空,则返回null。
Object poll()：获取该队列头部的元素，并删除该元素，如果此队列为空，则返回 null。
Object remove():获取队列头部的元素，并删除该元素。
Queue接口有一个PriorityQueue实现类，除此之外，Queue还有一个Deque接口，Deque代表一个“双端队列”，双端队列可以同时从两端来添加、删除元素，因此Deque的实现类既可以当成队列使用，也可以当成栈来使用。Java为Deque提供了ArrayDeque和Linkedlist两个实现类。
PriorityQueue实现类
PriorityQueue是一个比较标准的队列实现类，之所以说它是比较标准的队列实现，而不是绝对标准的队列实现，是因为PriorityQueue保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序，因此当调用peak()方法或者poll()方法取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。从这个意义上来看，PriorityQueue已经违反了队列的最基本规则：先进先出(FIFO)。
import java.util.*; public class PriorityQueueTest{ public static void main(String[] args) { PriorityQueue<Object> pq = new PriorityQueue<Object>(); pq.offer(-3); pq.offer(5); pq.offer(1); pq.offer(9); System.out.println(pq); while(pq.size() != 0) { System.out.println(pq.poll()); } } }
测试结果：
可以看到第一次打印的结果并非按照大小顺序排列的，这是由于PriorityQueue的toString()方法影响，当我们使用poll()方法不断返回PriorityQueue中的内容，可以看到是按照从小到大的顺序排列的。
PriorityQueue不允许插入null元素，它还需要对队列元素进行排序，PriorityQueue的元素有两种排序方式：
自然排序：采用自然顺序的PriorityQueue集合中的元素必须实现了Comparable接口，而且应该是同一个类的多个实例，否则可能导致ClassCastException异常。
定制排序：创建PriorityQueue队列时，传入一个Comparator对象，该对象负责对队列总的所有PriorityQueue队列中的所有元素进行排序。采用定制排序时不要求队列元素实现Comparable接口。
Deque接口与ArrayDeque实现类
Deque接口是Queue接口的子接口，它代表也双端队列，Deque接口里定义了一些双端队列的方法，这些方法允许从两端来操作队列的元素。
void addFirst(Object e):将指定元素插入该双端队列的开头。
void addLast(Object e):将指定元素插入该双端队里的末尾。
Iterator descendingIterator():返回该双端队列对应的迭代器，该迭代器将以逆向顺序来迭代队列中的元素。
Object getFirst():获取但不删除双端队列的第一个元素。
Object getLast():获取但不删除双端队列的最后一个元素
boolean offerFirst(Object e):将指定元素插入该双端队列的开头。
boolean offerLast(Object e):将指定元素插入该双端队列的末尾。
Object peakFirst():获取但不删除该双端队列的第一个元素，如果此双端队列为空，则返回null。
Object peakLast():获取但不删除该双端队列的最后一个元素，如果此双端队列为空，则返回nul
Object pollFirst()：获取并删除该双端队列的第一个元素，如果此双端队列为空，则返回null
Object pollLast():获取并删除该双端队列的最后一个元素，如果此双端队列唯恐，则返回null
Object pop()：弹出该双端队列的栈顶元素，相当于removeFirst()。
void push(Object e):将一个元素push进该双端队列所表示的栈顶，相当于addFirst()。
Object removeFirst():获取并删除该双端队列的第一个元素。
Object removeFirstOccurrence(Object e):删除该双端队列第一次出现的元素o
Object removeLast():获取并删除该双端队列的最后一个元素
Object removeLastOccurrence(Object e):删除该双端队列的最后一次出现的元素o。
import java.util.*;
public class ArrayDequeStack{
public static void main(String[] args) {
//创建一个栈
ArrayDeque<Object> stack = new ArrayDeque<Object>();
stack.push("龙珠");
stack.push("海贼王");
stack.push("火影忍者");
//打印栈中内容，先进后出原则，顺序应该为 火 海 龙
System.out.println(stack);
//获取但不删除栈顶元素
System.out.println(stack.peek());
//获取并删除栈顶元素
System.out.println(stack.pop());
//打印栈中内容
System.out.println(stack);
}
}
测试结果：
LinkedList实现类
LinkedList类是List接口的实现类——这意味着它是一个List集合，可以根据索引来随机访问集合中的元素，除此之外，LinkedList还实现了Deque接口，可以被当成双端队列来使用，因此既可以当成“栈”来使用，也可以当成队列来使用。
import java.util.*; public class LinkedListTest{ public static void main(String[] args) { LinkedList<Object> books = new LinkedList<Object>(); //将元素添加到栈顶 books.push("海贼王"); //将元素添加到队列末尾 books.offer("全职猎人"); //将元素添加到栈顶 books.offerFirst("钢之炼金术师"); books.offerLast("命运石之门"); //以List的方式，按索引打印栈中元素 for(int i = 0; i < books.size(); i ++ ){ System.out.println("遍历中："+books.get(i)); } //访问并不删除第一个元素,打印钢之炼金术师 System.out.println(books.peek()); //访问并不删除最后一个元素,打印命运石之门 System.out.println(books.peekLast()); //弹出栈顶元素 System.out.println(books.pop()); System.out.println(books); } }
测试结果：
LinkedList与ArrayList，ArrayDeque的实现机制完全不同，ArrayList，ArrayDeque内部以数组的形式来保存集合中的元素，因此随机访问集合元素时有较好的性能；而LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入，删除元素时性能比较出色（只需改变指针所指的地址即可）。需要指出的是，虽然Vector也是以数组的形式来存储集合元素的，但因为它实现了线程同步功能（而且实现机制也不好），所以各方面性能都比较差。
使用LinkedList模拟栈和队列
import java.util.*; /* 使用LinkedList模拟队列，先进先出 */ class NewQueue { private LinkedList<Object> list = new LinkedList<Object>(); public void add(Object e) { //将元素添加到栈顶 list.push(e); } public Object del() { //删除栈底元素 return list.pollLast(); } public int size() { return list.size(); } } /* 使用LinkedList模拟栈,先进后出 */ class NewStack{ private LinkedList<Object> list = new LinkedList<Object>(); public void add(Object e) { //将元素添加到栈顶 list.push(e); } public Object del() { //从栈顶删除并返回元素 return list.pollFirst(); } public int size() { return list.size(); } } public class StackTest{ public static void main(String[] args) { NewQueue queue = new NewQueue(); queue.add("海贼"); queue.add("火影"); queue.add("死神"); while(queue.size() != 0) { System.out.println(queue.del()); } //分割线 System.out.println("-------测试栈------------"); NewStack stack = new NewStack(); stack.add("海贼"); stack.add("死神"); stack.add("火影"); while(stack.size() != 0) { System.out.println(stack.del()); } } }
测试结果：
各种线性表的性能分析
Java提供的List就是一个线性表接口，而ArrayList，LinkedList又是线性表的两种典型实现：基于数组的线性表和基于链的线性表。Queue代表了队列，Deque代表了双端队列（即可作为队列使用，也可以作为栈使用），接下来对各种实现类的性能进行分析。
一般来说，由于数组以一块连续的内存区来保存所有的数组元素，所以数组在随机访问时性能最好，所有的内部以数组作为底层实现的集合在随机访问时性能都比较好；而内部以链表作为底层实现的集合在执行插入，删除操作时有较好的性能。但总体来说，ArrayList的性能比LinkedList的性能要好，因此大部分时候应该考虑使用ArrayList。
关于使用List集合有如下建议：
1）如果需要遍历List集合元素，对于ArrayList,Vector集合，应该采用随机访问方法(get)来遍历集合元素，这样性能更好，对于LinkedList集合，则应该采用迭代器来遍历集合元素。
2）如果要经常执行插入，删除操作来改变包含大量数据的List集合的大小，可考虑使用LinkedList集合，使用ArrayList,Vector集合可能需要经常重新分配内部数组大小，效果可能较差。
3）如果有多个线程需要同时访问List集合中的元素，开发者可考虑使用Collections将集合包装成线程安全的集合。