線性表：零個或多個數據元素的有限序列

線性表的數據對象集為{a 1 , a 2 , ……, a n }，每個數據元素的類型相同。其中，除了第一個元素 a1 之外，每個元素都有并且只有一個直接前驅元素，除了最后一個元素 a n之外，每個元素都有并且只有一個直接后繼元素。數據元素之間的關系是一對一的。

線性表的訂單存儲結構

線性表的數據元素一次存儲在具有連續地址的存儲單元中

一個1一個2......一個i-1我_......一個_

順序存儲結構需要三個屬性：

存儲空間的起始位置：數據數據，其存儲位置為存儲空間的存儲位置。

直線米最大存儲容量：數組MaxSize的長度。

直線米的當前長度：長度。

內存地址計算方法

用數組存儲順序表意味著分配固定長度的數組空間，因為線性表可以插入或刪除，所以分配的數組空間應該大于等于當前線性表的長度。

記憶中的地址，就像圖書館的座位一樣，都是編號的。內存中的每個存儲單元都有自己的編號、地址。因為是順序結構，所以當第一個位置確定后，后面的位置就可以計算出來了。比如，我全班第五，排在我后面的是10，學生的成績是6,7,...,15，因為5+1,5+2,...,5+10。每一個數據元素，無論是整容、真實還是人物，都需要占用一定的存儲單元空間。假設占用c個存儲單元，那么線性表中第二個i+1個數據元素的存儲位置和i個數據元素的存儲位置滿足如下關系：

LOC (a i + 1 ) = LOC (a i ) + c

所以對于第 i 個數據元素 a i的存儲位置可以有一個1計算得到：

LOC (a i ) = LOC (a 1 ) + (i-1) * c

通過這個公式，可以同時計算出線性表中任意位置的地址，任意位置，全部。它的時間復雜度是 O(1)。一般將具有這種特性的存儲結構稱為隨機存取結構。

順序存儲結構的插入和刪除

1.獲取元素操作碼：

public class ArrayList<E> {
transient Object[] elementData;
public E get(int index) {
Objects.checkIndex(index, this.size);
return this.elementData(index);
}
E elementData(int index) {
return this.elementData[index];
}
}
 Copy code 

2.插入

比如，買春運火車票。每個人都排好隊。這位是美女，說……對排隊的第三個人，“大哥，請幫幫我，我媽在家病了，趕緊回去看看她，隊伍這么長，能不能把我放進去在你面前?”你心軟，答應了。身后的人都不得不退后一步。這個例子實際上已經說明了線性表的順序存儲結構，插入數據時的實現過程。

插入思路：

如果插入位置不合理，拋出異常;

如果線性表長度大于等于數組長度，則拋出異常或動態增加容量;

從最后一個元素開始，向前遍歷到下一個 i A 地方，將它們分別向后移動一個位置;

填入要插入元素的位置i，Watch長度加1。

代碼實現：

public boolean add(E e) {
++this.modCount;
this.add(e, this.elementData, this.size);
return true;
}
public void add(int index, E element) {
this.rangeCheckForAdd(index);
++this.modCount;
int s;
Object[] elementData;
if ((s = this.size) == (elementData = this.elementData).length) {
elementData = this.grow();
}
System.arraycopy(elementData, index, elementData, index + 1, s - index);
elementData[index] = element;
this.size = s + 1;
}
 Copy code 

3.刪除操作

接下來，我們以上面的例子為例。這時，一名警察出現了，對美女說道：“跟我去局。” 女人離開了隊伍。原來，她是個賣火車票的黃牛，裝窮排隊買票。然后排隊的人，都往前邁了一步。這是在線性表的順序存儲結構中刪除元素的過程。

刪除想法：

如果刪除位置不合理，則拋出異常;

移除刪除元素;

從被刪除元素位置遍歷到最后一個元素位置，分別向前移動一個位置;

手表長度減 1。

代碼實現：

public E remove(int index) {
Objects.checkIndex(index, this.size);
Object[] es = this.elementData;
E oldValue = es[index];
this.fastRemove(es, index);
return oldValue;
}
 Copy code 

插入和刪除的時間復雜度。

最好的情況，如果要將元素插入到最后一個位置，或者刪除最后一個元素，此時時間復雜度為O(1)，因為不需要移動元素。

最壞的情況，如果要插入元素到第一個位置或者要刪除第一個元素，此時時間復雜度為O(n)，因為它向后或向前移動了1個位置之后的所有元素。

至于一般情況，因為元素插入到了第i個A地方，或者刪除了第i個元素，需要移動ni個元素。根據概率原理，在每個位置插入或刪除元素的可能性是相同的，也就是說，位置在前面，移動更多元素，位置向后，移動元素更少。最終平均移動次數等于中間元素的移動次數，乘以(n-1)/2，即O(n)。

分析表明，線性表的順序存儲結構，在存在、讀取數據時，無論在哪里，時間復雜度為零O(1);插入或刪除時，時間復雜度為零O(n)。說明它更適合，元素數量不變，訪問數據的應用也更多。

線性表順序存儲結構的優缺點

優勢 ：

無需為表中元素之間的邏輯關系增加額外的存儲空間

您可以快速檢索表格中任何位置的元素

缺點：

插入和刪除操作需要移動大量元素

當延米長度變化較大時，存儲空間的容量難以確定

創造存儲空間“碎片”

以上就是關于“線性表的順序存儲結構詳解”的介紹，大家如果對此比較感興趣，想了解更多相關知識，不妨來關注一下動力節點的Java在線學習，里面的課程內容從入門到精通，很適合沒有基礎的小伙伴學習，希望對大家能夠有所幫助。