內(nèi)存

內(nèi)存以1Byte=8bits來(lái)作為存儲(chǔ)單位。操作系統(tǒng)尋址最小單位為字節(jié)，一個(gè)字節(jié)為8bit。
一個(gè)整形int占4Byte.在計(jì)算機(jī)中占用內(nèi)存如下：

0x01-0x04對(duì)應(yīng)的內(nèi)存存儲(chǔ)的就是整體int a，所以我們可以看到這時(shí)把它當(dāng)作一個(gè)整體來(lái)對(duì)待。
如果是char類型則把2個(gè)byte來(lái)當(dāng)作一個(gè)整體來(lái)對(duì)待，因?yàn)閏har占用2個(gè)byte
所以基本數(shù)據(jù)類型就是告訴內(nèi)存應(yīng)該如何存儲(chǔ)數(shù)據(jù)。

如果該數(shù)據(jù)結(jié)構(gòu)是在內(nèi)存中是連續(xù)存放的。則有如下結(jié)構(gòu)

1. 順序表的形式（元素內(nèi)置vs外置）

元素內(nèi)置與外置主要區(qū)分的是是否存在與同一塊連續(xù)內(nèi)存區(qū)而決定的 存儲(chǔ)元素類型是否相同 。

元素內(nèi)置

將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示。
下圖表示的是順序表的基本形式，數(shù)據(jù)元素本身連續(xù)存儲(chǔ)，每個(gè)元素所占的存儲(chǔ)單元大小固定相同。 例如java中的array元素類型要相同 。

依次把這組數(shù)據(jù)存入內(nèi)存，這組數(shù)據(jù)變量名為L(zhǎng)i，Li其實(shí)代表的就是起始地址0x23；地址占用內(nèi)存統(tǒng)一的為4Byte。
這時(shí)我想去讀Li第0個(gè)元素為L(zhǎng)i[0]。
而當(dāng)我們要讀Li[3]，開(kāi)始我們需要從頭開(kāi)始找0x23往后走3步也就是走到 0x23+3*4Byte=0x35 ，到這個(gè)地址的時(shí)候就可以返回該地址存儲(chǔ)的值了。
這時(shí)我們就知道為何數(shù)組存儲(chǔ)要從Li[0]開(kāi)始，這里的角標(biāo)起始代表的就是偏移量，計(jì)算機(jī)通過(guò)偏移量來(lái)得到目標(biāo)地址，如Li[3]就計(jì)算偏移量為3的地址。
故，訪問(wèn)指定元素時(shí)無(wú)需從頭遍歷，通過(guò)計(jì)算便可獲得對(duì)應(yīng)地址，其時(shí)間復(fù)雜度為O(1)。

元素外置

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

找一個(gè)位置把每個(gè)數(shù)據(jù)存起來(lái)，但是每個(gè)數(shù)據(jù)的地址可以不連續(xù)。
這時(shí)每個(gè)地址指向?qū)?yīng)數(shù)據(jù)，而這時(shí)我們找一塊連續(xù)的內(nèi)存把每個(gè)數(shù)據(jù)的地址存儲(chǔ)起來(lái)。
這塊連續(xù)空間存儲(chǔ)全部都是地址，每個(gè)地址指向一個(gè)數(shù)據(jù)內(nèi)存。
這時(shí)Li[0]為0x324地址，然后找到該地址中的數(shù)據(jù)0x100然后找到0x100指向的內(nèi)存空間為數(shù)據(jù)12。
也就是把數(shù)據(jù)存儲(chǔ)到順序表之外，元素外置，可以存儲(chǔ)不同的數(shù)據(jù)類型。

圖b這樣的順序表也被稱為對(duì)實(shí)際數(shù)據(jù)的索引，這是最簡(jiǎn)單的索引結(jié)構(gòu)。

2. 順序表結(jié)構(gòu)（一體式vs分離式）

一個(gè)順序表的完整信息包括兩部分，一部分是表中的 元素存儲(chǔ)區(qū) ，另一部分為 表頭信息 ：主要包括元素存儲(chǔ)區(qū)的 容量 和當(dāng)前表中 已存的元素個(gè)數(shù) 。
一體式和分離式主要決定的是 存儲(chǔ)區(qū)大小是否為固定的 。

一體式存儲(chǔ)

表頭信息和數(shù)據(jù)區(qū)一起存儲(chǔ)

存儲(chǔ)表信息的單元與元素存儲(chǔ)區(qū)以連續(xù)的方式安排在一塊存儲(chǔ)區(qū)里，兩部分?jǐn)?shù)據(jù)的整體形成一個(gè)完整的順序表對(duì)象。
一體式結(jié)構(gòu)整體性強(qiáng)，易于管理。但是由于數(shù)據(jù)元素存儲(chǔ)區(qū)域是表對(duì)象的一部分，順序表創(chuàng)建后，元素存儲(chǔ)區(qū)就固定了。 比如java中的數(shù)組。大小是固定的

更換數(shù)據(jù)

所以若想更換數(shù)據(jù)區(qū)，則只能整體搬遷，即整個(gè)順序表對(duì)象（指存儲(chǔ)順序表的結(jié)構(gòu)信息的區(qū)域）改變了。

分離式存儲(chǔ)

表頭信息和存儲(chǔ)區(qū)分開(kāi)存儲(chǔ)

采用分離式間接訪問(wèn)，多了一次計(jì)算。
表對(duì)象里只保存與整個(gè)表有關(guān)的信息（即容量和元素個(gè)數(shù)），實(shí)際數(shù)據(jù)元素存放在另一個(gè)獨(dú)立的元素存儲(chǔ)區(qū)里，通過(guò)鏈接與基本表對(duì)象關(guān)聯(lián)。 類似于java的List
為了考慮數(shù)據(jù)動(dòng)態(tài)變化，盡量使用分離式。

更換數(shù)據(jù)

若想更換數(shù)據(jù)區(qū)，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可，而該順序表對(duì)象不變。
人們把采用這種技術(shù)實(shí)現(xiàn)的順序表稱為動(dòng)態(tài)順序表，因?yàn)槠淙萘靠梢栽谑褂弥袆?dòng)態(tài)變化。

數(shù)據(jù)區(qū)擴(kuò)充

當(dāng)進(jìn)行存儲(chǔ)區(qū)擴(kuò)充時(shí)，相當(dāng)于新建一個(gè)存儲(chǔ)區(qū)，但是新建這個(gè)存儲(chǔ)區(qū)究竟要多大。
擴(kuò)充的兩種策略：

1. 每次擴(kuò)充 增加固定數(shù)目 的存儲(chǔ)位置，如每次擴(kuò)充增加10個(gè)元素位置，這種策略可稱為線性增長(zhǎng)。特點(diǎn)：節(jié)省空間，但是擴(kuò)充操作頻繁，操作次數(shù)多。
2. 每次 擴(kuò)充容量加倍 ，如每次擴(kuò)充增加一倍存儲(chǔ)空間。特點(diǎn)：減少了擴(kuò)充操作的執(zhí)行次數(shù)，但可能會(huì)浪費(fèi)空間資源。以空間換時(shí)間， 推薦的方式 。

3. 順序表的操作

增加元素

當(dāng)我們?nèi)萘繛?，現(xiàn)在數(shù)字為4，我們想添加一個(gè)元素111時(shí)：

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

刪除元素

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

4. python中的順序表

Python中的list和tuple兩種類型采用了順序表的實(shí)現(xiàn)技術(shù)，tuple是不可變類型，即不變的順序表，因此不支持改變其內(nèi)部狀態(tài)的任何操作，而其他方面，則與list的性質(zhì)類似。

List的基本實(shí)現(xiàn)技術(shù)

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

• 基于下標(biāo)（位置）的高效元素訪問(wèn)和更新，時(shí)間復(fù)雜度應(yīng)該是O(1)；
  為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲(chǔ)區(qū)中，采用元素外置。
• 允許任意加入元素，而且在不斷加入元素的過(guò)程中，表對(duì)象的標(biāo)識(shí)（函數(shù)id得到的值）不變。
  為滿足該特征，就必須能更換元素存儲(chǔ)區(qū)，并且為保證更換存儲(chǔ)區(qū)時(shí)list對(duì)象的標(biāo)識(shí)id不變，只能采用分離式實(shí)現(xiàn)技術(shù)。

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

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