仿照arrayList寫了一個簡化版的線性表，主要為了用來研究arrayList在實現什麼操作的情況下比較節省性能，樓主文采不好，直接上代碼。
import java.util.Arrays;
public class SequenceList<T> {
private final int DEFAULT_SIZE = 16;
// 保存數組的長度
private int capacity;
// 定義一個數組用於保存順序線性表的元素
private Object[] elementData;
// 保存順序表中元素的當前個數
private int size = 0;
// 以默認數組長度創建空順序線性表
public SequenceList() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
// 以一個初始化元素創建順序線性表
public SequenceList(T element) {
this();
elementData[0] = element;
size++;
}
/**
* 以指定長度的數組來創建順序線性表
*
* @param element
* 指定順序線性表中第一個元素
* @param initSize
* 指定順序線性表底層數組的長度
*/
public SequenceList(T element, int initSize) {
capacity = 1;
// 把capacity設為大於initSize的最小的2的n次方
while (capacity < initSize) {
capacity <<= 1;
}
elementData = new Object[capacity];
elementData[0] = element;
size++;
}
// 獲取順序線性表的大小
public int length() {
return size;
}
// 獲取順序線性表中索引為i處的元素
public T get(int i) {
if (i < 0 || i > size - 1) {
throw new IndexOutOfBoundsException("線性表索引越界");
}
return (T) elementData[i];
}
// 查找順序線性表中指定元素的索引
public int locate(T element) {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(element)) {
return i;
}
}
return -1;
}
// 向順序線性表的指定位置插入一個元素
public void insert(T element, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("線性表索引越界");
}
ensureCapacity(size + 1);
// 將指定索引處之後的所有元素向後移動一格
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 在線性順序表的開始處添加一個元素
public void add(T element) {
insert(element, size);
}
// 很麻煩，而且性能很差
private void ensureCapacity(int minCapacity) {
// 如果數組的原有長度小於目前所需的長度
if (minCapacity > capacity) {
// 不斷地將capacity * 2，直到capacity大於minCapacity
while (capacity < minCapacity) {
capacity <<= 1;
}
elementData = Arrays.copyOf(elementData, capacity);
}
}
// 刪除順序線性表中指定索引處的元素
public T delete(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("線性表索引越界");
}
T oldValue = (T) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
// 清空最後一個元素
elementData[--size] = null;
return oldValue;
}
// 刪除順序線性表中最後一個元素
public T remove() {
return delete(size - 1);
}
// 判斷順序線性表是否為空表
public boolean empty() {
return size == 0;
}
// 清空線性表
public void clear() {
// 將底層數組所有元素賦為null
Arrays.fill(elementData, null);
size = 0;
}
public String toString() {
if (size == 0) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}
順序表使用數組儲存數據，所以對於隨機的訪問有很好的性能支持，不管是訪問線性表上的哪一個元素都可以直接使用elementData[i]直接得到，但是對於添加元素會很消耗性能，主要是在隨機插入元素的時候可能要將後面的元素整體向後移一位，還有數組長度不夠的時候需要創建原數組2倍的新數組然後將數據整體搬家到新數組，然後釋放掉原數組這兩點上非常消耗性能，所以arrayList的使用通常是沒有復雜的插入操作，更多的是對數據的取操作，而LinkedList(鏈表)在這些使用的性能方面正好相反。
