package SequenceList;

import java.util.Arrays;

public class SequenceList<T> {

    private 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++;
    }
    
    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的元素
    @SuppressWarnings("unchecked")
    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){
            while(capacity < minCapacity){
                capacity <<= 1;
            }
            elementData = Arrays.copyOf(elementData, capacity);
        }
    }
    
    @SuppressWarnings("unchecked")
    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);
        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();
        }
    }
}

package SequenceList;

public class SequenceListTest {

    public static void main(String[] args) {
        SequenceList<String> list = new SequenceList<String>();
        list.add("aaaa");
        list.add("bbbb");
        list.add("cccc");
        list.insert("dddd", 1);
        System.out.println(list);
        list.delete(2);
        System.out.println(list);
        System.out.println("cccc在线性表中的位置： " + list.locate("cccc"));
    }

}

[aaaa, dddd, bbbb, cccc]
[aaaa, dddd, cccc]
cccc在线性表中的位置： 2