1表的定义
一般表格，例如A0、A1、A2、An-1，其中该表格的大小为n，在N=0时称为空表格。 Ai后继Ai-1、Ai-1前驱Ai，表中最初的元素为A0，最后的元素为AN-1。
与这些定义相关的是，表上的操作集合、打印列表打印表、makeEmpty空表、find是最先出现的位置，insert插入元素，remove删除元素，findKth返回某个位置的元素
2表的实现方式
2.1表的数组安装
可以通过使用数组对表执行所有操作。 虽然数组是以固定容量创建的，但如果需要，可以以两倍的容量创建不同的数组。
1英特尔=新英特尔；
2
3 .
4
5int [ ]新arr=新int [ arr .长度*2]；
6 for (英制=0； iarr .长度； I ) {2}
7新arr=arr；
8 }
9 arr=新arr；
根据数组实现表的格式，print List以线性时间执行，findKth操作需要一定的时间。 但是，插入和删除的成本潜在着昂贵的成本，数组不是一个很好的选择，尤其是在桌面前端。 在这种情况下，请考虑使用另一个数据结构，即链表
2.2表的链表的实现
为了避免插入和删除的线性开销，必须允许表不连续地存储。 否则，表的各部分可能会影响整体。 图1给出了链表的一般思路。
图1 .链表
链表由一系列不需要在内存中连接的节点组成。 每个节点都包含一个表元素，以及指向包含该元素后继者的节点的链。 要运行printLis或find(x )，请从表的第一个节点开始，在后续的next链中遍历表。
remove方法可以通过修改next引用来实现。 图2显示了从原表中删除第三个元素的结果。
图2 .从链表中删除
insert方法必须使用new操作符从系统移动到新节点，然后执行两次引用调整。 其一般想法如图3所示。 其中，虚线表示原始的next引用。
图3 .插入链表
如图3所示，如果知道发生变动的地方，向链表插入项目或从链表删除项目的操作不需要移动很多项目，只设计常数个节点链的变更。 如图4所示，使各节点具有通向前体节点的链，构成双链表。
图4 .双链表
3. ArrayList类和链接的list类
ArrayList类和LinkedList类都实现了List接口，List接口继承了Collection接口，他们的继承关系如图5所示。
图5 .表的继承关系
所以无论是数组列表系统还是链接列表系统
包含有接口Collection和List所定义的方法。collection主要方法:
boolean add(Object o)添加对象到集合；boolean remove(Object o)删除指定的对象；int size()返回当前集合中元素的数量；boolean contains(Object o)查找集合中是否有指定的对象；boolean isEmpty()判断集合是否为空；Iterator iterator()返回一个迭代器；boolean containsAll(Collection c)查找集合中是否有c中的元素；boolean addAll(Collection c)将集合c中所有元素添加给该集合；void clear()删除集合中所有元素；void removeAll(Collection c)从集合中删除c集合中也有的元素；void retainAll(Collection c)从集合中删除集合c中不包含的元素。list主要方法：
void add(int index,Object element)在指定位置上添加一个对象；boolean addAll(int index,Collection c)将集合c的元素添加到指定的位置；Object get(int index)返回List中指定位置的元素；int indexOf(Object o)返回第一个出现元素o的位置；Object remove(int index)删除指定位置的元素；Object set(int index,Object element)用元素element取代位置index上的元素,返回被取代的元素；void sort()排序方法。3.1ArrayList类
ArrayList包含了两个重要的对象：
elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。 size 则是动态数组的实际大小。ArrayList三种遍历方法
1//第一种，通过迭代器遍历。即通过Iterator去遍历。 2 3Integer value = null; 4Iterator iter = list.iterator(); 5while (iter.hasNext()) { 6 value = (Integer)iter.next(); 7} 8 9//第二种，随机访问，通过索引值去遍历。 10由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。 11 12Integer value = null; 13int size = list.size(); 14for (int i=0; i<size; i++) { 15 value = (Integer)list.get(i); 16} 17 18//第三种，for循环遍历。如下： 19 20Integer value = null; 21for (Integer integ:list) { 22 value = integ; 23}ArrayList使用案例
1package ArrayListPackage; 2import java.util.ArrayList; 3import java.util.Iterator; 4public class ArrayListTest { 5 6 public static void main(String[] args) { 7 // TODO Auto-generated method stub 8 9 //创建一个数组链表对象list 10 ArrayList<String> list = new ArrayList<String>(); 11 12 //增加元素到list对象中 13 list.add("翟天临"); 14 list.add("秀丽的羊"); 15 list.add("和谐的钢铁侠"); 16 list.add("冷酷的香氛"); 17 list.add("rxdxlz"); 18 19 //显示数组链表中的内容 20 System.out.println("ArrayList 包含如下元素"+list); 21 22 //替换元素 23 list.set(4, "完美的嚓茶"); 24 System.out.println("替换后的ArrayList 包含如下元素"+list); 25 26 //检查元素的位置 27 int position = list.indexOf("秀丽的羊"); 28 System.out.println("秀丽的羊在ArrayList中的位置是:"+position); 29 30 //获取链表的大小 31 int size = list.size(); 32 System.out.println("ArrayList链表的大小为："+size); 33 34 //遍历ArrayList中所有的元素 35 Iterator<String> it = list.iterator(); 36 System.out.println("使用iterator遍历ArrayList中所有元素"); 37 for(;it.hasNext();){ 38 System.out.println("ArrayList 元素包括 "+it.next()); 39 } 40 } 41 42}输出结果为：
图6. 输出结果
3.2 LinkedList类
LinkedList的本质是双向链表，包含两个重要的对象：
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。size是双向链表中节点的个数。Linked的遍历方式
1//通过迭代器遍历。即通过Iterator去遍历。 2for(Iterator iter = list.iterator(); iter.hasNext();) 3 iter.next(); 4 5//通过快速随机访问遍历LinkedList 6int size = list.size(); 7for (int i=0; i<size; i++) { 8 list.get(i); 9} 10 11//通过另外一种for循环来遍历LinkedList 12for (Integer integ:list) 13 ; 14 15//通过pollFirst()来遍历LinkedList 16while(list.pollFirst() != null) 17 ; 18 19//通过pollLast()来遍历LinkedList 20while(list.pollLast() != null) 21 ; 22 23//通过removeFirst()来遍历LinkedList 24try { 25 while(list.removeFirst() != null) 26 ; 27} catch (NoSuchElementException e) { 28} 29 30//通过removeLast()来遍历LinkedList 31try { 32 while(list.removeLast() != null) 33 ; 34} catch (NoSuchElementException e) { 35}LinkedList使用案例
1package LinkedListPackage; 2 3import java.util.Iterator; 4import java.util.LinkedList; 5 6public class LinkedListTest { 7 8 public static void main(String[] args) { 9 // TODO Auto-generated method stub 10 11 //创建一个数组链表对象list 12 LinkedList<String> list = new LinkedList<String>(); 13 14 //增加元素到list对象中 15 list.add("翟天临"); 16 list.add("秀丽的羊"); 17 list.add("和谐的钢铁侠"); 18 list.add("冷酷的香氛"); 19 list.add("rxdxlz"); 20 21 //显示数组链表中的内容 22 System.out.println("LinkedList包含如下元素"+list); 23 24 //替换元素 25 list.set(4, "完美的嚓茶"); 26 System.out.println("替换后的LinkedList包含如下元素"+list); 27 28 //检查元素的位置 29 int position = list.indexOf("秀丽的羊"); 30 System.out.println("秀丽的羊在LinkedList中的位置是:"+position); 31 32 //获取链表的大小 33 int size = list.size(); 34 System.out.println("LinkedList链表的大小为："+size); 35 36 //遍历ArrayList中所有的元素 37 Iterator<String> it = list.iterator(); 38 System.out.println("使用iterator遍历LinkedList中所有元素"); 39 for(;it.hasNext();){ 40 System.out.println("LinkedList元素包括 "+it.next()); 41 } 42 } 43}输出结果与图6一致。
4. ArrayList和LinkedList的区别
ArrayList和LinkedList的区别大致可以总结为：
ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。