详细讲解见《数据结构与算法分析-Java语言描述》第2版
一、知识准备：
1、ADT(abstract data type)抽象数据类型，带有一组操作的一些对象的集合。简单一点说就是该集合可以有添加（add）、删除（remove）、包含（contains）这些操作。2、链表（linked list）：由一系列节点组成，这些节点不必在内存中相连。每一个节点均含有表元素和到包含该元素后继元的节点的链（link）。称为next链。
3、双链表（double linked list），具体如下图，这里就做不做过多叙述：
4、Collections API，普通数据结构的实现接口，这里列去接口一些最重要的部分： public interface Collecion<AnyType> extends Iterable<AnyType> {
int size(); // 返回集合中的项数
boolean isEmpty(); // 集合的大小为0时，返回true
boolean clear();
boolean contains(AnyType x);// 当x在集合中，则返回true
boolean add(AnyType x);// 从集合中添加x，成功返回true
boolean remove(AnyType x);// 从集合中删除x，成功返回true
java.util.Iterator<AnyType> iterator();// 扩展Iterator接口
}
5、Iterator接口在java.util包中定义的接口： public interface Iterator<AnyType>{ boolean hasNext(); // 下一项是否存在 AnyType next(); void remove(); } 注：Iterator接口还包含一个方法，叫做remove。该方法可以删除又next最新返回的项。这里就有学问了，为什么Collection里面也有一个remove方法，那不是这里这个 remove的出现就多此一举了吗？答案不是这样的，首先第一点，Iterator的remove方法比Collection的remove删除目标项开销要小很多，而且效率也更高；第二点：如果被迭 代时集合进行结构上的改变（增、删、清除..），那么当前的迭代器就不再合法，这样子就会抛出异常，恰恰合适的是，如果使用Iterator的remove方法进行删除的话，就不会发生。
二、List接口、ArrayList类和LinkedLIst类
1、List接口 继承Collection接口，包含其所有方法的同时，自己也外加了一些方法，如下： public interface List<T> extends Collection<T> { T get(int index); T set(int index,T newVal); void add (int index,T x); void remove(int index); ListIterator<T> listIterator(int pos); // 继承了Iterator接口，然后添加了一个从后往前遍历的方法}
2、 ArrayList和LinkedList
ArrayList类提供了List ADT的一种可增长数组的实现。优点在于：对get和set调用花费常数时间。其缺点在于插入和删除代价太高。
LinkedList类提供List ADT的双链表实现。优点在于新项的插入和现在项的删除均开销很小，但在查找上就不怎么好了。
三、栈
遵循后进先出（LIFO）原则，有push和pop操作。
四、队列
遵循先进先出（FIFO）原则，类似一个
五、链表的交换两个相邻元素操作
1、单链表
2、双链表
