package com.ietree.basic.datastructure.Sequence;

import java.util.Arrays;

/**
 * 順序線性表
 * 
 * @param <T>
 * @author Dylan
 */
public class SequenceList<T> {

 private final int DEFAULT_SIZE = 16;
 // 保存數(shù)組的長度
 private int capacity;
 // 定義一個數(shù)組用于保存順序線性表的元素
 private Object[] elementData;
 // 保存順序表中元素的當前個數(shù)
 private int size = 0;
 
 // 以默認數(shù)組長度創(chuàng)建順序線性表
 public SequenceList() {
  capacity = DEFAULT_SIZE;
  elementData = new Object[capacity];
 }
 
 // 以一個初始化元素創(chuàng)建順序線性表
 public SequenceList(T element) {
  this();
  elementData[0] = element;
  size++;
 }
 
 /**
  * 以指定長度的數(shù)組來創(chuàng)建順序線性表
  * @param element 指定順序線性表中第一個元素
  * @param initSize 指定順序線性表底層數(shù)組的長度
  */
 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處的元素
 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++;
 }
 
 // 在插入元素之前需要確保順序線性表的長度大于插入之后順序線性表的長度
 private void ensureCapacity(int minCapacity) {
  
  // 如果數(shù)組的原有長度小于目前所需的長度
  if (minCapacity > capacity) {
   // 不斷地將capacity * 2，直到capacity大于minCapacity
   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);
  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 com.ietree.basic.datastructure.Sequence;

/**
 * 測試類
 * 
 * @author Dylan
 */
public class SequenceListTest {
 
 public static void main(String[] args) {
  SequenceList<String> list = new SequenceList<String>();
  list.add("aaa");
  list.add("bbb");
  list.add("ccc");
  list.add("ddd");
  list.insert("eee", 1);
  System.out.println(list);
  list.delete(2);
  System.out.println(list);
  System.out.println("ccc在順序線性表中的位置：" + list.locate("ccc"));
 }
}

[aaa,eee,bbb,ccc,dd]
[aaa,eee,ccc,dd]