內存

內存以1Byte=8bits來作為存儲單位。操作系統尋址最小單位為字節，一個字節為8bit。
一個整形int占4Byte.在計算機中占用內存如下：

0x01-0x04對應的內存存儲的就是整體int a，所以我們可以看到這時把它當作一個整體來對待。
如果是char類型則把2個byte來當作一個整體來對待，因為char占用2個byte
所以基本數據類型就是告訴內存應該如何存儲數據。

如果該數據結構是在內存中是連續存放的。則有如下結構

1. 順序表的形式（元素內置vs外置）

元素內置與外置主要區分的是是否存在與同一塊連續內存區而決定的 存儲元素類型是否相同 。

元素內置

將元素順序地存放在一塊連續的存儲區里，元素間的順序關系由它們的存儲順序自然表示。
下圖表示的是順序表的基本形式，數據元素本身連續存儲，每個元素所占的存儲單元大小固定相同。 例如java中的array元素類型要相同 。

依次把這組數據存入內存，這組數據變量名為Li，Li其實代表的就是起始地址0x23；地址占用內存統一的為4Byte。
這時我想去讀Li第0個元素為Li[0]。
而當我們要讀Li[3]，開始我們需要從頭開始找0x23往后走3步也就是走到 0x23+3*4Byte=0x35 ，到這個地址的時候就可以返回該地址存儲的值了。
這時我們就知道為何數組存儲要從Li[0]開始，這里的角標起始代表的就是偏移量，計算機通過偏移量來得到目標地址，如Li[3]就計算偏移量為3的地址。
故，訪問指定元素時無需從頭遍歷，通過計算便可獲得對應地址，其時間復雜度為O(1)。

元素外置

如果元素的大小不統一 如python中的list存儲元素類型可以不同。則須采用圖b的元素外置的形式，將實際數據元素另行存儲，而順序表中各單元位置保存對應元素的地址信息（即鏈接）。注意，圖b中的c不再是數據元素的大小，而是存儲一個鏈接地址所需的存儲量，這個量通常很小與int型一樣為4Byte。

找一個位置把每個數據存起來，但是每個數據的地址可以不連續。
這時每個地址指向對應數據，而這時我們找一塊連續的內存把每個數據的地址存儲起來。
這塊連續空間存儲全部都是地址，每個地址指向一個數據內存。
這時Li[0]為0x324地址，然后找到該地址中的數據0x100然后找到0x100指向的內存空間為數據12。
也就是把數據存儲到順序表之外，元素外置，可以存儲不同的數據類型。

圖b這樣的順序表也被稱為對實際數據的索引，這是最簡單的索引結構。

2. 順序表結構（一體式vs分離式）

一個順序表的完整信息包括兩部分，一部分是表中的 元素存儲區 ，另一部分為 表頭信息 ：主要包括元素存儲區的 容量 和當前表中 已存的元素個數 。
一體式和分離式主要決定的是 存儲區大小是否為固定的 。

一體式存儲

表頭信息和數據區一起存儲

存儲表信息的單元與元素存儲區以連續的方式安排在一塊存儲區里，兩部分數據的整體形成一個完整的順序表對象。
一體式結構整體性強，易于管理。但是由于數據元素存儲區域是表對象的一部分，順序表創建后，元素存儲區就固定了。 比如java中的數組。大小是固定的

更換數據

所以若想更換數據區，則只能整體搬遷，即整個順序表對象（指存儲順序表的結構信息的區域）改變了。

分離式存儲

表頭信息和存儲區分開存儲

采用分離式間接訪問，多了一次計算。
表對象里只保存與整個表有關的信息（即容量和元素個數），實際數據元素存放在另一個獨立的元素存儲區里，通過鏈接與基本表對象關聯。 類似于java的List
為了考慮數據動態變化，盡量使用分離式。

更換數據

若想更換數據區，只需將表信息區中的數據區鏈接地址更新即可，而該順序表對象不變。
人們把采用這種技術實現的順序表稱為動態順序表，因為其容量可以在使用中動態變化。

數據區擴充

當進行存儲區擴充時，相當于新建一個存儲區，但是新建這個存儲區究竟要多大。
擴充的兩種策略：

1. 每次擴充 增加固定數目 的存儲位置，如每次擴充增加10個元素位置，這種策略可稱為線性增長。特點：節省空間，但是擴充操作頻繁，操作次數多。
2. 每次 擴充容量加倍 ，如每次擴充增加一倍存儲空間。特點：減少了擴充操作的執行次數，但可能會浪費空間資源。以空間換時間， 推薦的方式 。

3. 順序表的操作

增加元素

當我們容量為8，現在數字為4，我們想添加一個元素111時：

1. 尾端加入元素，直接加，時間復雜度為O(1)
2. 非保序的加入元素（不常見），時間復雜度為O(1)
3. 保序的元素插入，插入到[1]到位置，我們需要把111放到位置[1]，后面的元素都需要向后移一位。
   比如我們要插入隊頭，那么后面元素都向后移一位，也就是操作n次，那么時間復雜度為O(n)。、

刪除元素

1. 刪除表尾元素，時間復雜度為O(1)
2. 非保序的元素刪除（不常見），時間復雜度為O(1)
3. 保序的元素刪除，表頭刪除之后，其他元素都向前提一位，時間復雜度為O(n)

4. python中的順序表

Python中的list和tuple兩種類型采用了順序表的實現技術，tuple是不可變類型，即不變的順序表，因此不支持改變其內部狀態的任何操作，而其他方面，則與list的性質類似。

List的基本實現技術

Python標準類型list就是一種元素個數可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：

• 基于下標（位置）的高效元素訪問和更新，時間復雜度應該是O(1)；
  為滿足該特征，應該采用順序表技術，表中元素保存在一塊連續的存儲區中，采用元素外置。
• 允許任意加入元素，而且在不斷加入元素的過程中，表對象的標識（函數id得到的值）不變。
  為滿足該特征，就必須能更換元素存儲區，并且為保證更換存儲區時list對象的標識id不變，只能采用分離式實現技術。

在Python的官方實現中，list就是一種采用 分離式技術實現的動態順序表 。這就是為什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

在Python的官方實現中，list實現采用了如下的策略：在建立空表（或者很小的表）時，系統分配一塊能容納8個元素的存儲區；在執行插入操作（insert或append）時，如果元素存儲區滿就換一塊4倍大的存儲區。但如果此時的表已經很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現過多空閑的存儲位置。