線性表的順序存儲結構，也稱為順序表，指用一段連續的存儲單元依次存儲線性表中的數據元素。
根據順序表的特性，我們用數組來實現順序表，下面是我通過數組實現的Java版本的順序表。
package com.phn.datestructure;
/**
* @author 潘海南
* @Email [email protected]
* @TODO 順序表
* @date 2015年7月16日
*/
public class FOArrayList<E> {
// 順序表長度
private int size;
// 順序表默認數組為null
private Object[] data = null;
// 順序表中數組的初始化長度
private int capacity;
// 順序表默認初始化長度
private static final int DEFUALT_INITIAL_SIZE = 0;
/**
* 默認無參構造函數
*/
public FOArrayList() {
this(DEFUALT_INITIAL_SIZE);
}
/**
* @TODO 帶參構造函數
* @param initialSize 初始化順序表長度
*/
public FOArrayList(int initialSize) {
if (initialSize < 0) {
throw new RuntimeException("數組大小錯誤:" + initialSize);
}
this.data = new Object[initialSize];
this.capacity = initialSize;
this.setSize();
}
/**
* @TODO 設置順序表的長度
*/
private void setSize() {
this.size = 0;
}
/**
* @TODO 獲取順序表的長度
* @return size 順序表的長度
*/
public int size() {
return this.size;
}
/**
* @TODO 順序表添加元素
* @param e 數據元素類型
* @return true
*/
public boolean add(E e) {
ensureSize(size);
this.data[size] = e;
this.size++;
return true;
}
/**
* @TODO 順序表插入元素
* @param index 插入位置
* @param e 數據元素類型
* @return true
*/
public boolean insert(int index, E e) {
if (index >= 0 && index <= size) {
ensureSize(size);
E temp = (E) this.data[index - 1];
this.data[index - 1] = e;
this.size++;
for (int i = index; i <= size; i++) {
E temp2 = (E) this.data[i];
this.data[i] = temp;
temp = temp2;
}
} else {
throw new RuntimeException("數組下標錯誤：" + index);
}
return true;
}
/**
* @TODO 順序表刪除元素
* @param index 將要刪除的元素的索引位置
* @return E 刪除的元素
*/
public E remove(int index) {
validateIndex(index);
E e = (E) this.data[index];
for (int i = index; i < size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
return e;
}
/**
* @TODO 根據元素索引位置獲取元素
* @param index 元素的索引位置
* @return E 元素e
*/
public E get(int index) {
validateIndex(index);
return (E) this.data[index];
}
/**
* @TODO 將順序表中索引位置為i的元素修改為元素e
* @param index 元素的索引位置
* @param e 需要修改成的元素
* @return true 修改成功標志
*/
public boolean set(int index, E e) {
validateIndex(index);
this.data[index] = e;
return true;
}
@Override
public String toString() {
return this.arrayToString(data);
}
/**
* @TODO 獲取字符串形式的順序表中的數組序列
* @param a 順序表中的數組
* @return String 字符串形式的順序表中的數組序列
*/
private String arrayToString(Object[] a) {
if (a == null)
return "null";
int iMax = this.size - 1;
if (iMax == -1)
return "[]";
StringBuilder b = new StringBuilder();
b.append('[');
for (int i = 0;; i++) {
b.append(String.valueOf(a[i]));
if (i == iMax)
return b.append(']').toString();
b.append(", ");
}
}
/**
* @TODO 驗證所給索引位置是否合法
* @param index 給出的索引位置
*/
private void validateIndex(int index) {
if (index >= this.size || index <= 0) {
throw new RuntimeException("數組下標錯誤：" + index);
}
}
/**
* @TODO 判斷是否需要擴充順序表容量
* @param currentSize 當前順序表的大小
*/
private void ensureSize(int currentSize) {
if (currentSize == capacity) {
this.capacity = (this.capacity * 3) / 2 + 1;
Object[] newData = new Object[this.capacity];
for (int i = 0; i < currentSize; i++) {
newData[i] = this.data[i];
}
this.data = newData;
}
}
}
主要注意上述3個私有成員變量，如下：
// 順序表長度
private int size;
// 順序表中數組的初始化長度
private int capacity;
// 順序表默認數組為null
private Object[] data = null;
如同注釋解釋的那樣，size用來表示順序表的長度，data用來表示數組,而capacity用來表示數組的長度.
相信data應該比較好理解，而對應的兩個長度變量相對難理解一些，下面解釋一下：
這裡主要講講順序表的插入和刪除：
順序表的插入演示如圖所示：
根據圖片可以看出插入一個元素後，插入位置之後的元素都需要向後移動一個位置。
刪除操作則是插入操作的逆過程，刪除位置之後的元素都需要向前移動一個位置。
時間復雜度分析：
解釋：上述的存入和插入有區別，存入表示存儲在數組末尾，而插入表示插入在任意位置。
優缺點分析：
優點：
可以快速的存取表中任意位置的元素。
缺點：
插入和刪除操作需要移動大量元素；
