代碼如下:
import java.util.Arrays;
/**
* 順序線性表的實現
*/
public class LineList<E>{
private int size; //長度
private Object[] array; //底層數組
private final int default_length=16; //默認長度
/**
* 無參構造方法
*/
public LineList(){
size = 0;
//使用默認長度構造數組
array = new Object[default_length];
}
/**
* 指定長度進行構造
* @param length 指定初始長度
*/
public LineList(int length){
if(length<0){
throw new IllegalArgumentException("初始長度不合法:"+length);
}
//使用指定長度構造數組
array = new Object[length];
}
/**
* 指定初始化元素和長度進行構造
* @param element 初始化元素
* @param length 初始化長度
*/
public LineList(E element,int length){
if(length<1){
throw new IllegalArgumentException("初始長度不合法:"+length);
}
//使用指定長度構造數組
array = new Object[length];
//初始化第一個元素
array[0] = element;
size++;
}
/**
* 指定初始化元素進行構造
* @param element 初始化元素
*/
public LineList(E element){
//使用默認長度初始化數組
array = new Object[default_length];
//初始化第一個元素
array[0] = element;
}
/**
* 獲取元素個數
*/
public int size() {
return size;
}
/**
* 判斷是否為空
*/
public boolean isEmpty() {
return size==0;
}
/**
* 判斷是否包含此元素
*/
public boolean contains(E e) {
if(indexOf(e) == -1){
return false;
}
return true;
}
/**
* 格式化為數組
*/
public Object[] toArray() {
return Arrays.copyOf(array, size);
}
/**
* 向線性表尾部添加一個元素
* @param e
* @return
*/
public void add(E e) {
extendCapacity(size+1);
array[size]=e;
size++;
}
/**
* 擴容
* @param length 需要的長度
*/
private void extendCapacity(int length){
//當前數組長度和需要的長度取最大
int minCapacity = Math.max(array.length, length);
//判斷是否需要擴容
if(minCapacity - array.length>0){
//數組長度增加一半
int newLength = array.length + array.length/2;
//如果新的長度還比需求要小,將需求的長度作為數組長度
if(newLength < minCapacity){
newLength=minCapacity;
}
//數組長度不能超過Integer.Max_Value
if(newLength > Integer.MAX_VALUE - 8){
newLength = Integer.MAX_VALUE;
}
//數組擴容
array = Arrays.copyOf(array, newLength);
}
}
/**
* 從線性表中移除所有此元素
* @param e 需要移除的元素
* @return
*/
public void removeAll(E e) {
if(e==null){
for(int i=0;i<size;i++){
if(array[i]==null){
fastRemove(i);
}
}
}else{
for(int i=0;i<size;i++){
if(e.equals(array[i])){
fastRemove(i);
}
}
}
}
/**
* 刪除索引處元素,後面的元素依次前移
* @param index 需要刪除的索引
*/
private void fastRemove(int index){
if(size-index-1>0){
//數組從index+1開始全部前移
System.arraycopy(array, index+1, array, index, size-1);
}
//最後一個元素請空
array[--size]=null;
}
/**
* 清空線性表
*/
public void clear() {
//將數組全部填充為null
Arrays.fill(array, null);
//將元素個數改為0
size=0;
}
/**
* 獲得索引處的元素
* @param index
* @return 索引處的元素
*/
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
return (E)array[index];
}
/**
* 驗證是否為索引越界
* @param index
*/
private void checkIndex(int index){
if(index>=size || index<0){
throw new IndexOutOfBoundsException("索引越界");
}
}
/**
* 將索引處的元素修改為新的元素
* @param index 索引位置
* @param element 元素
* @return 原索引處的元素
*/
@SuppressWarnings("unchecked")
public E set(int index, E element) {
checkIndex(index);
E e = (E)array[index];
array[index]=element;
return e;
}
/**
* 在指定的索引處插入指定的元素
* @param index 索引位置
* @param element 元素
*/
public void add(int index, E element) {
//驗證索引
checkIndex(index);
//是否需要擴容
extendCapacity(size+1);
//復制數組
System.arraycopy(array, index, array, index+1, size-index);
array[index]=element;
}
/**
* 移除索引處的元素
* @param index 索引
* @return 刪除了的元素
*/
@SuppressWarnings("unchecked")
public E remove(int index) {
checkIndex(index);
//取得索引位置的元素
E e = (E)array[index];
fastRemove(index);
return e;
}
/**
* 取得元素第一次出現的位置的索引
* @param e 要查找的元素
* @return 如果為-1說明線性表沒有這個元素
*/
public int indexOf(E e) {
if(e==null){
for(int i=0;i<size;i++){
if(e==array[i]){
return i;
}
}
}
for(int i=0;i<size;i++){
if(e.equals(array[i])){
return i;
}
}
return -1;
}
/**
* 取得元素最後一次出現的位置的索引
* @param e 要查找的元素
* @return 如果為-1說明線性表沒有這個元素
*/
public int lastIndexOf(E e) {
//判斷元素是否為null
if(e==null){
for(int i=size-1;i>=0;i--){
if(e==array[i]){
return i;
}
}
}
for(int i=size-1;i>=0;i--){
//如果為null這裡會跑出NullPoint異常
//所以前面要加上驗證是否為Null
if(e.equals(array[i])){
return i;
}
}
return -1;
}
/**
* 截取線性表
* @param fromIndex 開始索引
* @param toIndex 結束索引
* @return 截取的線性表
*/
@SuppressWarnings("unchecked")
public LineList<E> subList(int fromIndex, int toIndex) {
//判斷開始索引是否越界
if(fromIndex<0 || fromIndex >=size){
throw new IndexOutOfBoundsException("開始索引越界:"+fromIndex);
}
//判斷結束索引是否越界
if(toIndex >=size || fromIndex <0){
throw new IndexOutOfBoundsException("結束索引越界:"+toIndex);
}
//判斷開始索引和結束索引是否正確
if(fromIndex > toIndex){
throw new IllegalArgumentException("參數不正確,開始索引應大於等於結束索引");
}
LineList<E> list = new LineList<E>();
for(int i=fromIndex,j=toIndex;i<=j;i++){
list.add((E)array[i]);
}
return list;
}
}