说到线性结构,我们应该立马能够在脑子里蹦出“Array数组”这个词。在Java当中,数组和对象区别基本数据类型存放在堆当中。它是一连串同类型数据存放的一个整体。通常我们定义的方式为:
Object[] objs = new Object[n] //n为数组大小
而顺序表的底层便是数组。在Java当中顺序表比较常用的有:ArrayList、Vector等。下面我们通过代码实现我们自己的SequenceList。
首先定义List接口:
1 package com.chen.arithmetic_test.list_test; 2 3 /** 4 * Created by ChenMP on 2017/7/3. 5 */ 6 public interface List { 7 //获得长度 8 public int size(); 9 //插入元素 10 public boolean insert(int index, Object o) throws Exception; 11 //新增元素 12 public boolean add(Object o) throws Exception; 13 //删除元素 14 public boolean remove(int index) throws Exception; 15 //获取元素 16 public Object get(int index) throws Exception; 17 //判断线性表是否为空 18 public boolean isEmpty(); 19 }
定义SequenceList实现类:
1 package com.chen.arithmetic_test.list_test; 2 3 /** 4 * Created by ChenMP on 2017/7/3. 5 */ 6 public class SequenceList implements List { 7 private Object[] listArray;//对象数组 8 private int size;//对象数组长度 9 private boolean isFixed;//是否限定对象数组长度 10 11 public SequenceList() { 12 this.size = 0; 13 this.listArray = new Object[3];//默认对象数组固定长度为3 14 this.isFixed = false;//不限定对象数组长度 15 } 16 17 public SequenceList(int length) { 18 this.listArray = new Object[length]; 19 this.size = 0; 20 this.isFixed = true;//限定对象数组长度 21 } 22 23 @Override 24 public int size() { 25 26 return size; 27 } 28 29 @Override 30 public boolean insert(int index, Object o) throws Exception { 31 if(index > size || index < 0) //index不合法 32 throw new Exception("IndexOutOfBoundsException"); 33 34 if(index==size && size==this.listArray.length && this.isFixed) //下标超过边界,且限定对象数组长度 35 throw new Exception("IndexOutOfBoundsException"); 36 37 if(index==size && size==this.listArray.length && !this.isFixed) {//下标超过边界,且不限定对象数组长度 38 Object[] newListArray = new Object[this.listArray.length + 10]; 39 System.arraycopy(listArray, 0, newListArray, 0, listArray.length); 40 newListArray[index] = o; 41 this.listArray = newListArray; 42 this.size++; 43 return true; 44 } 45 46 if (index == size && size<this.listArray.length) { 47 listArray[index] = o; 48 this.size++; 49 return true; 50 } 51 52 if(index < size && index >= 0) { 53 listArray[index] = o; 54 return true; 55 } 56 57 return false; 58 } 59 60 @Override 61 public boolean add(Object o) throws Exception { 62 if(this.size==this.listArray.length && this.isFixed) 63 throw new Exception("IndexOutOfBoundsException"); 64 65 if(this.size==this.listArray.length && !this.isFixed) { 66 Object[] newListArray = new Object[this.listArray.length + 10]; 67 System.arraycopy(listArray, 0, newListArray, 0, listArray.length); 68 newListArray[size] = o; 69 this.listArray = newListArray; 70 this.size++; 71 return true; 72 } 73 74 if(this.size<this.listArray.length) { 75 listArray[this.size] = o; 76 this.size++; 77 return true; 78 } 79 return false; 80 } 81 82 @Override 83 public boolean remove(int index) throws Exception { 84 if(index < 0 || index >= size) 85 throw new Exception("IndexOutOfBoundsException"); 86 87 System.arraycopy(listArray, 0, listArray, index, listArray.length-index); 88 this.size--; 89 return true; 90 } 91 92 @Override 93 public Object get(int index) throws Exception { 94 if(index < 0 || index >= size) 95 throw new Exception("IndexOutOfBoundsException"); 96 return this.listArray[index]; 97 } 98 99 @Override 100 public boolean isEmpty() { 101 return this.size>0?false:true; 102 } 103 104 @Override 105 public String toString() { //返回List内容信息 106 StringBuilder sb = new StringBuilder(); 107 for (Object o : this.listArray) { 108 if(null != o) 109 sb.append(o).append(" ,"); 110 } 111 return sb.toString(); 112 } 113 }
下面是我们的测试代码:
1 package com.chen.arithmetic_test.list_test; 2 3 /** 4 * Created by ChenMP on 2017/7/3. 5 */ 6 public class TestList { 7 8 public static void main(String[] args) throws Exception { 9 List list = new SequenceList(3); 10 list.insert(0,0); 11 list.add(1); 12 list.add(2); 13 // list.add(3); 14 System.out.print("测试定长list: " + list.toString() + "|| list长度为: " + list.size()); 15 16 System.out.println(); 17 List list2 = new SequenceList(); 18 list2.add(0); 19 list2.add(1); 20 list2.add(2); 21 list2.add(3); 22 System.out.print("测试不定长list: " + list2.toString() + "|| list长度为: " + list2.size()); 23 } 24 }
在java中顺序表的实现原理基本也是类似的,理解了它的原理再看JDK源码自然也就很容易理解了。