[[407946]]

本文轉載自微信公眾號「前端萬有引力」，作者一川。轉載本文請聯系前端萬有引力公眾號。

寫在前面

對于開發而言，數組是我們經常打交道的數據類型，那么它的內部存儲結構是怎樣的呢?我們將進行詳細介紹。

線性表

線性表是最基本、最簡單，也是最常用的一種數據結構，線性表就是n個具有相同特性的數據元素的有序數列。

前驅元素：若A元素在B元素的前面，則稱A為B的前驅元素。

后驅元素：若B元素在A元素的后面，則稱B為A的后驅元素。

線性表的分類：線性表中數據存儲的方式是分為順序存儲和鏈式存儲，其中：

• 順序存儲是用一段地址連續的存儲單元依次存儲線性表的數據元素。
• 鏈式存儲是用一段地址不連續的存儲單元存儲數據，而使用結點進行連接查詢地址。

隨機訪問：由于線性表存儲在連續的內存位置，因此可以通過它們的索引來計算內存地址，以便隨機訪問數據。

順序表

順序表的存儲方式其實就是在內存中找到空位置后進行占位，然后將數據元素依次進行存放到空位置。

是不是聽起來有點像數組的結構，對的，數據就是一種線性表結構。因此我們可以使用數組進行表示順序表，線性表在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，即通過數據元素物理存儲的相鄰關系來反映數據元素間邏輯上的相鄰關系。

數組的長度是存放線性表的存儲空間的長度，分配存儲后這個量一般是不變的。線性表的長度是線性表中數據元素的個數，隨著線性表中插入和刪除操作的進行，這個量是變化的。切記，在任何時刻線性表的長度應該小于等于數組的長度。

class SequenceList{ 
  
  constructor(){ 
    // 存儲元素的數組 
    this.elemList = []; 
    // 當前順序表中的元素個數 
    this.elemLength = 0; 
  } 
  // 將一個線性表置為空表 
  clear(){ 
    this.elemLength = 0; 
  } 
  // 判斷當前線性表是否為空表 
  isEmpty(){ 
    return this.elemLength === 0; 
  } 
  // 獲取當前線性表的長度 
  length(){ 
    return this.elemLength; 
  } 
  // 向線性表中添加元素 
  insert(elem){ 
    this.elemList[this.elemLength++] = elem; 
  } 
 
  // 在第i個元素插入元素elem 
  insertIndex(i,elem){ 
    // 先將i索引位置的元素及其后面位置的元素依次向后移動一位 
    for(let index = this.elemLength - 1; index > i; index--){ 
      this.elemList[index] = this.elemList[index-1]; 
    } 
    // 把elem元素存放在i索引位置 
    this.elemList[i] = elem; 
  } 
 
  // 刪除指定位置i處的元素后，返回該元素 
  remove(i){ 
    // 記錄索引i處的值 
    let current = this.elemList[i]; 
    // 索引i后面元素依次向前移動一位即可 
    for(let index = i; index < this.elemList - 1; index++){ 
      this.elemList[index] = this.elemList[index+1]; 
    } 
    // 元素個數-1 
    this.elemLength--; 
    return current; 
  } 
 
  // 查找elem元素首次出現在順序表的位置 
  indexOf(elem){ 
    for(let i = 0; i< this.elemLength; i++){ 
      if(this.elemList[i] === elem){ 
        return i; 
      } 
      return -1; 
    } 
  } 
} 

數組的優缺點

優點：

• 在內存空間的利用率高
• 查詢元素效率高，通過元素下標進行存取

缺點：

• 插入和刪除元素效率低。(在數組中間插入或刪除元素時，需要先移動遍歷整個表才能操作元素并重新排序)
• 有空間長度限制，不能擴增線性表長度。(當存取元素長度大于順序表的元素個數時，會出現“溢出”;當元素長度小于預先分配的空間時，空間浪費嚴重)

小結

本篇文章是《懂點算法》系列的第二篇文章，主要講述的線性表的第一類順序存儲，以及介紹了如何實現順序存儲。