package com.example.list;
import java.util.Arrays;
import java.util.Objects;
public class SequenceList {
private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private Object[] elements;
private int size;
public SequenceList() {
this(DEFAULT_CAPACITY);
}
public SequenceList(int initialCapacity) {
if (initialCapacity < 0) throw new IllegalArgumentException("Capacity < 0");
elements = new Object[initialCapacity];
}
// 核心：擴容機制
private void ensureCapacity(int minCapacity) {
if (minCapacity > elements.length) {
int newCapacity = elements.length + (elements.length >> 1); // 1.5 倍
if (newCapacity < minCapacity) newCapacity = minCapacity;
if (newCapacity > MAX_ARRAY_SIZE) newCapacity = hugeCapacity(minCapacity);
elements = Arrays.copyOf(elements, newCapacity);
}
}
private int hugeCapacity(int minCapacity) {
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
// === 基本操作 ===
public int size() { return size; }
public boolean isEmpty() { return size == 0; }
// 尾部新增
public boolean add(E e) {
ensureCapacity(size + 1);
elements[size++] = e;
return true;
}
// 指定位置插入
public void add(int index, E e) {
checkIndexForAdd(index);
ensureCapacity(size + 1);
System.arraycopy(elements, index, elements, index + 1, size - index);
elements[index] = e;
size++;
}
// 獲取元素
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
return (E) elements[index];
}
// 設置元素
@SuppressWarnings("unchecked")
public E set(int index, E e) {
checkIndex(index);
E old = (E) elements[index];
elements[index] = e;
return old;
}
// 刪除指定位置
@SuppressWarnings("unchecked")
public E remove(int index) {
checkIndex(index);
E old = (E) elements[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elements, index + 1, elements, index, numMoved);
}
elements[--size] = null; // 幫助 GC
return old;
}
// 按元素刪除（首次出現）
public boolean remove(Object o) {
int index = indexOf(o);
if (index >= 0) {
remove(index);
return true;
}
return false;
}
// 查找首次出現索引
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (Objects.equals(o, elements[i])) return i;
}
return -1;
}
// 查找最後出現索引
public int lastIndexOf(Object o) {
for (int i = size - 1; i >= 0; i--) {
if (Objects.equals(o, elements[i])) return i;
}
return -1;
}
// 是否包含
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// 清空
public void clear() {
Arrays.fill(elements, 0, size, null);
size = 0;
}
// 轉陣列
@SuppressWarnings("unchecked")
public E[] toArray(E[] a) {
if (a.length < size) {
return (E[]) Arrays.copyOf(elements, size, a.getClass());
}
System.arraycopy(elements, 0, a, 0, size);
if (a.length > size) a[size] = null;
return a;
}
// 索引檢查
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkIndexForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 0; i < size; i++) {
sb.append(elements[i]);
if (i < size - 1) sb.append(", ");
}
sb.append(']');
return sb.toString();
}
} | 設計點 | 實現細節 | 理由 |
|---|---|---|
| 泛型擦除 | 內部用 Object[]，get/set 強轉 (E) | Java 不支援泛型陣列創建 |
| 擴容因子 | 1.5 倍 (length + length>>1) | 平衡記憶體浪費與擴容頻率 |
| System.arraycopy | 批量移動元素 | JVM 內建、原生優化、比手寫迴圈快 |
| 元素置 null | remove/clear 後 elements[i]=null | 避免「過期引用」阻礙 GC |
| 索引檢查分離 | checkIndex / checkIndexForAdd | 插入允許 index==size，其餘不允許 |
| toArray 泛型 | 傳入類型陣列，動態創建同類型 | 保留運行時類型資訊 |
public class SequenceListTest {
public static void main(String[] args) {
SequenceList list = new SequenceList<>(3);
// 基本增
list.add("A");
list.add("B");
list.add("C"); // 觸發擴容
list.add(1, "X"); // [A, X, B, C]
System.out.println("插入後: " + list);
// 查
System.out.println("索引 2: " + list.get(2)); // B
System.out.println("包含 X: " + list.contains("X"));
System.out.println("X 索引: " + list.indexOf("X"));
// 改
list.set(0, "Z"); // [Z, X, B, C]
System.out.println("修改後: " + list);
// 刪
list.remove(2); // [Z, X, C]
list.remove("X"); // [Z, C]
System.out.println("刪除後: " + list);
// 邊界
list.add(0, "HEAD");
list.add(list.size(), "TAIL");
System.out.println("邊界: " + list);
// 轉陣列
String[] arr = list.toArray(new String[0]);
System.out.println("陣列: " + Arrays.toString(arr));
}
} transient Object[] elementData 標記非序列化，自定義序列化邏輯// JMH 基準測試模板
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Thread)
public class ListBenchmark {
private SequenceList seqList;
private ArrayList arrayList;
@Setup
public void setup() {
seqList = new SequenceList<>();
arrayList = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
seqList.add(i);
arrayList.add(i);
}
}
@Benchmark
public void seqListGet() { for (int i=0;i<10000;i++) seqList.get(i); }
@Benchmark
public void arrayListGet() { for (int i=0;i<10000;i++) arrayList.get(i); }
@Benchmark
public void seqListAddMid() { seqList.add(5000, 999); }
@Benchmark
public void arrayListAddMid() { arrayList.add(5000, 999); }
} 順序表是「陣列動態化」的經典實現。**System.arraycopy + 1.5 倍擴容 + 及時置 null** 是三大核心技巧。手寫實現能深入理解 ArrayList 底層機制，為效能調優、面試應答、框架原理分析打下堅實基礎。生產環境請直接使用 java.util.ArrayList，它經過數十年打磨，處理了所有邊界情況與併發陷阱。
