数组和链表的比较以及队列的两种方式实现

1、定义  

  数组又叫做顺序表，顺序表是在内存中开辟一段连续的空间来存储数据，数组可以处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。

　链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。链表是靠指针来连接多块不连续的的空间，在逻辑上形成一片连续的空间来存储数据。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。

2、二者区分：　

　A 从逻辑结构来看

　　A-1. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。

　　A-2. 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

    B 从内存存储来看

　　B-1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小

　　B-2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦.

       数组在内存中开辟连续的一块区域，如果一个数据要两个内存单元，一组5个数据10个单元就够了，无需标记其地址，因为数组定义时候标顶了第一个原始的地址，其他四个都知道了。

       链表可可以是连续的，也可以是不连续的，但一般都是不连续的，一链5个数据，如果每个数据本身用2个内存单元，那么10个单元是不够的，因为每个数据都要表示出下个数据在哪里，所以一个数据本身用2个单元，再用1个单元表示此链下一个数据在什么地址。

　C从访问顺序来看　

       数组中的数据在内存中的按顺序存储的，而链表是随机存储的！

　　C-1.要访问数组中的元素可以按下标索引来访问，速度比较快，如果对他进行插入操作的话，就得移动很多元素，所以对数组进行插入操作效率很低！

　　C-2.由于链表表是随机存储的，链表在插入，删除操作上有很高的效率（相对数组），如果要访问链表中的某个元素的话，那就得从链表的头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问的效率就比数组要低

 

3、分别用数组和链表实现队列：

    3-1数组实现

public class Queue <E>{
    
	//每次放入队列的元素的个数
	private int initLen=0;
	//每次增长的队列空间的大小
	private int increaseLen=0;
	private Object[] src;
	//己放入对象的个数
	private int count=0;
	
	public Queue(int initLen,int increaseLen){
		this.initLen=initLen;
		this.increaseLen=increaseLen;
		src = new Object[initLen];
	}
	
	public Queue(int initLen){
		this(initLen,initLen/2);
	}
	
	public Queue(){
		this(20,10);
	}
	
	
	/**
	 * 在末尾向队列中增加一个字符串
	 * @param s:向队列中增加的字符串 
	 */
	public void add(E e){
		src[count]=e;
		count++;
		if(count>=initLen){
			//新建数组，是原数组长度的length+1
			Object[] temp=new Object[src.length +increaseLen];
			//将原数组中的复制到新数组中
			for(int i=0;i<count;i++)
			{
				temp[i]=src[i];
			}
			src=temp;	
		}
		
	}
	/**
	 * 在指定位置向队列中增加一个字符串s
	 * @param s 向队列中增加的字符串
	 * @param index 队列中指定的位置
	 */
	public  void add(E e,int index){
		if(count>=initLen){
			//新建数组，是原数组长度的length+increaseLen
			Object[] temp=new Object[src.length +increaseLen];
			//将原数组中的复制到新数组中
			for(int i=0;i<count;i++)
			{
				temp[i]=src[i];
			}
			//新数组赋值给原数组
			src=temp;	
		}
		//将原数组从index处的元素向后以一位
		for(int i=count;i>index;i--)
		{
			src[i]=src[i-1];
		}
		//将s添加到新数组中指定位置
		src[index]=e;
	
	}
	
	/**
	 * 得到队列中指定位置的字符串
	 * @param index 队列中指定的位置
	 * @return 返回指定位置的字符串
	 */
	public E get(int index){
		if(index>=0&&index<=count){
		   return (E)src[index];
		   }
		else return null;
	}
	
	/**
	 * 返回当前字符串的位置
	 * @param s当前字符串
	 * @return 当前字符串的位置
	 */
	public int getPos(E e){
		 int temp=-1;
		for(int i=0;i<count;i++){
			if(e.equals(src[i])){
				temp=i;
		        break;
			}
		
		}
		//System.out.println("位置是："+temp);
		if(temp==-1)
		 System.out.println("队列中没有与  \""+e+"\" 匹配的字符串！");
		return temp;
	}
	
	/**
	 * 得到队列中字符串的长度即大小
	 * @return 返回的是字符串的大小
	 */
	public int size(){
		return count;
	}
	 
	/**
	 * 删除队列中指定位置的字符串
	 * @param index 要删除字符串的位置
	 * @return 返回锁删除的字符串
	 */
	public E delete(int index){
		//System.out.println("字符串的长度为"+src.length);
		//新建数组，是原数组长度的length+1
		Object[] temp=new Object[count-1];
		E e;
		//将原数组index前的元素复制到新数组中
		for(int i=0;i<index;i++)
		{
			temp[i]=src[i];
		}
		e=(E)src[index];
		//将原数组index后的元素复制到新数组中
		for(int i=index+1;i<count;i++)
		{
			temp[i-1]=src[i];
		}
		//新数组赋值给原数组
		src=temp;
		count--;
		//System.out.println("字符串的长度为"+src.length);
		return e;
	}
	
	/**
	 * 删除指定的字符串
	 * @param s要删除的字符串
	 * @return TRUE删除成功 FALSE删除失败
	 */
	public Boolean delete(E e){
		 int temp=-1;
			for(int i=0;i<count;i++){
				if(e.equals(src[i])){
					temp=1;
			        break;
				}
			}
			if(temp!=-1)return true;
			return false;
	}
	
	/**
	 * 替换队列中指定位置的字符串
	 * @param s新的字符串
	 * @param index要更新字符串的位置
	 * @return
	 */
	public Boolean replace(E e,int index){
        if(index>count){
        	System.out.println("长度超出！！");
        	return false;
        	}
		E temp;
		temp=(E)src[index];
		src[index]=e;
		e=temp;
		return true;
	}
	
}

 　3-2链表实现

 

public class Node<E> {
	public E Elem;
	public Node<E> next;
	public Node(E elem){
		Elem=elem;
	}
	public String toString(){
		return Elem.toString();
	}
}

public class LinkQueueDemo <E>{
	    
    public Node head=null;
    public Node tail=null;
	/**
		* 在末尾向队列中增加一个节点
		* @param s:向队列中增加的字符串 
		*/
	public void add(E elem){
		if(head==null){
			head=new Node(elem);
            tail=head;
		}else{
			tail.next=new Node(elem);
            tail=tail.next;	   
		}
		//System.out.println("插入的Node是："+elem);
	}
	
		/**
		 * 得到队列中指定位置的字符串
		 * @param index 队列中指定的位置
		 * @return 返回指定位置的字符串
		 */
		public Node get(int index){
		    Node temp=head;
		    int count=0;
		    if(index>this.size()){
		    	System.out.println("index is out of the size:"+this.size());
		    	return null;
		    }else if(temp==null){
		    	System.out.println("queue is empty;");
		    	return null;
		    }else{
		    	 while(count!=index){
		    		 count++;
		    		 temp=temp.next;
		    	 }
		         return  temp;
		     }
		     
		}
		
		/**
		 * 返回当前节点的位置
		 * @param s当前字符串
		 * @return 当前字符串的位置
		 */
		public int getPos(E e){
			Node temp=head;
			Node query_Node=new Node(e);
		    int count=0;
		   if(temp==null){
		    	System.out.println("queue is empty;");
		    	return -1;
		    }else{
		    	 while(temp.Elem!=query_Node.Elem&&temp.next!=null){
		    		 count++;
		    		 temp=temp.next;
		    	 }
		    	 if(temp.next==null){
		    		 System.out.println("there is no such Node");
		    		 return -1;
		    	 }
		    		
		         return count;
		     }
		}
		
		/**
		 * 得到队列中字符串的长度即大小
		 * @return 返回的是字符串的大小
		 */
		public int size(){
			int len=0;
			Node temp=head;
			if(head==null)
				return 0;
		    while(temp!=null){
		    	len++;
		    	temp=temp.next;
		    }
	         return len;
		}
		 
		/**
		 * 删除队列中指定位置的字符串
		 * @param index 要删除字符串的位置
		 * @return 返回锁删除的字符串
		 */
		public Node delete(int index){
			Node temp=head;
			Node pretem=temp;
		    int count=0;
		    if(index>this.size()){
		    	System.out.println("index is out of the size:"+this.size());
		    	return null;
		    }else if(temp==null){
		    	System.out.println("queue is empty;");
		    	return null;
		    }else{
		    	 while(count!=index){
		    		 count++;
		    		 pretem=temp;
		    		 temp=temp.next;
		    	 }
		         pretem.next=temp.next;
		     }
			return temp;
		}
		
		/**
		 * 删除队列中第一个Node
		 * @return 返回锁删除的node 
		 */
		public Node delete(){
			Node temp=head;
			if(temp==null){
				System.out.println("the queue is empty!");
				return null;
			}else{
			    if(head.next!=null){
			    	head=head.next;
			    }	
			    else{
			    	head=null;
			    }
			    return temp;
			}
		}
		
		/**
		 * 删除指定的字符串
		 * @param s要删除的字符串
		 * @return TRUE删除成功 FALSE删除失败
		 */
		public Boolean delete(E e){
			
				return false;
		}
		
		/**
		 * 替换队列中指定位置的字符串
		 * @param s新的字符串
		 * @param index要更新字符串的位置
		 * @return
		 */
		public Boolean update(E e,int index){
			Node temp=head;
		    int count=0;
		    if(index>this.size()){
		    	System.out.println("index is out of the size:"+this.size());
		    	return false;
		    }else if(temp==null){
		    	System.out.println("queue is empty;");
		    	return false;
		    }else{
		    	 while(count!=index){
		    		 count++;
		    		 temp=temp.next;
		    	 }
		         temp.Elem=e;
		     }
			return true;
		} 
		
		public void printQueue(){
			Node temp=head;
			int count=0;
			while(temp!=null){
				System.out.println(count+":"+temp+" ");
				temp=temp.next;
			    count++;
			}
		}
}

 

 

<!--EndFragment-->

评论

2 楼 freewxy 2010-11-19  

引用

你的想法很好，可以让用户自己决定开辟多少空间，也可以由我们自己决定开辟多少空间，我就没想到（惭愧啊！~）。但是我很好奇，为什么你要加上第一个构造函数呢？如果用户输入的需要增加的空间过大，会很浪费资源的。那个要增长的空间长度可以由我们自己定啊！~（个人见解）

嗯，确实，这点我没有考虑到，这个内部定义会更好一些

1 楼 吸血鬼猎人 2010-11-19  

 public Queue(int initLen,int increaseLen){   
12.        this.initLen=initLen;   
13.        this.increaseLen=increaseLen;   
14.        src = new Object[initLen];   
15.    }   
16.       
17.    public Queue(int initLen){   
18.        this(initLen,initLen/2);   
19.    }   

       public Queue(){   
22.        this(20,10);   
23.    }   

你的想法很好，可以让用户自己决定开辟多少空间，也可以由我们自己决定开辟多少空间，我就没想到（惭愧啊！~）。但是我很好奇，为什么你要加上第一个构造函数呢？如果用户输入的需要增加的空间过大，会很浪费资源的。那个要增长的空间长度可以由我们自己定啊！~（个人见解）