[Java算法分析与设计]--线性结构与顺序表(List)的实现应用

　　说到线性结构，我们应该立马能够在脑子里蹦出“Array数组”这个词。在Java当中，数组和对象区别基本数据类型存放在堆当中。它是一连串同类型数据存放的一个整体。通常我们定义的方式为：

Object[] objs = new Object[n] //n为数组大小

　　而顺序表的底层便是数组。在Java当中顺序表比较常用的有：ArrayList、Vector等。下面我们通过代码实现我们自己的SequenceList。

　　首先定义List接口：

 package com.chen.arithmetic_test.list_test;

 /**

  * Created by ChenMP on 2017/7/3.

  */

 public interface List {

     //获得长度

     public int size();

     //插入元素

     public boolean insert(int index, Object o) throws Exception;

     //新增元素

     public boolean add(Object o) throws Exception;

     //删除元素

     public boolean remove(int index) throws Exception;

     //获取元素

     public Object get(int index) throws Exception;

     //判断线性表是否为空

     public boolean isEmpty();

 }

　　定义SequenceList实现类：

 package com.chen.arithmetic_test.list_test;

 /**

  * Created by ChenMP on 2017/7/3.

  */

 public class SequenceList implements List {

     private Object[] listArray;//对象数组

     private int size;//对象数组长度

     private boolean isFixed;//是否限定对象数组长度

     public SequenceList() {

         this.size = 0;

         this.listArray = new Object[3];//默认对象数组固定长度为3

         this.isFixed = false;//不限定对象数组长度

     }

     public SequenceList(int length) {

         this.listArray = new Object[length];

         this.size = 0;

         this.isFixed = true;//限定对象数组长度

     }

     @Override

     public int size() {

         return size;

     }

     @Override

     public boolean insert(int index, Object o) throws Exception {

         if(index > size || index < 0) //index不合法

             throw new Exception("IndexOutOfBoundsException");

         if(index==size && size==this.listArray.length && this.isFixed) //下标超过边界，且限定对象数组长度

             throw new Exception("IndexOutOfBoundsException");

         if(index==size && size==this.listArray.length && !this.isFixed) {//下标超过边界，且不限定对象数组长度

             Object[] newListArray = new Object[this.listArray.length + 10];

             System.arraycopy(listArray, 0, newListArray, 0, listArray.length);

             newListArray[index] = o;

             this.listArray = newListArray;

             this.size++;

             return true;

         }

         if (index == size && size<this.listArray.length) {

             listArray[index] = o;

             this.size++;

             return true;

         }

         if(index < size && index >= 0) {

             listArray[index] = o;

             return true;

         }

         return false;

     }

     @Override

     public boolean add(Object o) throws Exception {

         if(this.size==this.listArray.length && this.isFixed)

             throw new Exception("IndexOutOfBoundsException");

         if(this.size==this.listArray.length && !this.isFixed) {

             Object[] newListArray = new Object[this.listArray.length + 10];

             System.arraycopy(listArray, 0, newListArray, 0, listArray.length);

             newListArray[size] = o;

             this.listArray = newListArray;

             this.size++;

             return true;

         }

         if(this.size<this.listArray.length) {

             listArray[this.size] = o;

             this.size++;

             return true;

         }

         return false;

     }

     @Override

     public boolean remove(int index) throws Exception {

         if(index < 0 || index >= size)

             throw new Exception("IndexOutOfBoundsException");

         System.arraycopy(listArray, 0, listArray, index, listArray.length-index);

         this.size--;

         return true;

     }

     @Override

     public Object get(int index) throws Exception {

         if(index < 0 || index >= size)

             throw new Exception("IndexOutOfBoundsException");

         return this.listArray[index];

     }

     @Override

     public boolean isEmpty() {

         return this.size>0?false:true;

     }

     @Override

     public String toString() { //返回List内容信息

         StringBuilder sb = new StringBuilder();

         for (Object o : this.listArray) {

             if(null != o)

                 sb.append(o).append(" ,");

         }

         return sb.toString();

     }

 }

　　下面是我们的测试代码：

 package com.chen.arithmetic_test.list_test;

 /**

  * Created by ChenMP on 2017/7/3.

  */

 public class TestList {

     public static void main(String[] args) throws Exception {

         List list = new SequenceList(3);

         list.insert(0,0);

         list.add(1);

         list.add(2);

 //        list.add(3);

         System.out.print("测试定长list： " + list.toString() + "|| list长度为： " + list.size());

         System.out.println();

         List list2 = new SequenceList();

         list2.add(0);

         list2.add(1);

         list2.add(2);

         list2.add(3);

         System.out.print("测试不定长list： " + list2.toString() + "|| list长度为： " + list2.size());

     }

 }

　　在java中顺序表的实现原理基本也是类似的，理解了它的原理再看JDK源码自然也就很容易理解了。

巴特西

[Java算法分析与设计]--线性结构与顺序表(List)的实现应用

最新文章

热门文章