线性表指的是由有限个数据元素组成的序列。
而顺序存储结构的线性表则表示逻辑上连续的序列，在物理存储上也是连续的。通常用数组来表示。
首先定义顺序线性表类,属性及其构造方法；
public class LinearList<T> {
// number of elements in list.
int length;
//elements
T[] items;
/**
* dynamic arguments constructor.
* @param t elements list
*/
public LinearList(T... t) {
length = t.length;
items = t;
}
/**
* non-argument constructor.
*/
public LinearList() {}
}
对于无参数的构造方法执行后，需要通过初始化方法来生成空表；
/**
* initiate empty linear list.
* @param size size of initialized list
*/
public void initiate(int size) {
length = 0;
items = (T[]) new Object[size];
}
顺序存储线性表是随机访问的，可通过索引直接访问指定位置元素；
/**
* get the element of specific index.
* @param idx specific index
* @return element
*/
public T get(int idx) {
if (idx >= 0 && idx < length) {
return items[idx];
} else {
throw new IndexOutOfBoundsException("index:" + idx + " is not valid, index should be between 0 to (not include) length:" + length);
}
}
同样可直接访问指定位置元素的前驱和后继；
/**
* get the prior element of the specific index.
* @param idx specific index
* @return prior element
*/
public T getPrior(int idx) {
if (idx > 0 && idx < length) {
return items[idx - 1];
}
return null;
}
/**
* get the next element of the specific index
* @param idx specific index
* @return next element
*/
public T getNext(int idx) {
if (idx >= 0 && idx < length - 1) {
return items[idx + 1];
}
return null;
}
提供查询指定元素的索引地址，如果表中无指定查询元素则返回-1；
/**
* get the index of the specific element.
* @param t element needs locate
* @return the index of the specific element
*/
public int locate(T t) {
for (int idx = 0; idx < length; idx++) {
if (items[idx].equals(t)) {
return idx;
}
}
return -1;
}
提供插入新元素方法，如果插入位置在表末尾，则在存储空间足够的情况下，在末尾直接插入；如果插入位置在表中间，则需要将插入位置之后的元素依次向后移动，在插入位置空出来之后将新元素插入。
/**
* insert element at specific position.
* @param idx the index to insert
* @param t the element to be insert
*/
public void insert(int idx, T t) {
if (length == items.length) {
enlarge();
}
if (idx >= 0 && idx <= length) {
T[] temp = (T[]) new Object[length - idx];
for (int i = 0, j = idx; j < length; i++, j++) {
temp[i] = items[j];
}
items[idx] = t;
length += 1;
for (int i = 0, j = idx + 1; i < temp.length; i++, j++) {
items[j] = temp[i];
}
}
}
/**
* insert at tail
* @param t the element to be insert
*/
public void insert(T t) {
insert(length, t);
}
当表存储满插入元素前，通过enlarge方法扩展表存储空间，扩充空间后需要将原表中的元素重新拷贝至新存储空间的对应位置；
/**
* enlarge size of list as double of the length.
*/
public void enlarge() {
enlarge(length);
}
/**
* enlarge size of list with specific.
* @param expendSize
*/
public void enlarge(int expendSize) {
T[] temp = items;
items = (T[]) new Object[items.length + expendSize];
for (int idx = 0; idx < length; idx++) {
items[idx] = temp[idx];
}
}
还有表清空、判空等操作，比较简单；
/**
* if the list is empty.
* @return true or false
*/
public boolean isEmpty() {
return length == 0 ? true : false;
}
/**
* set list as empty.
*/
public void clear() {
for (int i = 0; i < length; i++) {
items[i] = null;
}
length = 0;
}
表之间的聚合操作（剔除重复元素）；
/**
* merge lists
* @param l2 another list
* @return new list contains l1 and l2 non-duplicated elements
*/
public LinearList<T> union(LinearList<T> l2) {
LinearList<T> temp = this;// new LinearList<>();
//temp.initiate(this.length + l2.length);
temp.enlarge(l2.length);
for (int l2Idx = 0; l2Idx < l2.length; l2Idx++) {
T element = l2.get(l2Idx);
if(temp.locate(element) == -1) {
temp.insert(element);
}
}
return temp;
}
