Java的简单理解(11)-链表
常见数据结构的Java实现
编写程序时经常要和各种数据打交道，因此所选择的数据结构对于程序的运行效率是非常重要的。一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表，栈，队列，串，数组和文件；非线性数据结构有树和图。在JDK中，Java提供了实现常见数据结构的类，使创建链表等数据结构和创建数组一样简单，不在需要去写具体的算法。
1. 链表
线性表是最基本，最简单，也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是首尾相连的。线性表的逻辑结构简单，便于实现和操作。因此线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
线性表的逻辑结构是n个数据元素的有限序列：
(a1,a2,a3,...an)
n为线性表的长度(n>=0)，n=0的表称为空表。
数据元素呈线性关系，必存在唯一的称为"第一个"的数据元素，必存在唯一地称为“最后一个”的数据元素，除第一个元素外，每个元素都有且只有一个前驱元素，除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素在同一个线性表中必须是相同的数据类型。
在实际应用中，线性表都是以栈，队列，字符串，数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此掌握这些特殊线性表的特性对于数据运算的可靠性和提高操作效率都是至关重要的。
线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储，将线性表中的数据元素依次存放在某个存储区域中的表称为顺序表；用链式存储结构存储的线性表称为链表。一维数组是用顺序方式存储的线性表。
如果需要处理一些类型相同的数据，人们习惯上使用数组这种数据结构，但数组在使用之前必须定义大小，而且不能动态定义大小。链表是由若干个称作节点的对象组成的一种数据结构，分为两种类型。
- 单链表：每个节点含有一个数据和下一个节点对象的引用。
- 双链表：含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用。
2. 链表的创建
使用java.util包中的LinkedList类，可以创建一个链表对象。
LinkedList mylist = new LinkedList(); // 创建了一个空双链表
也可以使用add方法向链表依次增加节点。
mylist.add("It");
mylist.add("is");
mylist.add("a");
mylist.add("door");
这样就形成了四个节点的链表，数据依次为“It”，“is”，“a”，“door”，四个节点是自动连接的。mylist可以使用方法public Object get(index i)获取第i个节点中存储的数据。存放在节点中的数据都被看作是一个Object对象。
3. LinkedList类中的常用方法
public boolean add(Object element)// 向链表末尾添加一个新的节点，该节点中的数据是参数element指定的对象
public boolean add(int index,Object element)// 向链表指定位置添加节点，该节点中的数据是参数element指定的对象
public void addFirst(Object element)// 向链表头添加新节点，该节点中的数据是参数element指定的对象
public void addLast(Object element)// 向链表尾添加新节点，该节点中的数据是参数element指定的对象
public Object removeFirst()// 删除第一个节点，并返回这个节点中的对象。
public Object removeLast()// 删除最后一个节点，并返回这个节点中的对象。
public Object remove(int index)// 删除指定位置的节点
public Object get(int index)// 得到指定位置的节点
public Object getFirst()// 得到链表第一个节点的对象
public Object getLast()// 得到链表最后一个节点的对象
public int indexOf(Object element)// 返回节点对象element在链表中首次出现的位置，如果链表中无此节点对象则返回-1
public int lastIndexOf(Object element)//返回节点对象element在链表中最后出现的位置，如果链表中无此节点对象则返回-1
public Object set(int index, Object element)// 将当前链表index位置节点中的对象替换成参数element指定的对象，返回被替换对象。
public int size()// 返回链表的长度，即节点的个数。public boolean contains(Object element)// 判断链表节点对象中是否含有element。
4. 使用Iterator类遍历链表
迭代器(Iterator)模式又叫做游标(Cursor)模式。它的定义为: 提供一种方法访问一个容器(Container)对象中各个元素，而又不需要暴露该对象的内部细节。
从定义可见，迭代器模式是为容器而生的。很明显，对容器对象的访问必然涉及到遍历算法。迭代器提供了一种通用的方式来访问集合中的元素。
- boolean hasNext(); 如果仍有元素可以迭代，则返回true。
- Object next(); 返回迭代的下一个元素。
- void remove(); 从迭代器指向的集合中移除迭代器返回的最后一个元素。
当使用Iterator接口遍历链表时，一个链表对象可以使用iterator()方法获取Iterator变量，Iterator对象中每个数据成员刚好是链表节点中的数据，而且这些数据成员是按顺序存放在Iterator对象中的，Iterator对象使用next()方法可以得到其中的数据成员。
LinkedList list = new LinkedList();
Iterator iter = list.iterator();
while (iter.hasNext()) {
Student te = iter.next();
}
