数组与链表的区别

数组与链表都是数据结构，并且都是存储特定数据类型。

数组存储的特点：存储的内存地址是连续的。
优点：数据是存放在一个连续的内存地址的上，查找效率比较高。
缺点：在改变数据个数的时候[增加、插入、删除]效率较低。

链式结构的存储特点：[链表]数据在内存中可以在任意位置，通过引用来关联数据。
优点：链表是将每个对象存放在独立的结点中（每个结点还存放着下一个结点的引用），插入与删除的效率较高。
缺点：查找元素以及收索元素的效率较低。

数据结构一般都要实现存放、取出、删除、修改、数量这几个操作，所以下面就用实例来真正的了解一下数组链表的区别

/**
 * 自定义长度可变的数组[泛型]
 * 
 * @author Administrator
 * 
 */
public class MyArray<E> {

	// 定义一个长度为0的初始数组
	private Object[] src = new Object[0];

	/**
	 * 存放数据
	 * 
	 * @param s
	 *            要存放的数据
	 */
	public void add(E s) {
		// 定义一个新数组长度是源数组长度+1
		Object[] dest = new Object[src.length + 1];
		// 将原数组的数据拷贝到新数组中
		System.arraycopy(src, 0, dest, 0, src.length);
		// 将新数据放到新数组的最后一个位置
		dest[dest.length - 1] = s;
		// 将原数组指向新数组
		src = dest;

	}

	/**
	 * 取出数据
	 * 
	 * @param index
	 *            要取出的数据的下标
	 */
	public E get(int index) {
		Object s = src[index];
		return (E)s;
	}

	/**
	 * 根据下标删除数据
	 * 
	 * @param index
	 *            要删除的数据的下标
	 */
	public void delete(int index) {
		Object[] dest = new Object[src.length-1];
		//将下标小于index的拷贝到新数组对应的下标位置
		System.arraycopy(src, 0, dest, 0, index);
		
		//将下标大于index的拷贝到新数组下标的位置为原数组的下标位置-1
		System.arraycopy(src, index+1, dest, index, src.length-index-1);
		//将src指向新数组
		src=dest;
	}

	/**
	 * 删除指定的数据
	 * 
	 * @param s
	 *            要删除的数据，如果有重复的数据，就删除下标最小的
	 */
	public void delete(E s) {
		int t=-1;
		for(int i=0;i<src.length;i++){
			if(src[i].equals(s)){
				t=i;
				break;
			}
		}
		//如果s在数组中出现过，t一定会>=0
		if(t>=0){
			delete(t);
		}
	}

	/**
	 * 将数据插入到指定位置
	 * @param index 要插入的位置
	 * @param s 要插入的数据
	 */
	public void insert(int index,E s){
		Object[] dest = new Object[src.length+1];
		//将新数据放到新数组的指定位置
		dest[index]=s;
		
		//将下标小于index的数据拷贝到新数组对应的下标位置
		System.arraycopy(src, 0, dest, 0, index);
		//将下标>=index的数据宝贝到新数组下标+1的位置
		System.arraycopy(src, index, dest, index+1, src.length-index);
		
		src=dest;
		
	}
	
	/**
	 * 修改数据
	 * 
	 * @param index
	 *            要修改的数据的下标
	 * @param s
	 *            修改后的数据
	 */
	public void update(int index, E s) {
		src[index] = s;
	}

	/**
	 * 获得数据个数
	 */
	public int size() {
		return src.length;
	}
}

/**
 * 自定义链表类【双向链表】
 * @author Administrator
 *
 */
public class MyLinkList<E> {
	//初始状态下，链表没有任何结点，头结点为null
	private Node<E> head = null;
	//初始状态下，链表没有任何结点，尾结点为null
	private Node<E> last = null;
	private int num=0;//数据个数
	
	//增加数据
	public void add(E e){
		//根据数据创建结点对象
		Node<E> node = new Node<E>(e);
		//如果链表中已经有结点， 就将node作为last的下一个结点
		if(last!=null){
			last.next = node;
			node.front=last;
			last = node;
		}else{
			//如果链表中还没有结点，node就是第一个结点。既是头结点，又是尾结点
			head = node;
			last = node;
		}
		num++;
	}
	
	
	//插入结点
	public void insert(int index,E e){
		//创建新结点
		Node<E> node = new Node<E>(e);
		//找到index位置的结点
		Node<E> n1 = getNode(index);
		//找到n1的前一个结点
		Node <E> n2 = n1.front;
		
		//找到结点之后实现“插入”这个具体步骤
		n2.next=node;
		node.front=n2;
		node.next=n1;
		n1.front=node;
		
		//插入数值之后，结点的长度会增加。
		num++;
	}
	
	//根据'下标'删除结点
	public void delete(int index){
		//找到index位置的结点
		Node<E> n1 = getNode(index);
		//找到n1的前一个结点,以及n1的后一个结点
		Node <E> n2 = n1.front;
		Node <E> n3 = n1.next;
		n2.next=n3;
		n3.front=n2;
		num--;
	}
	
	
	//修改结点
	public void update(int index,E e){
		Node<E> n1 = getNode(index);
		n1.data =e;
	}
	
	//输出结点
	public E get(int index){
		Node<E> node = getNode(index);
		return node.data;
	}
	
	//根据下标确定结点
	private Node<E> getNode(int index){
		int t =  -1;
		if(index >= 0&& index <num){
			Node<E> n = head;
			
			while(n!=null){
				t++;
				if(t==index){
					break;
				}
				n = n.next;
			}
			return n;
		}else{
			//抛出异常
			throw new IndexOutOfBoundsException("下标超出边界！  index："+index+",size:"+num);
		}
	}
		
	//结点的长度
	public int size(){
		return num;
	}	
}


//内部结点类，主要是为MyLinkList类服务  （如果放置在MyLinkList类里面，可以定义为私有的，放在外面，还可以为这个包去使用）
class Node<E> {
	//节点的数据
	E data;
	//对下一个结点的引用
	Node<E> next;
	//对前一个结点的引用
	Node<E> front;
	
	//创建结点对象的时候必须制定数据
	public Node(E e){
		data = e;
	}

}