前言

我們都知道，所謂的數據結構，都是我們在為了更好的對數據的增刪改查而創(chuàng)造出來的對數據的結構設計悠鞍，但是我們要知道的是，這些數據結構都是抽象的邏輯結構饿凛，并不是真實的物理上的存儲結構狞玛，大部分時候软驰，我們對數據結構的討論，也都是討論的是邏輯上的數據結構心肪，并不是對真實的存儲在硬盤中的數據的存儲結構的討論锭亏。

真實的物理上的數據，存儲到我們的硬盤上的或者是在內存上的時候硬鞍，都是有著確切的存儲結構的慧瘤，而不是我們想象中的類似b樹，二叉樹這種抽象的邏輯結構固该。

那么锅减，在我們的硬盤上，數據是如何存儲的呢伐坏？這個問題怔匣，是我們去研究邏輯上的數據結構之前，需要搞清楚的問題桦沉，也是我們本篇文章的主題每瞒。

正文

物理存儲結構，是數據的邏輯結構在計算機中的存儲形式纯露。

但是在理解物理上的數據存儲結構之前剿骨，我們要先對硬盤有一個足夠的了解。

硬盤是一個實際存在的物品埠褪，那么也就是說浓利，這個硬盤不可能如我們想象出的邏輯設計那樣，去存儲我們的數據钞速。想象一下贷掖，如果存一百萬條數據，我們在硬盤中隨意存儲玉工，不按照客觀的物理規(guī)則來存儲羽资，那么我們會發(fā)現(xiàn)，硬盤的空間會被很大的浪費掉遵班。

也因此屠升，在硬盤中存儲數據的時候，我們必須按照一定的客觀規(guī)律來狭郑。而這種客觀規(guī)律腹暖，在計算機發(fā)展的過程中，逐漸形成了現(xiàn)在比較常見的兩種規(guī)律翰萨。

1.順序存儲結構

順序存儲結構脏答，是將我們邏輯上的數據結構中相鄰的數據，在物理位置上，也存儲在相鄰的位置殖告。數據結構中的節(jié)點關系由存儲單元的鄰接關系來體現(xiàn)阿蝶。

也就是說，數據間的邏輯關系和物理關系是一致的黄绩。

一般來說羡洁，在我們java語言中，描述這種物理存儲結構的話爽丹，都是借助我們的 數組 來闡述的筑煮。如圖所示：

image

這種存儲結構，還是很好理解的粤蝎，說白了真仲，就是排隊而已，每一條數據都是占一小段空間初澎，按照順序站好秸应，占據著連續(xù)的存儲空間。

1.1 優(yōu)點

順序存儲結構的優(yōu)點還是比較明顯的谤狡，由于是按照物理上的存儲空間的順序存儲數據灸眼，那么對存儲空間的利用率就會非常高，存儲密度比較大墓懂。

而且因為是順序存儲數據，那么也就是說霉囚，我們的數據捕仔，存儲在這里的時候，天然在硬盤中的平均尋道時間中盈罐，就會快很多榜跌。

那么，什么是尋道時間呢盅粪？ 先看一張關于磁盤的圖片钓葫，如下：

image

我們發(fā)現(xiàn)，這種傳統(tǒng)的硬盤票顾，數據是存儲到磁盤中的磁道（磁盤盤片）中础浮，通過磁頭（讀寫磁頭）來查找數據。而平均尋道時間就是指磁頭移動到數據所在的磁道所使用的時間的平均值奠骄。

如果硬盤的尋道速度變快豆同，那么就意味著我們的查找數據能力也在變快。

而在我們的順序存儲結構中含鳞，我們的數據是按照磁道的輪轉順序存儲到磁道上的影锈，也就是說，當我們進行數據查找的時候，會更快的定位到實際的數據所在鸭廷，這也就是意味著我們的數據查找速度變快枣抱。
<table><tr><td>
小知識；

在現(xiàn)代的計算機進化過程中辆床，數據的存儲有了很大的變化沃但，比如說我們現(xiàn)在比較常見的固態(tài)硬盤，由于SSD固態(tài)硬盤沒有磁頭佛吓，所以幾乎不存在尋道時間這一概念宵晚，當系統(tǒng)發(fā)出指令時，不需要磁頭和盤片维雇，而是直接從Flash顆粒上讀取淤刃，相對傳統(tǒng)的機械硬盤的尋道時間來說要快多了。
</td></tr></table>

順序存儲結構的優(yōu)點總結如下：

1. 數據存儲密度大吱型，存儲空間的利用率要大逸贾。
2. 查找速度比較快。

1.2 缺點

首先我們知道的是津滞，順序存儲結構铝侵，存儲的數據，在存儲空間中触徐，是連續(xù)的咪鲜，如下圖所示；

image

那么當我們要插入一條數據的時候撞鹉，會怎么樣呢疟丙？如圖所示：

image

從圖所示的插入過程中，我們發(fā)現(xiàn)鸟雏，自插入位置起享郊，后面的所有數據元素都往后面移動了一位，想一想孝鹊，如果數據量上去了炊琉，那么等于大量的數據都要移動，而且實際的情況又活，遠遠比這個更糟糕苔咪，所以這樣的插入效率，可想而知皇钞。

而刪除的過程悼泌，雖然和插入恰恰相反，但是造成的后果夹界，都是一樣的馆里，都是會導致大量的數據移動位置隘世。

也因此，我們知道的是鸠踪，順序存儲結構的缺點丙者，就是在插入或者是刪除的時候，效率會比較低营密。

2. 鏈式存儲結構

在實際的數據操作過程中械媒，有的數據結構需要的是查找的時候速度快一點，那么我們的順序存儲結構是符合這種需求的评汰，但是也有很多時候纷捞，我們的數據會被多次刪除也會被多次的插入，這就引發(fā)了一個問題被去，順序存儲結構不能滿足這種需求場景主儡，于是就出現(xiàn)了鏈式存儲結構。

鏈式存儲結構是將數據元素存放在任意的存儲單元里惨缆，這組存儲單元可以是連續(xù)的糜值，也可以是不連續(xù)的。

也就是說坯墨，在鏈式存儲結構中寂汇，數據是可以放到這個存儲空間的任意位置，也因此捣染，數據與數據之間物理位置的關系骄瓣，不能表達出數據之間的邏輯關系。

那么液斜，要如何解決這種邏輯關系呢累贤？

于是在鏈式存儲結構中，會將一個數據單元少漆，分為兩個區(qū)域，一個數據域硼被，一個指針域示损。

數據域存儲的就是我們實際的數據，而指針域則存儲的是關聯(lián)的其他數據的位置的指針嚷硫，如果要通過鏈式存儲結構存儲數據 [A , B , C , D , E] 检访，存儲的大概模型如圖所示：

image

在這張圖的基礎上，經過轉變后仔掸，將圖變?yōu)槿缦碌臉幼樱?/p>

image

這樣可以看的出來脆贵，指針域指向了下一個數據節(jié)點，也就是說起暮，在連式存儲結構中卖氨，數據之間的關系，是通過指針域的指向關系來表現(xiàn)的，和數據實際存儲的位置沒有關系筒捺。

2.1 優(yōu)點

鏈式存儲結構的優(yōu)點是很好理解的柏腻，先看鏈式存儲結構的插入圖：

image

由于鏈式存儲結構中，數據的關系不是由數據的實際存儲位置表示的系吭，而是由各個數據節(jié)點的指針域來表示的五嫂，那么也就是說，在數據插入或者刪除的時候肯尺，不需要將插入數據后面的數據移動沃缘，只需要修改一下指針域的指向性就可以了。

image

也就是說则吟，鏈式存儲結構的插入或者刪除元素很方便槐臀，比較靈活。而且我們看到的是逾滥，鏈式存儲結構不需要連續(xù)的內存來存儲峰档，也就是說，對碎片型的內存的利用效率還是相對比較高的寨昙。

2.2 缺點

在順序存儲結構中讥巡，數據的存儲就只需要存儲這個數據就行。但是在鏈式存儲結構中舔哪，數據的存儲欢顷，除了存儲的是這個數據外，還需要存儲和這個數據相關的指針域捉蚤。

image

這樣抬驴，就相比于順序存儲結構外，鏈式存儲結構多存儲了一部分其他的數據缆巧，所以對存儲空間的利用率就會降低布持。

而且要注意的是，鏈式存儲結構陕悬，在物理邏輯上講题暖，因為實際存儲的位置不是順序的，那么讀取的時候捉超，效率會比較低胧卤。

總結

3.1 順序存儲結構

優(yōu)點：

1. 數據存儲密度大，存儲空間的利用率要大拼岳。
2. 查找速度比較快枝誊。
   缺點：
3. 插入或者是刪除的時候，效率會比較低

3.2 鏈式存儲結構

優(yōu)點：

1. 插入或者刪除的時候惜纸，效率比較高
2. 對碎片型的內存利用率高叶撒。
   缺點：
3. 額外新增了指針域的數據绝骚，對內存的消耗大
4. 在讀取的時候效率比較低。