(java實現)順序表-ArrayList
- 2019 年 10 月 3 日
- 筆記
什麼是順序表
順序表是在電腦記憶體中以數組的形式保存的線性表，是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。
在使用順序表存儲數據前，會先申請一段連續的記憶體空間（即數組），然後把數組依次存入記憶體，中間沒有一點空隙。
基本操作
每個數據結構都有集合對數據處理的方法，這能讓我們更方便的使用保存在數據結構中的數據。順序表的基本操作有：增（add)，刪(remove)，改(set)，查（find)，插(insert)等。
在這裡我們只詳細講解remove 和 insert 操作，其他實現可看下面的源碼。
順序表刪除元素
從順序表中刪除指定元素，實現起來非常簡單，只需找到目標元素，並將其後續所有元素整體前移 1 個位置即可。
後續元素整體前移一個位置，會直接將目標元素刪除，可間接實現刪除元素的目的。
例如：從順序表{1,2,3,4,5}中刪除元素3的過程如下
時間複雜度分析：從順序表中刪除元素，最好的情況是刪除的元素剛好是最後一個元素，這時候不需要移動元素，只需要把順序表的size-1即可,時間複雜度是O(1)。最壞的情況是刪除的元素剛好是第一個元素，這個時候就需要後面的元素全部向前移動一位，同時size-1,時間複雜度是O(N)。我們分析時間複雜度的原則是分析最壞情況，這樣才有意義。因此刪除操作的時間複雜度為O(N)。
順序表插入元素
向已有順序表中插入數據元素，根據插入位置的不同，可分為以下 3 種情況：
- 插入到順序表的表頭；
- 在表的中間位置插入元素；
- 尾隨順序表中已有元素，作為順序表中的最後一個元素；
雖然數據元素插入順序表中的位置有所不同，但是都使用的是同一種方式去解決，即：通過遍歷，找到數據元素要插入的位置，然後做如下兩步工作：
- 將要插入位置元素以及後續的元素整體向後移動一個位置；
- 將元素放到騰出來的位置上；
例如，在 {1,2,3,4,5} 的第 3 個位置上插入元素 6，實現過程如下：
時間複雜度分析同刪除元素一樣，均為O(N).
順序表的優劣和應用情形
優勢
- 因為數據在數組中按順序存儲，可以通過數組下標直接訪問，因此順序表查找定位元素很快
劣勢
- 插入和刪除元素需要大量的操作
- 因為數組在聲明時需要確定長度，因此順序表的長度是確定的。若需要擴大順序表長度，有需要大量的操作，不夠靈活。（將該數組copy到另外一個數組）
- 由於數據大小的不可測性，有時會浪費掉大量的空間
應用情形
- 總而言之，順序表適用於那些不需要對數據進行大量改動的結構
源碼實現（java)
public class MyArrayList<AnyType> { public int AMOUNT=10;//初始長度 public static int index;//表位置 AnyType[] myList; public MyArrayList(){ initList(); } //初始化順序表 public void initList(){ myList=(AnyType[])new Object[AMOUNT]; index=0; } //判斷順序表是否為空 public boolean listEmpty(){ if(index==0){ return true; } return true; } //清空順序表 public boolean clearList(){ myList=null; index=0; return true; } //返回i位置的元素 public AnyType get(int i){ if(i<0||i>=index){ throw new ArrayIndexOutOfBoundsException(); } return myList[i]; } //在i位置加入元素，即插入操作，這裡我沒有用insert命名 public void add(int i,AnyType a){ if(i<0||i>index){ throw new ArrayIndexOutOfBoundsException(); } if (i==index){ largeList(); } for(int k=index;k>i;k--){ myList[k]=myList[k-1]; } myList[i]=a; index++; } //在結尾增添元素a public void add(AnyType a){ add(index,a); } //為i位置元素重新賦值 public AnyType set(AnyType a,int i){ if(i<0||i>=index){ throw new ArrayIndexOutOfBoundsException(); } AnyType old=myList[i]; myList[i]=a; return old; } //列印遍歷順序表 public void print(){ String s="["; for(int i=0;i<index;i++){ s=s+myList[i]; s=s+" ,"; } System.out.println(s); } //查找a元素是否在表中，返回位置，沒有返回0 public int locateElem(AnyType a){ for(int i=0;i<index;i++){ if(a==myList[i]){ return i+1; } } return 0; } //返回表長 public int length(){ return index; } //刪除i位置元素 public AnyType delete(int i){ if(i<0||i>=index){ throw new ArrayIndexOutOfBoundsException(); } AnyType old=myList[i]; for(int k=i;k<index;k++){ myList[k]=myList[k+1]; } index--; return old; } //擴大表的最大長度 public void largeList(){ AnyType[] newList=(AnyType[])new Object[2*length()+1]; for(int i=0;i<index;i++){ newList[i]=myList[i]; } myList=newList; } }