杂谈基本数据结构--"线性表":
　　表结构是一种基本的数据结构，常见的实现是数组，几乎在每个程序每一种开发语言中都提供了数组这个顺序存储的线性表结构实现.
　　什么是线性表?
　　由0个或多个数据元素组成的有限序列.如果没有元素，称为空表，如果存在多个元素，则第一个元素无前驱，后一个元素无后继，其他元素元素都有且只有一个前驱和后继.
　　ArrayList和LinkedList
　　ArrayList和LinkedList是顺序存储结构和链式存储结构的表在java语言中的实现.
　　ArrayList提供了一种可增长数组的实现，使用ArrayList，因为内部使用数组实现，所以，它的优点是，对于get和set操作调用花费常数时间.缺点是插入元素和删除元素会付出昂贵的代价.因为这个操作会导致后面的元素都要发生变动，除非操作发生在集合的末端.
　　鉴于这个缺点，如果需要对表结构的前端频繁进行插入，删除操作，那么数组不是一个好的实现，为此需要使用另一种结构，链表，而LinkedList是基于一种双链表的实现，使用它的优点是，对于元素的插入，删除操作开销比较小，无论是在表的前端还是后端.但是缺点也显而易见，对于get操作，它需要从表的一端一个一个的进行查找，因此对get的调用花费的代价也是很昂贵的.
　　理解这两个集合好的方式是自己去实现它，下面我们通过代码来实现自己的arrayList和LinkedList.
　　实现ArrayList
　　通过拜读java中ArrayList的源码可以发现，其实实现一个ArrayList并不难，借鉴源码，我们也可以写出一个简易版的ArrayList集合表结构.
　　MyArrayList:
package com.wang.list;
import java.util.Iterator;
public class MyArrayList<T> implements Iterable<T> {
//初始化集合的容量
private static final int DEFAULT_CAPACITY=10;
//当前元素的个数
private int theSize;
//使用一个数组来实现这个List
private T [] theItems;
public MyArrayList(){
clear();
}
//清空集合元素，初始化时使用
public void clear(){
theSize=0;
ensureCapacity(DEFAULT_CAPACITY);
}
//通过传入的int值大小决定是否需要扩充集合空间大小
public void ensureCapacity(int newCapacity) {
if(newCapacity<theSize)
return;
T[] old=theItems;
theItems=(T[]) new Object[newCapacity];
for(int i=0;i<size();i++){
theItems[i]=old[i];
}
}
//返回当前集合元素的个数
public int size() {
return theSize;
}
//返回当前集合是否为空
public boolean isEmpty(){
return size()==0;
}
public void trimToSize(){
ensureCapacity(size());
}
//获取指定索引下的元素值
public T get(int index){
if(index<0||index>=size())
throw new ArrayIndexOutOfBoundsException("索引越界");
return theItems[index];
}
//修改指定索引上的元素值
public T set(int index，T value){
if(index<0||index>=size())
throw new ArrayIndexOutOfBoundsException("索引越界");
T old=theItems[index];
theItems[index]=value;
return old;
}
//添加元素，直接指定元素，默认添加在数组末尾
public boolean add(T value){
add(size()，value);
return true;
}
//添加元素，指定添加位置和元素值
public void add(int index， T value) {
//如果数组元素个数已经达到指定size();那么扩展该数组，使数组容量加倍
if(theItems.length==size()){
ensureCapacity(size()*2+1);
}
//从末尾元素向前遍历，一直到index处，使index处之后的所有元素向后移动一位
for(int i=theSize;i>index;i--){
theItems[i]=theItems[i-1];
}
theItems[index]=value;
//添加完元素，是集合元素个数加一
theSize++;
}
//移除指定索引处的元素值，
public T remove(int index){
T val=theItems[index];
for(int i=index;i<size()-1;i++){
theItems[i]=theItems[i+1];
}
theSize--;
return val;
}
//重写迭代器的方法，使用下面的静态内部类实现，注意static，如果没有该关键字，会使内部类访问不到外部的成员
@Override
public Iterator<T> iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements java.util.Iterator<T>{
private int current=0;
@Override
public boolean hasNext() {
return current<size();
}
@Override
public T next() {
return theItems[current++];
}
@Override
public void remove() {
MyArrayList.this.remove(--current);
}
}
}