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

学习一门语言我们基本都会用到数组和链表，那么这两种结构肯定是有各自的优缺点的，俗话说没有对比就没有伤害哈（），不管是一个什么东西都 是如此，接下来我就来分析分析他们各自的特点（没有分析到位的话不要见怪哈，请尽情下评论区留言，一起交流交流）

 

数组：我们知道不管是一维数组还是二维数组培训它们在内存里面的地址都 必须是连续的

优点：既然地址是连续的那么必然给我查找数据提供了极大的方便，让我们很容易的就能根据下标找到你需要的数据，提高了我们的效率

缺点：我们刚刚在它的优点中只讲到提高我们查找数据的效率，因为毕竟我们对数组的运用不只是查找数据，还有增加数据，插入数据，删除数据等一些操作；由于数组的特殊性，使得我们在进行这些操作的时候不能对其进行直接操作，还要重新开辟一个新的数组并使其长度增加来存放数据，这样的工作模式给我们带来了很大的不便，影响了效率

 

链表：链表的地址不是连续的，可以随意存放，删除等操作，通过引用来关联数据，链表可以分为单向的和双向的

优点：链表和数组的差别就在于链表在对数据进行插入和删除的时候可以不用开辟新的空间，只需要找到需要操作的结点就可以了，大大提高了人我们的效率

缺点：数组利于了查找，那链表就不利于查找咯

 

下面是我们上课的时候做的关于一个双向链表的练习

/**
 * 双向链表
 * @author Administrator
 *
 * @param <E>
 */
public class MyLinkList<E> {


	public Node<E>head=null;
	public Node<E>last=null;
	public int num=0;
	
	//增加数据
	public void add(E e){
		//创建一个新结点
		Node<E> node=new Node<E>(e);
		//判断链表中是否有结点，如果有就将node作为链表的最后一个结点
		if(last!=null){
			last.next=node;
			node.front=last;
			last=node;
		}//如果没 有那么node既是头结点也是尾结点
		else{
			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){
		Node<E> node=getNode(index);
		Node<E> n1=node.front;
		Node<E> n2=node.next;
		n1.next=n2;
		n2.front=n1;
		num--;
	}
	
	//根据内容删除数据
	public void delete(E e){
		int index=getIndex(e);
		delete(index);
		
	}
	
	//修改数据
	public void updata(int index, E e){
		Node<E> node=getNode(index);
		node.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++;
			//判断n所指向的结点的值是否和我们要找的那个值相等，相等退出，否则将n指向下一个结点
			if(n.data.equals(e)){
				break;
			}
			n=n.next;
		}
		return index;//返回找到的结点的下标
	}
	
	//根据下标确定结点
	private Node<E> getNode(int index){
		//定义一个变量为一个不存在的值
		int t=-1;
		//判断index是否在结点数据内
		if(index>=0&&index<num){
			//定义一个n指向头结点
			Node<E> n=head;
			//判断n所指向的结点的值是否为空
			while(n!=null){
				t++;
				//判断t是否和我们要查找的下标相等，如果相等就说明找到了我们要找的结点，就返回结点n
				//否则就将n指向它的下一个结点
				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 static void main(String[] args) {
		MyLinkList<String> list = new MyLinkList<String>();

		//增加数据
		list.add("aa");
		list.add("bb");
		list.add("cc");
		list.add("dd");
		list.add("ee");
		
		//插入数据
		list.insert(2,"nana");
		
		//修改数据
		list.updata(1, "tx");
		
		//根据下标删除数据
		list.delete(3);
		
		//根据内容删除数据
		list.delete("tx");
		
		//输出
		for(int i=0;i<list.size();i++){
			String s=list.get(i);
			System.out.println(s);
		}
	}