我是南城余！阿里云開發(fā)者平臺(tái)專家博士證書獲得者！

歡迎關(guān)注我的博客！一同成長(zhǎng)！

一名從事運(yùn)維開發(fā)的worker，記錄分享學(xué)習(xí)。

專注于AI，運(yùn)維開發(fā)，windows Linux 系統(tǒng)領(lǐng)域的分享！

本章節(jié)對(duì)應(yīng)知識(shí)庫(kù)

數(shù)據(jù)結(jié)構(gòu)與集合源碼 (yuque.com)

---

【拓展】尚硅谷_宋紅康_數(shù)據(jù)結(jié)構(gòu)概述-Java版.xmind

計(jì)算機(jī)基礎(chǔ)概念

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)，就是一種程序設(shè)計(jì)優(yōu)化的方法論，研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，目的是加快程序的執(zhí)行速度、減少內(nèi)存占用的空間。

數(shù)據(jù)間的關(guān)系

邏輯關(guān)系

• 集合結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外，別無(wú)其他關(guān)系。集合元素之間沒有邏輯關(guān)系。
• 線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系。比如：排隊(duì)。結(jié)構(gòu)中必須存在唯一的首元素和唯一的尾元素。體現(xiàn)為：一維數(shù)組、鏈表、棧、隊(duì)列
• 樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系。比如：家譜、文件系統(tǒng)、組織架構(gòu)
• 圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系。比如：全國(guó)鐵路網(wǎng)、地鐵圖

存儲(chǔ)關(guān)系（物理結(jié)構(gòu)）

順序結(jié)構(gòu)

• 順序結(jié)構(gòu)就是使用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)邏輯上相鄰的各個(gè)元素。
• 優(yōu)點(diǎn)： 只需要申請(qǐng)存放數(shù)據(jù)本身的內(nèi)存空間即可，支持下標(biāo)訪問，也可以實(shí)現(xiàn)隨機(jī)訪問。
• 缺點(diǎn)： 必須靜態(tài)分配連續(xù)空間，內(nèi)存空間的利用率比較低。插入或刪除可能需要移動(dòng)大量元素，效率比較低

開發(fā)中，我們更習(xí)慣如下的方式理解存儲(chǔ)結(jié)構(gòu)：

》線性表（一對(duì)一關(guān)系）：一維數(shù)組、單向鏈表、雙向鏈表、棧、消息隊(duì)列

》樹（一對(duì)多關(guān)系）：各種樹，比如：二叉樹、B+樹

》圖（多對(duì)多關(guān)系）

》哈希表：比如：HashMap、HashSet

鏈?zhǔn)浇Y(jié)構(gòu)

• 不使用連續(xù)的存儲(chǔ)空間存放結(jié)構(gòu)的元素，而是為每一個(gè)元素構(gòu)造一個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)中除了存放數(shù)據(jù)本身以外，還需要存放指向下一個(gè)節(jié)點(diǎn)的指針。
• 優(yōu)點(diǎn)：不采用連續(xù)的存儲(chǔ)空間導(dǎo)致內(nèi)存空間利用率比較高，克服順序存儲(chǔ)結(jié)構(gòu)中預(yù)知元素個(gè)數(shù)的缺點(diǎn)。插入或刪除元素時(shí)，不需要移動(dòng)大量的元素。
• 缺點(diǎn)：需要額外的空間來(lái)表達(dá)數(shù)據(jù)之間的邏輯關(guān)系，不支持下標(biāo)訪問和隨機(jī)訪問。

  

  索引結(jié)構(gòu)
• 除建立存儲(chǔ)節(jié)點(diǎn)信息外，還建立附加的索引表來(lái)記錄每個(gè)元素節(jié)點(diǎn)的地址。索引表由若干索引項(xiàng)組成。索引項(xiàng)的一般形式是：（關(guān)鍵字，地址）。
• 優(yōu)點(diǎn)：用節(jié)點(diǎn)的索引號(hào)來(lái)確定結(jié)點(diǎn)存儲(chǔ)地址，檢索速度快。
• 缺點(diǎn)： 增加了附加的索引表，會(huì)占用較多的存儲(chǔ)空間。在增加和刪除數(shù)據(jù)時(shí)要修改索引表，因而會(huì)花費(fèi)較多的時(shí)間。

  

  散列結(jié)構(gòu)
• 根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址，又稱為Hash存儲(chǔ)。
• 優(yōu)點(diǎn)：檢索、增加和刪除結(jié)點(diǎn)的操作都很快。
• 缺點(diǎn)：不支持排序，一般比用線性表存儲(chǔ)需要更多的空間，并且記錄的關(guān)鍵字不能重復(fù)。

  

運(yùn)算結(jié)構(gòu)

施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn)。運(yùn)算的定義是針對(duì)邏輯結(jié)構(gòu)的，指出運(yùn)算的功能；運(yùn)算的實(shí)現(xiàn)是針對(duì)存儲(chǔ)結(jié)構(gòu)的，指出運(yùn)算的具體操作步驟。

- 分配資源，建立結(jié)構(gòu)，釋放資源

- 插入和刪除

- 獲取和遍歷

- 修改和排序