Java 数组和链表的区别以及使用场景

  数组：是将元素在内存中连续存储的；它的优点：因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高；它的缺点：在存储之前，我们需要申请一块连续的内存空间，并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，当数据两比较大的时候，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间。在改变数据个数时，增加、插入、删除数据效率比较低。

  链表：是动态申请内存空间，不需要像数组需要提前申请好内存的大小，链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置，通过应用来关联数据（就是通过存在元素的指针来联系）。

  数组和链表就拿增加数据来说，数组中增加一个元素，需要移动大量的元素，在内存中空出一个元素的空间，然后将增加的元素放到空出的空间中；而链表就是将链表中最后的一个元素的指针指向新增的元素，在指出新增元素是尾元素就好了。

数组应用场景：
1、数据比较少；
2、经常做的运算是按序号访问数据元素；
3、数组更容易实现，任何高级语言都支持；
4、构建的线性表较稳定。

/**
 * 自定义长度可变的数组[存放字符串]
 * @author Administrator
 */

public class my {
	
		// 定义一个长度为0的初始数组
		private String[] src = new String[0];

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

		}

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

		/**
		 * 根据下标删除数据
		 * @param index要删除的数据的下标
		 */
		public void delete(int index) {
			String[] dest=new String[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(String s) {
			int t=-1;
			for(int i=0;i<src.length;i++){
				if(s.equals(src[i])){
					t=i;
					break;
				}
			}
			//如果s在数组中出现过，t一定是大于等于0的
			if(t>=0){
			  delete(t);
			}
		
		}

		/**
		 * 将数据插入到指定位置
		 * @param index 要插入的位置
		 * @param s 要插入的数据
		 */
		public void insert(int index,String s){
			String[] dest = new String[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, String s) {
			src[index] = s;
		}

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


}

/**
 * 自定义长度可变数组的测试类
 * 
 * @author Administrator
 * 
 */
	public static void main(String[] args) {
		// 创建数组对象
		my arr = new my();
		// 增加数据
		arr.add("AA");
		arr.add("BB");
		arr.add("CC");
		arr.add("DD");
		arr.add("EE");
		arr.add("FF");
		
		//根据下标删除数据
		arr.delete(3);
		//删除指定的数据
		arr.delete("BB");
		//将数据插入到指定位置
		arr.insert(0,"on");
		//修改数据
		arr.update(2, "up");
		//获得数据个数
		arr.size();
		// 取出数据
		for (int i = 0; i < arr.size(); i++) {
			String s = arr.get(i);
			System.out.println(s);
		}
	}
}
//结果
// on
// AA
// up
// EE
// FF

链表应用场景：
1、对线性表的长度或者规模难以估计；
2、可以频繁做插入删除操作；
3、构建动态性比较强的线性表。

/**
 * 自定义链表类【双向链表】
 * 
 * @author Administrator
 * 
 */
public class MyLinkList<E> {

	// 初始状态下，链表没有任何结点，头结点为null,尾结点为null
	private Node<E> head = 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) {

	}

	public void delete(E e) {

	}

	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 int getIndex(E e){
		int index=-1;
		Node<E> n = head;
		while(n!=null){
			index++;
			if(n.data.equals(e)){
				break;
			}
			n=n.next;
		}
		return index;
	}
	
	public int getIndex2(E e){
		for(int i=0;i<num;i++){
			E e2 = get(i);
			if(e2.equals(e)){
				return i;
			}
		}
		return -1;
		
	}
	
	//根据下标确定结点
	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类服务
class Node<E> {
	// 结点的数据
	E data;
	// 对下一个结点的引用
	Node<E> next;
	// 对前一个结点的引用
	Node<E> front;

	// 创建结点对象的时候必须指定数据
	public Node(E e) {
		data = e;
	}

}

public class Main {
	public static void main(String[] args){
		myLinkList<String> mm=new myLinkList<String>();
		mm.add("AA");
		mm.add("BB");
		mm.add("CC");
		mm.add("DD");
		mm.add("EE");
		
		mm.insert(2,"链");
		mm.update(3, "表");
		for(int i=0;i<mm.size();i++){
			String s=mm.get(i);
			System.out.println(s);
			
		}
	}
}
//结果
// AA
// BB
// 链
// 表
// DD
// EE