上一篇博客中,博主为大家介绍了关于数据结构的三个基本概念:数据结构数据类型抽象数据类型

    在本篇博客中,博主将为大家介绍本系列中第一个出场的数据结构——线性表。顾名思义,线性表就是一种具有像线一样性质的表。比如在操场上站成一列的学生们,总有一个打头,一个结尾,中间的任何一个学生都知道自己前一名同学是谁和后一名同学是谁,就像有一根线将他们串了起来一样。

    像这种从逻辑上看,具有零个或多个数据元素的有限序列我们就称之为线性表(List).

    让我们简单来解读一下线性表的概念。首先它是一个序列,也就是说在线性表中的元素之间是有顺序的,当这个线性表不为空时,除了第一个元素只有后继元素,最后一个元素只有前驱元素之外,其余的元素都有且只有一个前驱和一个后继。线性表中同样允许没有元素,这时我们称之为空表。

    还记得我们在上一篇博客中提到的,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,这种结构可以是逻辑结构或者是物理结构。上面对线性表的定义,明显是从逻辑结构上进行的。

    那么如果从不同的存储形式(物理结构)上来看,在内存中顺序存储的线性表我们称之为顺序表,在内存中链式存储的线性表我们称之为链表。

    也就是说,顺序表与链表也都是数据结构,它们是从物理存储结构角度上定义的线性表,可以看作是抽象的线性表在计算机编程语言中具体的实现。

    接下来我们就一起来定义一下,线性表的抽象数据类型(ADT)

    	ADT List{
    		Data: 
    		线性表中的数据对象集合为{a1,a2,a3... an},所有元素的数据类型必须都是DataType。
    		除了第一个元素a1只有后继元素,最后一个元素an只有前驱元素之外,其余的元素都有且只有一个前驱和一个后继。
    		
    		Operation:
    		int size();                        //返回线性表中元素的个数
    		boolean isEmpty();                 //检查线性表是否为空
    		boolean contains(Object o);        //检查线性表是否包含某个元素
    		boolean add(E e);                  //在线性表的结尾插入一个元素
    		void add(int  index, E element);   //在线性表指定位置插入一个元素
    		boolean remove(Object o);          //在线性表中删除指定元素
    		E remove(int index);               //删除线性表上指定位置的元素
    		void clear();                      //清空整个线性表
    		E get(int index);                  //返回指定位置上的元素
    		E set(int index, E element);       //替换指定位置上的元素
    		
    	}
    

    在Java中,我们可以将线性表的抽象数据类型List抽象为一个接口类MyList(为了区分java.util.List),并将上面我们归纳出的操作放在接口类中。

    	interface MyList<E>{
    		int size();                        //返回线性表中元素的个数
    		boolean isEmpty();                 //检查线性表是否为空
    		boolean contains(Object o);        //检查线性表是否包含某个元素
    		boolean add(E e);                  //在线性表的结尾插入一个元素
    		void add(int  index, E element);   //在线性表指定位置插入一个元素
    		boolean remove(Object o);          //在线性表中删除指定元素
    		E remove(int index);               //删除线性表上指定位置的元素
    		void clear();                      //清空整个线性表
    		E get(int index);                  //返回指定位置上的元素
    		E set(int index, E element);       //替换指定位置上的元素
    	}
    

    接下来博主就带着大家一起用Java实现一个在内存中顺序存储的线性表(也叫顺序表)。要想在内存中顺序存储,我们必须将元素放在数组当中,因此我们的顺序表就起名叫做MyArrayList。

    • 首先我们来写这个数据结构的私有成员,一个能装泛型E的数组,size表示列表中元素的数目,以及一个默认的初识数组大小
    public class MyArrayList<E> implements MyList<E>{
    
        //在声明MyArrayList时,如不指明大小,则初始大小为10
        private static final int DEFAULT_CAPACITY = 10;
        private E[] contents;
        private int size = 0;
    
        //两种构造函数,允许用户创建指定大小或者默认大小的线性表
        public MyArrayList(){
            init(DEFAULT_CAPACITY);
        }
        public MyArrayList(int initCapacity){
            init(initCapacity);
        }
        //私有化方法init帮助构造函数来初始化数组contents
        private void init(int capacity){
            //注意不能建立泛型数组,因此我们强行转换一个Object数组
            contents = (E[]) new Object[capacity];
        }
    
    • 接下来我们实现获取元素个数和查看是否为空的方法,很简单单行代码即可实现
    	@Override
    	public int size() {
    		// TODO Auto-generated method stub
    		return this.size;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		// TODO Auto-generated method stub
    		return size()==0;
    	}
    
    • 然后是两种不同的插入方法
    	@Override
    	public boolean add(E e) {
    		// TODO Auto-generated method stub
    		//在插入元素之前,检查数组是否有足够的空间放置新的元素,若没有,则对数组进行扩容
    		ensureCapacity();
    		contents[size++] = e;
    		return true;
    	}
    
    	@SuppressWarnings("unchecked")
    	private void ensureCapacity() {
    		// TODO Auto-generated method stub
    		if(size()>=contents.length) {
    			//此处新数组的容量是旧数组的2倍加1,你可以自己选择扩容的多少
    			E[] newContents = (E[]) new Object[2*contents.length+1];
    			//将就数组中的值全部拷于新数组中
    			System.arraycopy(contents, 0, newContents, 0, size());
    			//再让contents指向新的数组
    			contents = newContents;
    		}
    	}
    	@Override
    	public void add(int index, E element) {
    		// TODO Auto-generated method stub
    		//一旦要插入元素的位置为负或大于目前的元素数量就抛出异常
            //此处允许index等于size,相当于在列表末尾插入元素
    		if(index<0 || index>size())
    			throw new ArrayIndexOutOfBoundsException();
    		//在插入元素之前,检查数组是否有足够的空间放置新的元素,若没有,则对数组进行扩容
    		ensureCapacity();
    		//将数组中从index位置开始的size-index个元素复制到数组从index+1开始的位置去
    		//相当于将数组中index位置之后的元素顺次向后移动一位
    		System.arraycopy(contents, index, contents, index+1, size() - index);
    		//将要插入的元素放置到index位置上去
    		contents[index] = element;
    		this.size++;
    	}
    	/*
    	 * 等价与上面的add(int index, E element)方法
    	 * 
    	 * System.arraycopy(contents, index, contents, index+1, size() - index);
    	 * 等价于:
    	 * for(int i=size(); i>index; i--){ 
    			contents[i] = contents[i-1];
    	   }
    	 * 
    	  @Override
    	  public void add(int index, E element) {
    		  // TODO Auto-generated method stub
    		  //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常
    		  //此处允许index等于size,相当于在列表末尾插入元素
    		  if(index<0 || index>size())
    			  throw new ArrayIndexOutOfBoundsException();
    		  //在插入元素之前,检查数组是否有足够的空间放置新的元素,若没有,则对数组进行扩容
    		  ensureCapacity();
    		  for(int i=size(); i>index; i--) 
    			  contents[i] = contents[i-1];
    		  //将要插入的元素放置到index位置上去
    		  contents[index] = element;
    		  this.size++;
    	  }*/
    
    • 紧接着是两个不同的删除方法
    	@Override
    	public boolean remove(Object o) {
    		// TODO Auto-generated method stub
    		if(o == null) {
    			for(int i=0; i<size(); i++) {
    				if(contents[i] == null) {
    					//如果找到元素为null,就使用私有方法fastRemove将该位置元素删除
    					fastRemove(i);
    					return true;
    				}
    			}
    			return false;
    		}else {
    			for(int i=0; i<size();i++) {
    				if(contents[i].equals(o)) {
    					//如果找到元素为o,就使用私有方法fastRemove将该位置元素删除
    					fastRemove(i);
    					return true;
    				}
    			}
    			return false;
    		}
    	}
    	private void fastRemove(int index) {
    		// TODO Auto-generated method stub
    		//需要从后向前移动的元素数目
            int numMoved = size() - index -1;
            if(numMoved > 0){
                //将数组i+1位置开始的numMoved个元素移动到数组i的位置
                //相当于将i位置上的元素删除,并将后面的元素向前移一位
                System.arraycopy(contents,index+1,contents,index,numMoved);
            }
            //将元素数目减一并释放原来最后一位的内存
            contents[--size] = null;
    	}
    	
    	/*
    	 * 等价与上面的fastRemove(int index)方法
    	 * 
    	 * System.arraycopy(contents,index+1,contents,index,numMoved);
    	 * 等价于:
    	 * for(int i=index; i<size()-1; i++){
    			contents[i] = contents[i+1];
    	   }
    	 * 
    	  private void fastRemove(int index) {
    		  // TODO Auto-generated method stub
    		  for(int i=index; i<size()-1; i++)
    			  contents[i] = contents[i+1];
    		  //将元素数目减一并释放原来最后一位的内存
    		  contents[--size] = null;
    	  }*/
    	
    	@Override
    	public E remove(int index) {
    		// TODO Auto-generated method stub
    		//一旦要插入元素的位置为负或大于目前的元素数量就抛出异常
            //此处不允许index等于size
    		checkIndexValidation(index);
    		E element = contents[index];
    		fastRemove(index);
    		return element;
    	}
    	
    	private void checkIndexValidation(int index) {
    		if(index<0 || index>=size())
    			throw new ArrayIndexOutOfBoundsException();
    	}
    
    • 之后是获取,修改,查看是否包含,以及清空整个列表这几个简单的方法了:
    	@Override
    	public void clear() {
    		// TODO Auto-generated method stub
    		for(int i=0; i<size(); i++) {
    			contents[i] = null;
    		}
    		size = 0;
    	}
    
    	@Override
    	public E get(int index) {
    		// TODO Auto-generated method stub
    		checkIndexValidation(index);
    		return contents[index];
    	}
    
    	@Override
    	public E set(int index, E element) {
    		// TODO Auto-generated method stub
    		checkIndexValidation(index);
    		E old = contents[index];
    		contents[index] = element;
    		return old;
    	}
    	@Override
    	public boolean contains(Object o) {
    		// TODO Auto-generated method stub
    		if(o == null) {
    			for(int i=0 ;i<size(); i++) {
    				if(contents[i] == null)
    					return true;
    			}
    			return false;
    		}else {
    			for(int i=0 ;i<size(); i++) {
    				if(o.equals(contents[i]))
    					return true;
    			}
    			return false;
    		}
    	}
    

    在完成了自己写的一个MyArrayList之后,我们分析一下这种数据结构的特点。很明显,对于基于数组实现的线性表来说

    我们要读取或修改某一个位置的元素只花费常数时间 O(1)
    我们要增加或删除某一个元素最坏情况下要花费线性时间 O(n),因为涉及到移动其它的元素

    因此,当我们在遇到频繁访问列表中元素时,ArrayList是一个很好的选择;但当我们需要频繁添加、删除列表中元素,尤其是在表的前端进行增删操作时,ArrayList就不是一个特别好的选择了。

    到这里我们自己实现的MyArrayList就完成了,是不是感觉自己写数据结构也没有那么难呢?但是我们这里完成的这个只是一个很简单的数据结构,也没有实现Itrable等接口。

    要想真正提高巩固自己的Java水平,我们需要在自己写完之后去对比源码中ArrayList的实现。看看尽管功能都是实现的差不多,为什么大牛写的代码就很优雅、效率高。不断地比较、吸收、学习,我们才能进步下去。