什么是List

在集合框架中，List是一個接口，繼承自Collection。

Collection也是一個接口，該接口中規范了后序容器中常用的一些方法，具體如下所示：

Iterable也是一個接口，表示實現該接口的類是可以逐個元素進行遍歷的，具體如下：

List 的官方文檔

站在數據結構的角度來看，List就是一個線性表，即n個具有相同類型元素的有限序列，在該序列上可以執行增刪改查以及變量等操作。

常見接口介紹

List中提供了好的方法，具體如下：

雖然方法比較多，但是常用方法如下：

注意：List是個接口，并不能直接用來實例化

線性表

線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列…

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲

順序表

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

在數組上完成數據的增刪查改。

順序表接口的實現

我們現在有這樣一個SepList接口為：

public interface SepList  {// 新增元素,默認在數組最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某個元素boolean contains(int toFind);// 查找某個元素對應的位置int indexOf(int toFind);// 獲取 pos 位置的元素int get(int pos);// 給 pos 位置的元素設為 valuevoid set(int pos, int value);//刪除第一次出現的關鍵字keyvoid remove(int key);// 獲取順序表長度int size();// 清空順序表void clear();
}

這里博主將在一個MyArrayList類里面實現這些接口

public class MyArrayList implements SepList  {private int[] elem;//數組private int usedSize;//記錄有效的數據的個數private static final int DEFAULT_SIZE = 10;//最初的數據容量public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}// 新增元素,默認在數組最后新增public void add(int data) { }// 在 pos 位置新增元素public void add(int pos, int data) { }// 判定是否包含某個元素public boolean contains(int toFind) { return true; }// 查找某個元素對應的位置public int indexOf(int toFind) { return -1; }// 獲取 pos 位置的元素public int get(int pos) { return -1; }// 給 pos 位置的元素設為 valuepublic void set(int pos, int value) { }//刪除第一次出現的關鍵字keypublic void remove(int key) { }// 獲取順序表長度public int size() { return 0; }// 清空順序表public void clear() { }
}

add在末尾新增元素

在增加一個元素前，我們需要對該順序表進行判斷，判斷是否已滿，若滿則需要進行擴容

每增加一個元素，我們我們記錄有效個數的usedSize加1

// 新增元素,默認在數組最后新增public void add(int data) {//判斷數組是否已經被裝滿if(usedSize >= this.elem.length) {//被裝滿后需要進行擴容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSize] = data;usedSize++;}

在 pos 位置新增元素

在增加一個元素前，我們需要對該順序表進行判斷，判斷是否已滿，若滿則需要進行擴容

我們還需要多pos進行一個判斷，判斷它是否合法，如果不合法，我們拋出異常進行提醒

在pos位置增加元素，需要將pos位置及以后的元素進行后移一位，然后再在pos位置新增元素

每增加一個元素，我們我們記錄有效個數的usedSize加1

//自定義異常
class PosWrongfulException extends RuntimeException {public PosWrongfulException(String message) {super(message);}
}// 在 pos 位置新增元素public void add(int pos, int data) throws PosWrongfulException {//判斷數組是否已經被轉滿if(usedSize >= this.elem.length) {//被裝滿后需要進行擴容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}if(pos < 0 || pos > this.usedSize) {System.out.println("pos位置不合法！");throw new PosWrongfulException("pos位置不合法");}for(int i = this.usedSize;i >= pos;i--) {//pos位置以及pos位置以后的數據整體進行后移this.elem[i] = this.elem[i-1];}this.elem[pos] = data;usedSize++;}

判定是否包含某個元素

遍歷即可

// 判定是否包含某個元素public boolean contains(int toFind) {for(int i = 0;i < this.usedSize;i++) {if(this.elem[i] == toFind) {return true;}}return false;}

查找某個元素對應的位置

對數組進行遍歷，有的話返回相應的數組下標就好，沒有返回-1

// 查找某個元素對應的位置public int indexOf(int toFind) {for(int i = 0;i < this.usedSize;i++) {if(this.elem[i] == toFind) {return i;}}return -1;}

獲取 pos 位置的元素

獲取前我們得進行判斷，該順序表類元素不能為空

我們還得對pos進行是否合法得判斷

//自定義的異常
class PosWrongfulException extends RuntimeException {public PosWrongfulException(String message) {super(message);}
}
class EmptyException extends RuntimeException {public EmptyException(String message) {super(message);}
}// 獲取 pos 位置的元素public int get(int pos)throws PosWrongfulException {if(this.usedSize == 0){throw new EmptyException("當前順序表為空！");}if(pos < 0 || pos > this.usedSize) {System.out.println("pos位置不合法！");throw new PosWrongfulException("pos位置不合法");}return this.elem[pos];}

給 pos 位置的元素設為 value

我們依舊需要判斷pos的合法性，前面已經自定義了該異常，這里就不再進行定義了

然后將pos位置的元素改為value就好

// 給 pos 位置的元素設為 valuepublic void set(int pos, int value) {if(pos < 0 || pos > this.usedSize) {System.out.println("pos位置不合法！");throw new PosWrongfulException("pos位置不合法");}this.elem[pos] = value;}

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

我們依舊需要判斷數組是否為空

遍歷數組，若沒有我們要刪除的元素，我們便進行提示后退出

若有，則只需要用后面的數據對前面進行覆蓋就好

 //刪除第一次出現的關鍵字keypublic void remove(int key) {if(this.usedSize == 0) {throw new EmptyException("順序表為空！");}int index = this.indexOf(key);if(index == -1) {System.out.println("沒有這個數字");return;}//進行覆蓋for (int i = index; i < size()-1; i++) {this.elem[i] = this.elem[i+1];}//如果不是基本類型，將usedSize下標置為空//this.elem[this.usedSize] = null;this.usedSize--;}

獲取順序表的長度

這個就非常簡單了，只需要返回usedSize就好

 // 獲取順序表長度public int size() {  return this.usedSize;}

清空順序表

對于當前基本類型的數據來說，只需要將usedSize置為0就好

 public void clear() {this.usedSize=0;}

順序表的優缺點

線性表的順序存儲結構，在存、讀數據時，不管是哪個位置，時間復雜度都是O(1)；而插入或刪除時，時間復雜度都是O(n)。這就說明，它比較適合元素個數不太變化，而更多是存取數據的應用。當然，它的優缺點還不只這些……

優點：

無需為表示表中元素之間的邏輯關系而增加額外的存儲空間可以快速地存取表中任一位置的元素

缺點：

插入刪除操作需要移動大量元素，當線性表長度變化較大時，難以確定存儲空間的容量，造成存儲空間的碎片

總結

關于《【數據結構】 List與順序表及接口的實現》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關注，點贊，收藏支持一下！