1,引入了JAVA泛型類,因此定義了一個Object[] 類型的數組,從而可以保存各種不同類型的對象。
2,默認構造方法創建了一個默認大小為16的Object數組;帶參數的構造方法創建一個指定長度的Object數組
3,實現的順序表的基本操作有:返回表的長度、獲取指定索引處的元素(注意是索引,而不是位置。索引以下標0開始,位置以下標1開始)、按值查找數據元素的位置、直接插入元素(順序表尾部)、向指定位置插入元素、直接刪除元素(在順序表尾部)、刪除指定索引處元素、判斷表是否為空、清空表。
4,在Java類庫中,java.util.ArrayList 類 實現了順序表,因此可以直接使用JAVA類庫中的ArrayList來完成順序表的各種操作。以下為實現順序表的具體代碼:
import java.util.Arrays;
public class SequenceList<T> {
private final int DEFAULT_SIZE = 16;//final實例變量顯示指定初始值,且不再變化。
private Object[] elementData;//該數組用來保存順序表中的元素
private int capacity;//保存數組的長度
private int size;//保存順序表中當前元素的個數
//以默認的大小創建順序表
public SequenceList(){
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以指定的大小創建順序表
public SequenceList(int initSize){
capacity = 1;
while(capacity < initSize)
capacity <<= 1;//將capacity設置成大於initSize的最小2次方
elementData = new Object[capacity];
}
//獲取順序表中當前元素的個數
public int length(){
return size;
}
//獲取順序表中索引為 i 處的元素,i表示索引,即以 0 開始
public T get(int i){
if(i < 0 || i > size - 1)
throw new IndexOutOfBoundsException("順序表索引越界");
return (T)elementData[i];
}
//查看順序表中指定元素的索引,若未找到,返回-1
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);
for(int i = size; i > index; i--)
elementData[i] = elementData[i - 1];
elementData[index] = element;
size++;//順序表中的元素個數增1
}
private void ensureCapacity(int minCapacity){
//當數組容量已滿時,對數組進行擴容。將容量擴展到大於minCapacity的最小2的次方
if(minCapacity > capacity){
while(capacity < minCapacity)
capacity <<= 1;
elementData = Arrays.copyOf(elementData, capacity);
}
}
//在順序表的末尾添加一個元素
public void add(T element){
insert(element, size);
}
//刪除順序表中指定索引處的元素
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(){
Arrays.fill(elementData, null);//將數組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();
//刪除由於上面for循環中最後添加的多余的兩個字符 (一個是逗號,一個是空格符號)
return sb.delete(len - 2, len).append("]").toString();
}
}
}