java登神之階之順序表

一、了解List接口

在Java中，List接口是一個非常重要的集合框架接口，它繼承自Collection接口（Collection接口繼承Iterable接口）。List接口定義了一個有序集合，允許我們存儲元素集合。并且可以根據元素的索引來訪問集合中的元素。這意味著List中的每個元素都有其固定的位置，可以通過索引來訪問和修改。

List接口的實現類有很多，其中最常用的有ArrayList和LinkedList。它們各自有不同的特點和性能表現：

ArrayList：基于動態數組的實現，隨機訪問性能很好，但在列表的開頭和中間插入、刪除元素時性能較差，因為需要移動其他元素。
LinkedList：基于鏈表的實現，在插入、刪除元素時性能較好，尤其是當這些操作發生在列表的開頭或中間時，但在隨機訪問元素時性能較差。

二、順序表

2.1 線性表

線性表是n個具有相同特征的數據元素的

有限序列。線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表，鏈表，棧，隊列…
線性表在邏輯上時線性結構，也就是說連續的一條直線。但是在物理結構上并不一定是連續的。線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。

2.2 順序表

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲，在數組上完成增刪改查。

?粗略了解

public interface IList {//給數組增加新元素public void add(int data);//判斷數組數據是否為滿boolean isFull();// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某個元素public boolean contains(int toFind);// 查找某個元素對應的位置public int indexOf(int toFind);// 獲取 pos 位置的元素public int get(int pos);// 給 pos 位置的元素設為 valuepublic void set(int pos, int value);//刪除第一次出現的關鍵字keypublic void remove(int toRemove);// 獲取順序表長度public int size() ;// 清空順序表public void clear();// 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測試結果給出的public void display() ;
}

細節實現?

判斷是否滿

    @Overridepublic boolean isFull() {//相等返回true；反之，返回falsereturn useSize== array.length;}

給數組增加新元素?

    public void add(int data) {//首先需要先判斷數組是否已經存滿if(isFull()){grow();}array[useSize]=data;useSize++;}

在 pos 位置新增元素

這里需要先考慮插入數組下標是否合理，所以需要自己寫一個自定義異常！

//自定義的數組下標插入異常
class PosExpection extends RuntimeException{public PosExpection(String message){super(message);}
}
//自定義的異常：判斷數組是否為空
class EmptyException extends RuntimeException{public EmptyException(String message){super(message);}
}

    //這個是私有方法，只是為了在這個類中檢查數組下標是否合理，// 所以用private修飾private void checkPos(int pos) throws PosExpection{if(pos < 0 || pos >= useSize){throw new PosExpection("數組下標異常");}}@Overridepublic void add(int pos, int data) {try {checkPos(pos);//如果插入數組下表沒問題，則判斷是否需要擴容if(isFull()){grow();}}catch (PosExpection e){System.out.println("插入數組下標不合理...");e.printStackTrace();}//這里挪動數組，將Pos下標之后的數組往后挪for (int i = useSize-1; i >=pos ; i--) {array[i+1]= array[i];}array[pos]=data;}

判定是否包含某個元素

    @Overridepublic boolean contains(int toFind) {for (int i = 0; i < useSize; i++) {if(array[i]==toFind){return true;}}return false;}

查找某個元素對應的位置

    @Overridepublic int indexOf(int toFind) {for (int i = 0; i < useSize; i++) {if(array[i]==toFind){return i;}}return 0;}

獲取 pos 位置的元素

    @Overridepublic int get(int pos) {try {checkPos(pos);return array[pos];}catch (PosExpection e){System.out.println("數組下標不合理...");e.printStackTrace();}return 0;}

給 pos 位置的元素設為 value

    public void set(int pos, int value) {try {checkPos(pos);array[pos]=value;}catch (PosExpection e){System.out.println("數組下標不合理...");e.printStackTrace();}}

刪除第一次出現的關鍵字key

    @Overridepublic void remove(int toRemove) {int pos=indexOf(toRemove);if(pos==-1){return;}for (int i = pos; i <useSize-1 ; i++) {array[i]=array[i+1];}useSize--;}

獲取順序表長度

    @Overridepublic int size() {return useSize;}

清空順序表

     // 清空順序表public void clear() {for (int i = 0; i < this.usedSize; i++) {this.elem[i] = 0;}this.usedSize = 0; // 注意有效數組長度也要清零}

打印順序表

?@Overridepublic void display() {for (int i = 0; i < useSize; i++) {System.out.print(array[i]+" ");}//這里不能for-each遍歷,// 用for-each遍歷不管數組里面有沒有數據，都會遍歷出和數組大小一樣的元素，對應下標沒有元素會用0來代替。
//        for (int x:
//             array) {
//            System.out.println(x+" ");
//        }}?

三、ArrayList類

在集合框架中，ArrayList是一個類，實現了List接口。
ArrayList實現了List接口，而List接口在數據結構的角度上就是線性表的一種抽象。因此，ArrayList可以看作是順序表在Java集合框架中的一種具體實現。

ArrayList是通過泛型的方式實現的，使用前必須先實例化。
ArrayList實現了RandomAccess接口，表明ArrayList類支持隨機訪問。
ArrayLIst實現了Cloneable接口，表明ArrayLIst支持Clone的。
ArrayLIst實現了Serializable接口，表明ArrayLIst支持可序列化。
ArrayLIst不是線程安全的，在單線程下是可以使用的。
ArrayLIst是一段連續的空間，并且可以動態擴容，是一個動態類型的線性表

ArrayLIst方法

構造方法

public static void main(String[] args) {
// ArrayList創建 ，推薦寫法 // 構造一個空的列表List<Integer> list1 = new ArrayList<>();
// 構造一個具有10個容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);
// list2.add("hello");  // 編譯失敗 ， List<Integer>已經限定了 ，list2中只能存儲整形元素
// list3構造好之后 ，與list中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略類型 ，否則 ：任意類型的元素都可以存放 ，使用時將是一場災難List list4 = new ArrayList();list4.add("111");list4.add(100);
}

?常用方法

?

public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("JavaSE");list.add("JavaWeb");list.add("JavaEE");list.add("JVM");list.add("測試課程");System.out.println(list);
// 獲取list中有效元素個數System.out.println(list.size());
// 獲取和設置index位置上的元素 ，注意index必須介于[0, size)間System.out.println(list.get(1));list.set(1, "JavaWEB");System.out.println(list.get(1));
// 在list的index位置插入指定元素 ，index及后續的元素統一往后搬移一個位置list.add(1, "Java數據結構");System.out.println(list);
// 刪除指定元素 ，找到了就刪除 ，該元素之后的元素統一往前搬移一個位置list.remove("JVM");System.out.println(list);
// 刪除list中index位置上的元素 ，注意index不要超過list中有效元素個數,否則會拋出下標越界異常list.remove(list.size() - 1);System.out.println(list);
// 檢測list中是否包含指定元素 ，包含返回true ，否則返回falseif (list.contains("測試課程")) {list.add("測試課程");}
// 查找指定元素第一次出現的位置：indexOf從前往后找 ，lastIndexOf從后往前找list.add("JavaSE");System.out.println(list.indexOf("JavaSE"));System.out.println(list.lastIndexOf("JavaSE"));
// 使用list中[0, 4)之間的元素構成一個新的SubList返回,但是和ArrayList共用一個elementData數組List<String> ret = list.subList(0, 4);System.out.println(ret);list.clear();System.out.println(list.size());
}

?ArrayList的遍歷
ArrayList 可以使用三方方式遍歷： for循環+下標、foreach、使用迭代器

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);
// 使用下標+for遍歷for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();
// 借助foreach遍歷for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();Iterator<Integer> it = list.listIterator();while (it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();
}

ArrayList的擴容機制?

ArrayList是一個動態類型的順序表，即：在插入元素的過程中會自動擴容。以下是ArrayList源碼中擴容方式：
源碼理解：

Object[] elementData;  // 存放元素的空間
private static ? nal
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默認空間 private static ? nalint DEFAULT_CAPACITY = 10;  // 默認容量大小public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!! elementData[size++] = e;return true;
}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// over?ow-conscious codeif (minCapacity - elementData.length > 0) grow(minCapacity);
}private static ? nalint
MAX_ARRAY_SIZE =Integer.MAX_VALUE -8;private void grow(int minCapacity) {
// 獲取舊空間大小int oldCapacity = elementData.length;
// 預計按照1.5倍方式擴容int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果用戶需要擴容大小 超過 原空間1.5倍 ，按照用戶所需大小擴容if (newCapacity - minCapacity < 0)newCapacity = minCapacity;
// 如果需要擴容大小超過MAX_ARRAY_SIZE ，重新計算容量大小if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);
// 調用copyOf擴容elementData = Arrays.copyOf(elementData, newCapacity);
}private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0 ，拋出OutOfMemoryError異常if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}