线性表分析及Java实现

      数据结构中的线性表，对应着Collection中的List接口。

      在本节中，我们将做以下三件事

            第一。我们先来看看线性表的特征

            第二，自己用JAVA实现List

            第三，对比的线性表、链式表性能，以及自己的List性能与JDKList性能对比

 

      线性表特征： 

            第一，一个特定的线性表，应该是用来存放特定的某一个类型的元素的（元素的“同一性”）

            第二， 除第一个元素外，其他每一个元素有且仅有一个直接前驱；除最后一个元素外，其他每一个元素有且仅有一个             直接后继（元素的“序偶性”）

            第二， 元素在线性表中的“下标”唯一地确定该元素在表中的相对位置（元素的“索引性”）

       又，一.线性表只是数据的一种逻辑结构，其具体存储结构可以为顺序存储结构和链式储存结构来完成，对应可以得到顺序表和链表，

            二.对线性表的入表和出表顺序做一定的限定，可以得到特殊的线性表，栈(FILO)和队列（FIFO）

 

 

    自己实现线性表之顺序表

             思路：

                1. 顺序表因为采用顺序存储形式，所以内部使用数组来存储数据

                2.因为存储的具体对象类型不一定，所以采用泛型操作

                3.数组操作优点：1.通过指针快速定位到下表，查询快速

                               缺点：1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据

                                        2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）

  具体实现代码如下

/**
 * 自己用数组实现的线性表
 */
public class ArrayList<E> {
	Object[] data = null;// 用来保存此队列中内容的数组
	int current;// 保存当前为第几个元素的指标
	int capacity;// 表示数组大小的指标
	 
	/**
	 * 如果初始化时，未声明大小，则默认为10
	 */
	public ArrayList() {
		this(10);
	}

	/**
	 * 初始化线性表，并且声明保存内容的数组大小
	 * @param initalSize
	 */
	public ArrayList(int initalSize) {
		if (initalSize < 0) {
			throw new RuntimeException("数组大小错误:" + initalSize);
		} else {
			this.data = new Object[initalSize];
			this.current = 0;
			capacity = initalSize;
		}
	}

	/**
	 * 添加元素的方法 添加前，先确认是否已经满了
	 * @param e
	 * @return
	 */
	public boolean add(E e) {
		ensureCapacity(current);// 确认容量
		this.data[current] = e;
		current++;
		return true;
	}

	/**
	 * 确认系统当前容量是否满足需要,如果满足，则不执行操作 如果不满足，增加容量
	 * @param cur 当前个数
	 */
	private void ensureCapacity(int cur) {
		if (cur == capacity) {
			// 如果达到容量极限，增加10的容量，复制当前数组
			this.capacity = this.capacity + 10;
			Object[] newdata = new Object[capacity];
			for (int i = 0; i < cur; i++) {
				newdata[i] = this.data[i];
			}
			this.data = newdata;
		}
	}

	/**
	 * 得到指定下标的数据
	 * @param index
	 * @return
	 */
	public E get(int index) {
		validateIndex(index);
		return (E) this.data[index];
	}
     
   /**
    * 返回当前队列大小
    * @return
    */
	public int size() {
		return this.current;
	}

	/**
	 * 更改指定下标元素的数据为e
	 * @param index 
	 * @param e
	 * @return
	 */
	public boolean set(int index, E e) {
		validateIndex(index);
		this.data[index] = e;
		return true;
	}
   
	/**
	 *  验证当前下标是否合法，如果不合法，抛出运行时异常
	 * @param index 下标
	 */
	private void validateIndex(int index) {
		if (index < 0 || index > current) {
			throw new RuntimeException("数组index错误：" + index);
		}
	}

	/**
	 * 在指定下标位置处插入数据e
	 * @param index 下标
	 * @param e 需要插入的数据
	 * @return 
	 */
	public boolean insert(int index, E e) {
		validateIndex(index);
		Object[] tem = new Object[capacity];// 用一个临时数组作为备份
		//开始备份数组
		for (int i = 0; i < current; i++) {
			if (i < index) {
				tem[i] = this.data[i];
			}else if(i==index){
				tem[i]=e;
			}else if(i>index){
				tem[i]=this.data[i-1];
			}
		}
		this.data=tem;
		return true;
	}


/**
	 * 删除指定下标出的数据
	 * @param index
	 * @return
	 */
	public boolean delete(int index){
		validateIndex(index);
		Object[] tem = new Object[capacity];// 用一个临时数组作为备份
		//开始备份数组
		for (int i = 0; i < current; i++) {
			if (i < index) {
				tem[i] = this.data[i];
			}else if(i==index){
				tem[i]=this.data[i+1];
			}else if(i>index){
				tem[i]=this.data[i+1];
			}
		}
		this.data=tem;
		return true;
	}

}

 

   自己实现线性表之链表

         思路：1.链表采用链式存储结构，在内部只需要将一个一个结点链接起来。（每个结点中有关于此结点下一个结点的引用）

         链表操作优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可

                     缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。

 

 

  实现代码如下

/**
 * 自己用链式存储实现的线性表
 */
public class LinkedList<E> {

	private Node<E> header = null;// 头结点
	int size = 0;// 表示数组大小的指标

	public LinkedList() {
		this.header = new Node<E>();
	}

	public boolean add(E e) {
		if (size == 0) {
			header.e = e;
		} else {
			// 根据需要添加的内容，封装为结点
			Node<E> newNode = new Node<E>(e);
			// 得到当前最后一个结点
			Node<E> last = getNode(size-1);
			// 在最后一个结点后加上新结点
			last.addNext(newNode);
		}
		size++;// 当前大小自增加1
		return true;
	}

	public boolean insert(int index, E e) {
		Node<E> newNode = new Node<E>(e);
		// 得到第N个结点
		Node<E> cNode = getNode(index);
		newNode.next = cNode.next;
		cNode.next = newNode;
		size++;
		return true;

	}

	/**
	 * 遍历当前链表，取得当前索引对应的元素
	 * 
	 * @return
	 */
	private Node<E> getNode(int index) {
		// 先判断索引正确性
		if (index > size || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		}
		Node<E> tem = new Node<E>();
		tem = header;
		int count = 0;
		while (count != index) {
			tem = tem.next;
			count++;
		}
		return tem;
	}

	/**
	 * 根据索引，取得该索引下的数据
	 * 
	 * @param index
	 * @return
	 */
	public E get(int index) {
		// 先判断索引正确性
		if (index >= size || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		}
		Node<E> tem = new Node<E>();
		tem = header;
		int count = 0;
		while (count != index) {
			tem = tem.next;
			count++;
		}
		E e = tem.e;
		return e;
	}

	public int size() {
		return size;
	}

	/**
	 * 设置第N个结点的值
	 * 
	 * @param x
	 * @param e
	 * @return
	 */
	public boolean set(int index, E e) {
		// 先判断索引正确性
		if (index > size || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		}
		Node<E> newNode = new Node<E>(e);
		// 得到第x个结点
		Node<E> cNode = getNode(index);
		cNode.e = e;
		return true;
	}

	/**
	 * 用来存放数据的结点型内部类
	 */
	class Node<e> {
		private E e;// 结点中存放的数据

		Node() {
		}

		Node(E e) {
			this.e = e;
		}

		Node<E> next;// 用来指向该结点的下一个结点

		// 在此结点后加一个结点
		void addNext(Node<E> node) {
			next = node;
		}
	}

}

 

自己实现线性表之栈

         栈是限定仅允许在表的同一端（通常为“表尾”）进行插入或删除操作的线性表。

         允许插入和删除的一端称为栈顶(top)，另一端称为栈底(base)
         特点：后进先出 (LIFO)或，先进后出（FILO）

 

         因为栈是限定线的线性表，所以，我们可以调用前面两种线性表，只需要对出栈和入栈操作进行设定即可

    具体实现代码

/**
 * 自己用数组实现的栈
 */
public class ArrayStack<E> {
	  private ArrayList<E> list=new ArrayList<E>();//用来保存数据线性表
	  private  int size;//表示当前栈元素个数
	  /**
	   * 入栈操作
	   * @param e
	   */
	  public void push(E e){
		  list.add(e);
		  size++;
	  }
	 
	  /**
	   * 出栈操作
	   * @return
	   */
	  public E pop(){
		 E e= list.get(size-1);
		 size--;
		 return e;
	  }

}

 

 至于用链表实现栈，则只需要把保存数据的顺序表改成链表即可，此处就不给出代码了

 

自己实现线性表之队列

        与栈类似

        队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。

        在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为队头(front)。
        特点：先进先出 (FIFO)、后进后出 (LILO)

 

       同理，我们也可以调用前面两种线性表，只需要对队列的入队和出队方式进行处理即可

 

package cn.javamzd.collection.List;

/**
 * 用数组实现的队列
 */
public class ArrayQueue<E> {
	private ArrayList<E> list = new ArrayList<E>();// 用来保存数据的队列
	private int size;// 表示当前栈元素个数

	/**
	 * 入队
	 * @param e
	 */
	public void EnQueue(E e) {
		list.add(e);
		size++;
	}

	/**
	 * 出队
	 * @return
	 */
	public E DeQueue() {
		if (size > 0) {
			E e = list.get(0);
			list.delete(0);
			return e;
		}else{
			throw new RuntimeException("已经到达队列顶部");
		}
	}
}

 

 

       
对比线性表和链式表
         前面已经说过顺序表和链式表各自的特点，这里在重申一遍

         数组操作优点：1.通过指针快速定位到下标，查询快速

                     缺点：1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据

                              2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）    

 

 

         链表操作优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可

                     缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。

 

         现在，我们通过进行增删改查操作来感受一次其效率的差异

         思路：通过两个表，各进行大数据量操作（2W）条数据的操作，记录操作前系统时间，操作后系统时间，得出操作时间

  实现代码如下

 

package cn.javamzd.collection.List;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//测试自己实现的ArrayList类和Linkedlist类添加20000个数据所需要的时间
		ArrayList<String> al = new ArrayList<String>();
		LinkedList<String> ll = new LinkedList<String>();
		Long aBeginTime=System.currentTimeMillis();//记录BeginTime
		for(int i=0;i<30000;i++){
			al.add("now"+i);
		}
		Long aEndTime=System.currentTimeMillis();//记录EndTime
		System.out.println("arrylist  add time--->"+(aEndTime-aBeginTime));
		Long lBeginTime=System.currentTimeMillis();//记录BeginTime
		for(int i=0;i<30000;i++){
			ll.add("now"+i);
		}
		Long lEndTime=System.currentTimeMillis();//记录EndTime
		System.out.println("linkedList add time---->"+(lEndTime-lBeginTime));
		
		//测试JDK提供的ArrayList类和LinkedList类添加20000个数据所需要的世界
		java.util.ArrayList<String> sal=new java.util.ArrayList<String>();
		java.util.LinkedList<String> sll=new java.util.LinkedList<String>();
		Long saBeginTime=System.currentTimeMillis();//记录BeginTime
		for(int i=0;i<30000;i++){
			sal.add("now"+i);
		}
		Long saEndTime=System.currentTimeMillis();//记录EndTime
		System.out.println("JDK arrylist  add time--->"+(saEndTime-saBeginTime));
		Long slBeginTime=System.currentTimeMillis();//记录BeginTime
		for(int i=0;i<30000;i++){
			sll.add("now"+i);
		}
		Long slEndTime=System.currentTimeMillis();//记录EndTime
		System.out.println("JDK linkedList add time---->"+(slEndTime-slBeginTime));
	}

}

  得到测试结果如下： 

arrylist add time--->446
linkedList add time---->9767
JDK arrylist add time--->13
JDK linkedList add time---->12

        由以上数据，我们可知：

           1.JDK中的ArrayList何LinkedList在添加数据时的性能，其实几乎是没有差异的

           2.我们自己写的List的性能和JDK提供的List的性能还是存在巨大差异的

           3.我们使用链表添加操作，花费的时间是巨大的，比ArrayList都大几十倍

 

      第三条显然是跟我们最初的设计不相符的，按照我们最初的设想，链表的添加应该比顺序表更省时

      查看我们写的源码，可以发现：

      我们每次添加一个数据时，都需要遍历整个表，得到表尾，再在表尾添加，这是很不科学的

 

      现改进如下：设立一个Node<E>类的成员变量end来指示表尾，这样每次添加时，就不需要再重新遍历得到表尾

      改进后add()方法如下

 

	public boolean add(E e) {
		if (size == 0) {
			header.e = e;
		} else {
			// 根据需要添加的内容，封装为结点
			Node<E> newNode = new Node<E>(e);
			//在表尾添加元素
			last.addNext(newNode);
                                         //将表尾指向当前最后一个元素
			last = newNode;
		}
		size++;// 当前大小自增加1
		return true;
	}

 

       ArrayList添加的效率和JDK中对比起来也太低

       分析原因为：

       每次扩大容量时，扩大量太小，需要进行的复制操作太多

       现在改进如下：

       每次扩大，则扩大容量为当前的三倍，此改进仅需要更改ensureCapacity()方法中的一行代码，此处就不列出了。

 

改进后，再次运行添加元素测试代码，结果如下：

 

arrylist add time--->16
linkedList add time---->8
JDK arrylist add time--->7
JDK linkedList add time---->7

 虽然还有改进的空间，但是显然，我们的效果已经大幅度改进了，而且也比较接近JDK了

 

 

接下来测试插入操作的效率

  我们只需要将测试代码中的添加方法(add())改成插入方法(insert(int index,E e)),为了使插入次数尽可能多，我们把index都设置为0

测试结果如下：

 

arrylist inset time--->17
linkedList inset time---->13
JDK arrylist inset time--->503
JDK linkedList inset time---->11

多次测试，发现我们写的ArrayList在插入方法的效率都已经超过JDK了，而且也接近LinkedLst了。撒花！！！

 

接下来测试删除、得到下标等等操作就不一一列出来了（只需要改变每次调用的方法即可）

 

 

 

 

恩，本来想今晚把所有的集合框架实现都写一下的

但是不知不觉这都又2点了

明早还得去蓝杰上课

果断先睡吧

敬请大家期待我明日大作------------静态/动态查找表的实现，动态查找表查找/加入算法的JAVA实现，Hash表的实现

 

good night

 

 

 

评论

12 楼 wujianjun12315 2011-07-28  

如何实现for each 功能呢？麻烦楼主给讲一下。。。。

11 楼 hnzhoujunmei 2011-05-16  

get(int indext)取出元素，可以调用现成的Node<E> get(int index)啊，知道节点，节点的元素值就知道了啊

10 楼 hackpro 2011-04-21  

是啊，考虑下并发的情况，不过楼主的精神可嘉..

9 楼 blackartanan 2011-01-04  

再来拜读下

8 楼 juda 2010-12-22  

实践帝，赞赞

7 楼 sysiphus 2010-12-07  

6 楼 HelloJimmy 2010-12-04  

没考虑多线程环境 

5 楼 贾懂凯 2010-11-28  

牛，自己实现了，学习了。

4 楼 sxfenglei 2010-11-28  

3 楼 tianmo2008 2010-11-28  

add()里面调用getNode(int index)函数开销有点大吧，实现为双向连表可以吧getNode(int index)的函数开销节省掉

2 楼 java_mzd 2010-11-28  

blackartanan 写道

不错的文章

多谢捧场

1 楼 blackartanan 2010-11-28  

不错的文章