文章导读
【List接口定义了线性表数据结构的操作，按照线性表存储方式又分为顺序存储线性表和链式存储线性表，其实现类分别对应ArrayList类和LinkedList类。本文主要讲述ArrayList类和LinkedList类的操作及使用方法。】
文章分成三个小节。第一小节认识List接口，理解其提供的操作方法；第二小节讲述List接口实现类ArrayList的使用方法；第三小节讲述List接口实现类LinkedList类的使用方法。
第一小节 认识List接口
ArrayList和LinkedList是List接口的实现类，List集合接口提供了元素的有序排列，其实现类在插入元素时，插入的元素都会根据索引进行排列。由于 List 的元素在存储时互不干扰，没有什么依赖关系，因此List集合接口可以存储重复的元素。
List集合接口除了继承Collection的接口方法外，还提供了关于元素查询、在指定位置添加元素等操作。下面按操作类型列出并予以说明。
1、List集合添加方法
● boolean add(int nIndex，Object o)
此方法在指定位置插入Object元素。
● boolean addAll(int nIndex，Collection c)
此方法在指定位置插入Collection的所有元素。这些元素按照迭代器 Iterator 返回的先后顺序进行插入。
2、List集合元素查询方法
● int indexOf (Object o)
此方法返回指定元素的第一个匹配项在当前集合中的索引，如果当前集合不包含该元素返回-1。
● int lastIndexOf (Object o)
此方法返回指定元素在当前集合中最后一次出现的位置索引，如果当前集合不包含该元素返回-1。
● Object get (int nIndex)
此方法根据下标查询当前集合中所存储的元素，并返回元素对象。
● boolean contains (Object o)
此方法查询当前集合中是否包含指定的元素，如果包含返回true，否则返回false。
● boolean isEmpty ()
此方法用于判断当前集合是否为空。
List集合接口最常用的两个实现类是ArrayList和LinkedList，这两个类的实现代表两种典型的存储结构，分别是顺序存储和链式存储。
第二小节 认识ArrayList类
可以把ArrayList看成一个动态数组，数组大小能够动态改变，并能动态增加和删除元素。
由于ArrayList基于顺序存储实现，因此可以通过下标索引直接查找到指定位置的元素，其查找效率非常高，但每次插入或删除元素时，需要移动大量元素，因此插入删除元素的效率较低。
下面先通过一个应用实例对ArrayList的用法有个具体了解。
package com.milihua.arrarytest;
import java.util.ArrayList;
import java.util.Iterator;
public class ArraryListTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 实例化ArrayList，用于存储学生姓名
ArrayList<String> studentList = new ArrayList<String>();
//添加学生姓名
studentList.add("李红");
studentList.add("赵梦影");
studentList.add("王国强");
studentList.add("孙立");
// 删除下标为1的元素，此时删除赵梦影
studentList.remove(1);
//删除姓名为王国强的元素
studentList.remove("王国强");
//修改下标为0的元素，此操作把李红修改为李强
studentList.set(0, "李强");
// 输出ArrarList
System.out.println(studentList);
// 遍历ArrayList，输出学生姓名
Iterator i = studentList.iterator();
while (i.hasNext()) {
String s = (String) i.next();
System.out.println(s);
}
}
}例子程序给出了ArrayList的基本用法，包括元素的增加、修改、删除以及遍历。遍历ArrayList时，需要使用迭代器Iterator，使用hasNext方法判断下一个游标位置是否存在元素，再用next方法获取集合的元素，需要将next方法返回的元素强制转换为需要接收的元素类型。
ArraryListTest输出结果如下图所示：
图1 ArraryListTest输出结果
前面介绍了ArrayList存储String类的情况，如果是自定义类呢？下面的示例使用自定义的类作为ArrayList存储的元素，同样提供元素的增、删、改、查操作。
ArrayList存储自定义类的示例程序。
（1）新建一个自定义的Student类
package com.milihua.arrarytest;
public class Student {
public String name="";
public String sex="";
public int age=0;
//利用构造方法传递参数
public Student(String name,String sex,int age) {
super();
this.name =name;
this.sex =sex;
this.age =age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getSex() {
return sex;
}
public void setSex(String sex) {
this.sex = sex;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}（2）再建主方法调用类StudentTest类
package com.milihua.arrarytest;
import java.util.ArrayList;
import java.util.Iterator;
public class StudentTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 这里存入集合的不是系统已定义的类，而是自己创建的Student类
ArrayList<Student> list = new ArrayList<Student>();
// 添加10个Student对象
for (int i = 0; i < 10; i++) {
list.add(new Student("name" + i, "女", 10 + i));
}
// 使用迭代器Iterator删除前面5个元素
Iterator iterator = list.iterator();
int num = 0;
while (iterator.hasNext()) {
// 游标指向下一个
iterator.next();
iterator.remove();
num++;
// 删除前面0到4个，马上退出循环
if (num == 5) {
break;
}
}
// 创建一个Student对象
Student newStudent = new Student("新生", "女", 18);
// 改变集合里面第一个元素的值
list.set(0, newStudent);
// 显示集合里面的元素的具体属性
for (Student st : list) {
System.out.println(st.getName() + "\t" + st.getSex() + "\t" + st.getAge());
}
}
}该示例程序首先创建了Student类，然后在StudentTest类的mian方法中声明并实例化了ArrayList集合，该集合存储的元素类型是Student对象。遍历ArrayList集合采用了forearch语句，foreach语句在遍历数组等方面为程序员提供了很大的方便，其语法规则如下：
for(元素变量 x : 遍历对象obj){
引用了x的java语句
}
StudentTest输出结果如下图所示：
图2 StudentTest输出结果
第三小节 认识LinkedList
LinkedList也是List接口的实现类，与ArrayList不同之处是采用的存储结构不同，ArrayList的存储结构为顺序存储，而LinkedList存储结构是链式存储。链表数据结构的特点是每个元素分配的空间不必连续、插入和删除元素时速度非常快、但访问元素的速度较慢。
LinkedList是一个双向链表, 当数据量很大或者操作很频繁的情况下，添加和删除元素时具有比ArrayList更好的性能。但在元素的查询和修改方面要弱于ArrayList。LinkedList类每个结点用内部类Node表示，LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，当链表为空时，first和last都为NULL值。LinkedList数据结构如下图所示：
图3 LinkedList数据结构
LinkedList类内部的Node结点代码如下：
//存储对象的结构 Node, LinkedList的内部类
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;
}
}Node节点一共有三个属性：item代表节点值，prev代表节点的前一个节点，next代表节点的后一个节点。每个结点都有一个前驱和后继结点，并且在 LinkedList中也定义了两个变量分别指向链表中的第一个和最后一个结点。
transient Node<E> first;
transient Node<E> last;
1、添加元素到LinkedList
LinkedList提供了多个添加元素的方法：
● boolean add(E e)
在链表尾部添加一个元素，如果成功，返回true，否则返回false。
● void addFirst(E e)
在链表头部插入一个元素。
● addLast(E e)
在链表尾部添加一个元素。
● void add(int index, E element)
在指定位置插入一个元素。
添加元素到LinkedList示例代码如下:
package adddemo;
import java.util.LinkedList;
public class LinkedListAddDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println(linkedList);
linkedList.addFirst("addFirst");
System.out.println(linkedList);
linkedList.addLast("addLast");
System.out.println(linkedList);
linkedList.add(2, "addByIndex");
System.out.println(linkedList);
}
}代码通过add、addFirst、addLast方法加入元素，并通过println输出链表元素。输出结果如下图所示：
图4 LinkedListAddDemo输出结果
2、从LinkedList中删除元素
LinkedList提供了多个删除元素的方法：
● boolean remove(Object o)
从当前链表中移除指定的元素。
● E remove(int index)
从当前链表中移除指定位置的元素。
● E removeFirst()
从当前链表中移除第一个元素。
● E removeLast()
从当前链表中移除最后一个元素。
● E remove()
从当前链表中移除第一个元素，同removeLast()相同。
从LinkedList删除元素示例代码如下:
package com.milihua.remove;
import java.util.LinkedList;
public class LinkedListRemoveDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("second");
linkedList.add("third");
linkedList.add("four");
linkedList.add("five");
System.out.println(linkedList);
linkedList.remove();
System.out.println("remove: " + linkedList);
linkedList.remove("second");
System.out.println("remove(Object): " + linkedList);
linkedList.remove("six");
System.out.println("remove(Object) not exist: " + linkedList);
linkedList.remove(2);
System.out.println("remove(index): " + linkedList);
linkedList.removeFirst();
System.out.println("removeFirst: " + linkedList);
linkedList.removeLast();
System.out.println("removeLast:" + linkedList);
System.out.println("----------------------------------");
linkedList.clear();
linkedList.add("first");
linkedList.add("second");
linkedList.add("first");
linkedList.add("third");
linkedList.add("first");
linkedList.add("five");
System.out.println(linkedList);
linkedList.removeFirstOccurrence("first");
System.out.println("removeFirstOccurrence: " + linkedList);
linkedList.removeLastOccurrence("first");
System.out.println("removeLastOccurrence: " + linkedList);
}
}代码通过add方法加入元素，再通过remove、removeFirst、removeLast等方法移除元素，并通过println输出操作后的链表元素。输出结果如下图所示：
图5 LinkedListRemoveDemo输出结果
3、从LinkedList中获取元素
LinkedList提供了多个获取元素的方法：
● E get(int index)
从当前链表中获取指定位置的元素。
● E getFirst()
从当前链表中获取第一个元素。
● E getLast()
从当前链表中获取最后一个元素。
从LinkedList获取元素示例代码如下:
package com.milihua.getdemo;
import java.util.LinkedList;
public class LinkedListGetDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("second");
linkedList.add("third");
linkedList.add("four");
linkedList.add("five");
System.out.println(linkedList);
linkedList.get(3);
System.out.println("get(index): " + linkedList.get(3));
linkedList.getFirst();
System.out.println("getFirst: " + linkedList.getFirst());
linkedList.getLast();
System.out.println("getLast: " + linkedList.getLast());
System.out.println(linkedList);
}
}代码通过add方法加入元素，再通过get、getFirst、getLast方法获取元素，并通过println输出操作后的链表元素。输出结果如下图所示：
图6 LinkedListGetDemo输出结果
4、LinkedList的遍历方法
同前面介绍的集合类遍历方式一样，LinkedList可以通过迭代器、foreach语句、for循环语句等方法遍历集合的所有元素。
遍历LinkedList元素示例代码如下:
package com.milihua.traverse;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListTraverseDemo {
public static void main(String[] args) {
LinkedList<Integer> llist = new LinkedList<Integer>();
for (int i = 0; i < 100000; i++)
llist.addLast(i);
//通过一般for循环来遍历LinkedList
long start = System.currentTimeMillis();
int size = llist.size();
for (int i=0; i<size; i++) {
llist.get(i);
}
long end = System.currentTimeMillis();
long total = end - start;
System.out.println("byCommonFor------->" + total+" ms");
//通过迭代器来遍历LinkedList
start = System.currentTimeMillis();
for(Iterator iter = llist.iterator(); iter.hasNext();)
iter.next();
end = System.currentTimeMillis();
total = end - start;
System.out.println("byIterator------->" + total+" ms");
//通过foreach来遍历LinkedList
start = System.currentTimeMillis();
for (Integer integ:llist)
;
end = System.currentTimeMillis();
total = end - start;
System.out.println("byForEach------->" + total+" ms");
}
}代码采用for循环、迭代器、foreach方式，遍历包含10万个元素的LinkedList，通过输出结果可以看出，foreach语句效率最高，其次是迭代器，效率最差的是for循环。输出结果如下图所示：
图7 LinkedListTraverseDemo输出结果
文章小结
1、每个实例化的ArrayList都有一个容量，该容量用来表示能够存储元素的个数，容量是动态变化的，随着向 ArrayList 中不断添加元素，其容量也会自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果能够预知所能存储的元素个数，可在构造 ArrayList 时指定其容量。
2、LinkedList存储元素的数据结构是双向链表结构，由存储元素的结点连接而成，每一个节点都包含前一个节点的引用，后一个节点的引用和节点存储的值。当一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可。
思考与练习
1、使用ArrayList集合，对其添加100个不同的元素。要求如下：
（1）使用add()方法将元素添加到ArrayList集合对象中；
（2）调用集合的iterator()方法获得Iterator对象，并调用Iterator的hasNext()和next()方法，迭代的读取集合中的每个元素；
（3）调用get()方法先后读取索引位置为50和102的元素，要求使用try-catch结构处理下标越界异常。
2、使用LinkedList模拟队列数据结构。