抽象数据模型ADT：
1 package ren.laughing.datastructure.base; 2 3 import ren.laughing.datastructure.exception.OutOfBoundaryException; 4 /** 5 * 线性表ADT（抽象数据模型） 6 * ADT包括数据数据元素，数据关系以及相关的操作。 7 * 即ADT 8 * { 9 * 数据对象：（数据元素集合）10 * 数据关系：（数据关系二元组结合）11 * 基本操作：（操作函数的罗列）12 * }13 * @author Laughing14 * @time 2016年4月5日15 */16 public interface List {17 //返回线性表的大小，即数据元素的个数。18 public int getSize();19 //如果线性表为空返回 true，否则返回 false。20 public boolean isEmpty();21 //判断线性表是否包含数据元素 e22 public boolean contains(Object e);23 //返回数据元素 e 在线性表中的序号24 public int indexOf(Object e);25 //将数据元素 e 插入到线性表中 i 号位置26 public void insert(int i, Object e) throws OutOfBoundaryException;27 //将数据元素 e 插入到元素 obj 之前28 public boolean insertBefore(Object obj, Object e);29 //将数据元素 e 插入到元素 obj 之后30 public boolean insertAfter(Object obj, Object e);31 //删除线性表中序号为 i 的元素,并返回之32 public Object remove(int i) throws OutOfBoundaryException;33 //删除线性表中第一个与 e 相同的元素34 public boolean remove(Object e);35 //替换线性表中序号为 i 的数据元素为 e，返回原数据元素36 public Object replace(int i, Object e) throws OutOfBoundaryException;37 //返回线性表中序号为 i 的数据元素38 public Object get(int i) throws OutOfBoundaryException;39 } 数据元素的比较策略：
1 package ren.laughing.datastructure.base; 2 /** 3 * 数据元素的比较策略 4 * @author Laughing 5 * @time 2016年4月5日 6 */ 7 public interface Strategy { 8 //判断两个数据是否相等 9 public boolean equal(Object obj1,Object obj2);10 //判断两个数据大小，返回-1|0|111 public int compare(Object obj1,Object obj2);12 } 线性表的实现：顺序存储结构
1 package ren.laughing.datastructure.baseImpl; 2 3 import ren.laughing.datastructure.base.List; 4 import ren.laughing.datastructure.base.Strategy; 5 import ren.laughing.datastructure.exception.OutOfBoundaryException; 6 /** 7 * 线性表的实现 8 * @author Laughing 9 * @time 2016年4月5日 10 */ 11 public class ArrayList implements List{ 12 private final int LEN = 8; //默认数组大小8 13 private Strategy strategy; //数据元素的比较策略 14 private int size; //线性表中数据元素的个数 15 private Object[] elements; //数据元素数组 16 //构造器 17 public ArrayList() { 18 this(new DefaultStrategy()); 19 } 20 public ArrayList(Strategy strategy) { 21 this.strategy = strategy; 22 size = 0; 23 elements = new Object[LEN];//默认数组大小 24 } 25 26 27 @Override 28 public int getSize() { 29 return size; 30 } 31 32 @Override 33 public boolean isEmpty() { 34 if(size == 0){ 35 return true; 36 }else{ 37 return false; 38 } 39 } 40 41 @Override 42 public boolean contains(Object e) { 43 for(int i=0;i size) { 64 throw new OutOfBoundaryException("错误，指定的插入序号越界。"); 65 } 66 //若数据元素个数大于数据元素数组长度 67 if (size >= elements.length) { 68 expandSpace();// 扩充数组长度 69 } 70 for (int j = size; j > i; j--) { 71 elements[j] = elements[j - 1]; 72 } 73 elements[i] = e; 74 size++; 75 76 } 77 //将数据元素 e 插入到元素 obj之前 78 @Override 79 public boolean insertBefore(Object obj, Object e) { 80 int index = this.indexOf(obj); 81 if(index < 0){ 82 return false; 83 }else{ 84 this.insert(index, e); 85 return true; 86 } 87 } 88 //将数据元素 e 插入到元素 obj之后 89 @Override 90 public boolean insertAfter(Object obj, Object e) { 91 int index = this.indexOf(obj); 92 if(index < 0){ 93 return false; 94 }else{ 95 this.insert(index+1, e); 96 return true; 97 } 98 } 99 //删除线性表中序号为 i 的元素,并返回之100 @Override101 public Object remove(int i) throws OutOfBoundaryException {102 if(i>=size||i<0){103 throw new OutOfBoundaryException("指定的删除序号越界");104 }105 Object obj = elements[i];106 for(int j=i;j =size){127 throw new OutOfBoundaryException("要替换元素的序号越界");128 }129 Object obj = elements[i];130 elements[i] = e;131 return obj;132 }133 //返回线性表中序号为 i 的数据元素134 @Override135 public Object get(int i) throws OutOfBoundaryException {136 if(i<0||i>=size){137 throw new OutOfBoundaryException("要获取元素的序号越界");138 }139 Object obj = elements[i];140 return obj;141 }142 /**143 * 扩充数组长度144 */145 private void expandSpace() {146 Object[] a = new Object[elements.length * 2];147 for (int i = 0; i < elements.length; i++)148 a[i] = elements[i];149 elements = a;150 }151 152 }