顺序表的设计与实现List（Arraylist）

  1 //采用线性表实现一个list集合
  2 public class SeqList<T> extends Object {
  3     private Object[] elements;            //数组
  4     private int n;                        //长度
  5 
  6     /**
  7      * 构造方法，根据传参创建空表
  8      * @param length
  9      */
 10     public SeqList(int length) {
 11         this.elements = new Object[length];
 12         this.n = length;
 13     }
 14 
 15     /**
 16      * 空参构造将会调用本类已声明的指定参数列表的构造方法 进而创建一个空表,默认长度为64
 17      */
 18     public SeqList() {
 19         this(64);
 20     }
 21 
 22     /**
 23      * 重载构造方法，根据传参确定表长度，并且将数组元素复制到成员变量elements中
 24      * @param values
 25      */
 26     public SeqList(T[] values) {
 27         this(values.length);          // 创建容量为values.length的空表
 28         for (int i = 0; i < values.length; i++) {
 29             this.elements[i] = values[i];  //复制数组元素
 30             this.n = elements.length;
 31         }
 32     }
 33 
 34     /**
 35      * 判断顺序表是否为空，为空则返回true,时间复杂度为O(1)
 36      * @return
 37      */
 38     public boolean isEmpty() {
 39         return this.n == 0;
 40     }
 41 
 42     /**
 43      * 返回顺序表元素个数,时间复杂度为O(1)
 44      * @return
 45      */
 46     public int size() {
 47         return this.n;
 48     }
 49 
 50     /**
 51      * 返回第i个元素，若i越界则返回null,,时间复杂度为O(1)
 52      * @param i
 53      * @return
 54      */
 55     @SuppressWarnings("unchecked")
 56     public T get(int index) {
 57         if (index >= 0 && index < this.n) {
 58             return (T) this.elements[index];
 59         } else {
 60             return null;
 61         }
 62     }
 63 
 64     /**
 65      * 替换指定位置的元素，若index越界，则抛出越界异常，若x为空，则抛出空对象异常,时间复杂度为O(1)
 66      * @param index
 67      * @param x
 68      */
 69     public void set(int index, T x) {
 70         if (x == null) {
 71             throw new NullPointerException("x==null");
 72         }
 73         if (index >= 0 && index < this.n) {
 74             this.elements[index] = x;
 75         } else {
 76             throw new java.lang.IndexOutOfBoundsException(index + "");
 77         }
 78     }
 79 
 80     /**
 81      * 覆写Object的toString 方法,需要遍历,时间复杂度为O(n)
 82      */
 83     public String toString() {
 84         String str = this.getClass().getName() + "(";
 85         if (this.n > 0) {
 86             str += this.elements[0].toString();
 87         }
 88         for (int i = 0; i < this.n; i++) {
 89             str += "," + this.elements[i].toString();
 90         }
 91         return str + ")";
 92     }
 93 
 94     /**
 95      * 在指定位置插入操作，index是插入的位置（下标），x是插入的元素
 96      * @param index
 97      * @param x
 98      * @return
 99      */
100     public int add(int index, T x) {
101         if (x == null) {
102             throw new NullPointerException("x==null");
103         }
104         // 对index进行容错处理,使下标index始终在数组长度范围内
105         if (index < 0) {
106             index = 0;
107         }
108         if (index > this.n) {
109             index = this.n;
110         }
111         // 复制原数组到一个新的数组source中
112         Object[] source = this.elements;
113         // 如数组满，则扩充顺序表的数组容量，通过重申请和复制完成
114         if (this.n == elements.length) {
115             this.elements = new Object[source.length +1];
116             // 复制当前数组前i-1个元素到新的数组中
117             for (int j = 0; j < index; j++) {
118                 this.elements[j] = source[j];
119             }
120         }
121         // x插入为第i个元素
122         this.elements[index] = x;
123         // 从i开始至表尾的元素往后移，次序从后向前，这些元素的下标都要加1
124         for (int j = this.n - 1; j >= index; j--) {
125             this.elements[j + 1] = source[j];
126         }
127         // 数组的长度增加
128         this.n++;
129         // 返回插入元素的下标
130         return index;
131     }
132     /*
133      * 重载add方法，在尾部插入元素
134      */
135     public int add(T x) {
136         return this.add(this.n, x);
137     }
138     /*
139      * 在尾部插入一个线性表对象
140      * @param newList
141      * @return
142      */
143     public int addAll(SeqList<T> newList) {
144         Object[] source = this.elements;
145         this.n = source.length + newList.size();
146         // 数组扩容
147         this.elements = new Object[n];
148         // 将原数组的元素拷贝到新数组中
149         for (int i = 0; i < source.length; i++) {
150             this.elements[i] = source[i];
151         }
152         // 将插入的集合元素拷贝到数组的后面
153         for (int j = 0; j < newList.size(); j++) {
154             this.elements[source.length + j] = newList.get(j);
155         }
156         return n;
157     }
158     /*
159      * 从指定位置index处开始插入一组元素
160      * @param index
161      * @param newList
162      * @return
163      */
164     public int addAll(int index,SeqList<T> newList) {
165         // 对index进行容错处理,使下标index始终在数组长度范围内
166         if (index < 0) {
167             index = 0;
168         }
169         if (index > this.n) {
170             index = this.n;
171         }
172         // 复制原数组到一个新的数组source中
173         Object[] source = this.elements;
174         this.n = source.length+newList.size();
175         this.elements = new Object[n];
176         //从source中拷贝index之前的元素
177         for (int j = 0; j < index; j++) {
178             this.elements[j] = source[j];
179         }
180         //从集合中取出元素拷贝到新数组中
181         for (int j = 0; j < newList.size(); j++) {
182             this.elements[j+index] = newList.get(j);
183         }
184         //从source中拷贝index之后的元素
185         for (int j = index; j < source.length; j++) {
186             this.elements[j+newList.size()] = source[j];
187         }
188         return n;
189     }
190     
191     /**
192      * 删除元素，返回被删除元素，index之后的元素都要往前移一位
193      * @param index
194      */
195     @SuppressWarnings("unchecked")
196     public T remove(int index) {
197         T old = null;
198         if (index > this.n) {
199             index = this.n - 1;
200         }
201         if (index >= 0 && index < this.n) {
202             old = (T) this.elements[index]; // 被删除元素
203         }
204         // 复制原数组到source作为备份
205         Object[] source = this.elements;
206         // 前i个元素复制
207         for (int j = 0; j < index; j++) {
208             this.elements[j] = source[j];
209         }
210         // 后i个朝前挪一位
211         for (int j = index; j < this.n - 1; j++) {
212             this.elements[j] = source[j + 1];
213         }
214         this.n--;
215         return old;
216     }
217 
218     /*
219      *  查找指定元素的位置,若不存在则返回-1
220      */
221     public int indexOf(T value) {
222         for (int i = 0; i < this.n; i++) {
223             if (value.equals(this.elements[i])) {
224                 return i;
225             }
226         }
227         return -1;
228     }
229 
230     /*
231      * 顺序表比较相等 (non-Javadoc)
232      * @see java.lang.Object#equals(java.lang.Object)
233      */
234     public boolean equals(Object obj) {
235         // 同一个顺序表实例
236         if (this == obj) {
237             return true;
238         }
239         // SeqList<?>是所有SeqList<T>的父类
240         if (obj instanceof SeqList<?>) {
241             SeqList<T> slist = (SeqList<T>) obj;
242             if (this.n == slist.n) {
243                 for (int i = 0; i < this.n; i++) {
244                     if (!this.get(i).equals(slist.get(i))) {
245                         return false;
246                     }
247                     return true;
248                 }
249             }
250         }
251         return false;
252     }
253 }