数据结构之表结构【数组，链表的实现方式】（数据结构读后感 一）

最近除了在看Java虚拟机外，我还在学习数据结构与算法分析（Java语言），这是因为前段时间去公司面试的时候被问到一些数据结构和算法都有点不知所措，程序不就是=数据结构+算法吗，我想要作为一名合格的程序员，所以我准备啃下这本书，不管再难都得啃下，人生不亦如此吗。嘻嘻，我是一个打不倒的元气妹

首先要学习的是最简单和最基本的三种数据结构：表，栈和队列。每一个有意义的程序都将显示的至少使用一种这样的数据结构。今天我要记录的是学习 表 结构。

抽象数据类型（abstract data type,ADT）是带有一组操作的一些对象的集合，以及我们接下来要讨论的表，栈，队列都是一种ADT结构。

诸如表，集合，图以及与他们各自的操作一起形成的这些对象都可以被看做是抽象数据类型，这是一种什么样的概念呢？就好比我们说整数，实数和布尔数是数据类型一样，当然他们都有自己对应的一系列操作，抽象数据类型（ADT）也一样，就拿集合ADT来说，可以有添加（add），删除（delete），以及包含（contain）这样的一些操作。Java类考虑到了ADT的实现，但是隐藏了一些细节，如果我们在程序中需要对ADT进行一些操作，就可以调用一些合适的方法来执行，当他们被正确执行或实现之后，使用他们的程序却没有必要知道他们是如何实现的。

表ADT：

形如A0，A1，A2，A3...An-1,An的一般的表，说这个表的大小是N，将大小为0的表称为空表。

在表ADT上进行的操作有：printList和makeEmpty，find：返回某一项首次出现的位置；findKth：返回某个位置上的元素；insert（x，b）：在位置b上插入x元素；remove（a）：移除a元素；

以上举的一系列操作都可以通过数组来实现，只是存在一个效率问题；

我们需要知道的是：数组虽然是固定容量的，但是在需要的时候也可以用双倍的容量创建一个不同的数组，下面是解释数组arr在必要的时候如何被扩展的，其初始容量为10：

package ADT;

//测试对数组扩容
public class ArrayTest {
	public static void main(String[] args) {
		
		int[] arr = new int[10];
		System.out.println(arr.length);//10
		//..
		//下面我们对数组arr进行扩容
		int[] newArr = new int[arr.length*2];
		for (int i = 0; i < arr.length; i++) {
			newArr[i] = arr[i];
		}
		arr = newArr;
		System.out.println(arr.length);//20
	}
}

最坏的情况下：在位置0的插入（在表前端插入）和删除第一个元素（在表前端删除）都需要移动表中的所有元素，则最坏情况花费时间O(N);

最坏的情况下：在最后插入（在表的末尾插入）和在表末尾插入都不需要移动表的元素，则最好的情况下花费时间O（1）；

所以，对于不同的操作，我们选择不同的数据结构：

当在表末尾（高端）进行插入操作，其后做的最多的是对数组的访问，我们选择数组来做表的实现；

当经常对表做一些插入和删除操作，特别是在表前端进行，那么数组效率不高，我们选择链表作为表的适合实现。

简单链表：

为了执行printList或find（x）只需要从表的第一个节点开始然后用一些后继的next链遍历该表即可，其中findKth()没有数组的执行效率高， 但是remove()可以直接修改一个next链来实现，插入insert()使用new操作符创建一个新的节点，然后两次修改next引用，效率较数组实现会更高。典型的链表拥有到该表两端的链，删除最后一项时，要先找到指向最后节点的项，把它的next改为null。

Java Collections API 中的表：

Collection接口：位于java.util包中，集合的概念在Collection接口中变得抽象，存储一组类型相同的对象，下面是Collection接口中常用的方法：

public interface Collection<AnyType> extends Iterable<AnyType>{
	
	int size();
	boolean isEmpty();
	void clear();
	boolean contains(AnyType x);
	boolean add(AnyType x);
	boolean remove(AnyType x);
	java.util.Iterator<AnyType> iterator();
}

Collection接口扩展了Iterable接口，实现了Iterable接口的类可以拥有增强for循环就，如下：

//实现了Iterable接口的类可以使用增强for循环
	public static <AnyType> void print(Collection<AnyType>  coll){
		for (AnyType item : coll) {
			System.out.println(item);
		}
	}
	
	//上面的增强for循环代码等价于此段代码
	public static <AnyType> void print(Collection<AnyType> coll){
		Iterator<AnyType> itr = coll.iterator();
		while(itr.hasNext()){
			AnyType item = itr.next();
			System.out.println(item);
		}
	}

Iterator接口：

实现了Iterable接口的类必须实现iterator()方法获得一个Iterator对象，如上代码，不同的集合会得到不同的Iterator对象，Iterator是一个在java.util包下的接口，如下：

public interface Iterator<AnyType>{
	boolean hasNext();
	AnyType next();
	void remove();
}

对于Iterator接口，因为他的现有方法有限，所以很难使用Iterator做简单遍历Collection以外的任何工作，还有一个点需要注意的是，Iterator接口有一个remove方法，一般我们都使用Iterator接口的remove方法而不用Collection的remove，主要原因有两点：

1. Collection的remove方法必须找出要被删除的项(意味着，就算已经知道了要删除项的准确位置，还是需要再去遍历一遍)

2.如果对正在迭代的集合进行结构上的改变，如（增，删），如果这个时候使用Collection的remove方法，则会报异常（ConcurrentModificationException）

List接口，ArrayList类和 edList类：

我们要学的是最大的集合就是表（list），它由java.util包中的List接口所指定，List接口继承了Collection接口，因此它包含了Collection接口的所有方法和一些他自己的方法：

public interface List<AnyType> extends Collection<AnyType>{
	AnyType get(int index);
	AnyType set(int index,AnyType newVal);
	void add(int index,AnyType x);;
	void remove(int index);
	
	ListIterator<AnyType> listIterator(int pos);
}

List ADT有两种流行的实现方式：ArrayList和 edList；

ArrayList提供了List ADT的一种可增长数组的实现，他的优点是便于查询，get和set方法花费的时间为常数，而缺点是不便insert和delete；

edLis提供了List ADT的双链表实现，他的优点在于假设变动项的位置已知，则他的新增和删除开销很小，在表的前端进行添加和删除所花费的时间都是常数的，但是对get的调用花销很大，除非调用的是接近表末尾的数据，这样可以从表的末尾开始遍历。

所以可以做个总结：

在表的前端进行添加， edList花费的时间为O(N),而ArrayList花费的时间为O(N的平方);

在表的末尾进行添加， edList和ArrayList所花费的时间都是O(N);

在表的前端进行查找，ArrayList花费的时间为O(N),而 edList花费的时间为O（N的平方），但是 如果是使用的增强for循环，则不论是哪一种List，所花费的时间都为O(N);

在这篇文章的结尾有一个例子：

如果表包含有6,5,1,4,2，则在该方法被调用之后，表中仅有5，1，也就是说，我们要写一个删除表中偶数的方法；

思路一：我们首先淘汰ArrayList，因为他对于删除这个操作效率并不高，所以我们考虑用 edList，但需要知道是， edList的get方法效率并不高，如下：

思路二：不是用get，而是用迭代器一步步遍历，当找到我们需要删除的元素时，就使用Collection的remove方法来删除，但是这个方法是行不通的，会报异常：

思路三：在迭代器找到一个偶数值时，用迭代器来删除这个值，但是这个对于 edList是可用的，效率也高，但是对于ArrayList而言，其remove方法仍然是昂贵的，因为它仍然需要移动。

public static void main(String[] args) {
		System.out.println(\"第一种开始\"+getDateTimeIN());
		List<Integer> list = new  edList<Integer>();
		list.add(6);
		list.add(5);
		list.add(1);
		list.add(4);
		list.add(2);
		//测试第一种
		//removeEvensVer1(list);
		
		
		 //第一种的结果如下：
		 /* 第一种开始2018/12/20-15:39:41:872
			删除完毕
			第一种结束2018/12/20-15:39:41:881
		 */
		//测试第三种
		removeEvensVer3(list);
		System.out.println(\"第一种结束\"+getDateTimeIN());
		//第三种结果
	
		/*  第一种开始2018/12/20-15:41:23:756
			删除完毕
			第一种结束2018/12/20-15:41:23:763
		 */

	}
	/**
	 * 第一种，利用 edList
	 * @param list
	 */
	public static void removeEvensVer1(List<Integer> list){
		int i = 0;
		while(i<list.size()){
			if(list.get(i)%2 == 0){
				list.remove(i);
			}else{
				i++;
			}
		}
		System.out.println(\"删除完毕\");
	}
	
	/**
	 * 第二种
	 * @return
	 */
	public static void removeEvensVer2(List<Integer> list){
		for (Integer item : list) {
			if(item % 2 == 0){
				list.remove(item);//抛出异常
			}
		}
	}
	
	/**
	 * 第三种
	 * @return
	 */
	public static void removeEvensVer3(List<Integer> list){
		Iterator<Integer> itr = list.iterator();
		while(itr.hasNext()){
			if(itr.next() % 2 == 0){
				itr.remove();
			}
		}
		System.out.println(\"删除完毕\");
	}
	
	public static String getDateTimeIN(){
		{
	         
	        Calendar Cld = Calendar.getInstance();
	        int YY = Cld.get(Calendar.YEAR) ;
	        int MM = Cld.get(Calendar.MONTH)+1;
	        int DD = Cld.get(Calendar.DATE);
	        int HH = Cld.get(Calendar.HOUR_OF_DAY);
	        int mm = Cld.get(Calendar.MINUTE);
	        int SS = Cld.get(Calendar.SECOND);
	        int MI = Cld.get(Calendar.MILLISECOND);   
	        //由整型而来,因此格式不加0,如  2016/5/5-1:1:32:694
	        //func2
	        Calendar cal = Calendar.getInstance();
	        Date date = cal.getTime();
	        return new SimpleDateFormat(\"yyyy/MM/dd-HH:mm:ss:SSS\").format(date);
	    }
	}

,