前言：

? ? 數(shù)據(jù)結(jié)構(gòu)是計(jì)算存儲(chǔ)，組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

Data Structure Visualization? 數(shù)據(jù)結(jié)構(gòu)可演示線上地址

一.線性結(jié)構(gòu)

1.1? 數(shù)組

? ? ?數(shù)組(Array)是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用于存儲(chǔ)固定大小的相同類型的數(shù)據(jù)元素。在數(shù)組中，數(shù)據(jù)元素按照有序的方式進(jìn)行排列，可以通過(guò)索引訪問(wèn)數(shù)組中的任意位置的元素。

//動(dòng)態(tài)初始化：初始化時(shí)由程序員指定數(shù)組長(zhǎng)度，由系統(tǒng)為數(shù)組元素分配初始值
char c1[] = new char[5];//靜態(tài)初始化：初始化由程序員顯示指定每個(gè)數(shù)組的初始值，由系統(tǒng)決定數(shù)組的長(zhǎng)度
char c2[] = new char[]{'A','B','C'};
char c3[] = {'D','E','E','U'}

數(shù)組的特點(diǎn)：

1. 順序存儲(chǔ)：數(shù)組中的元素按照順序存儲(chǔ)在內(nèi)存空間中，每個(gè)元素都有一個(gè)唯一的索引，可以通過(guò)索引快速訪問(wèn)。
2. 大小固定：一旦定義了數(shù)組的大小，就不能改變。如果需要更大的存儲(chǔ)空間，需要重新定義一個(gè)新的數(shù)組。
3. 元素類型相同：數(shù)組中的所有元素必須是相同的類型。
4. 無(wú)界數(shù)組：數(shù)組的長(zhǎng)度可以是任意的整數(shù)，只要內(nèi)存空間足夠。

數(shù)組優(yōu)點(diǎn)：

? ? ?1.訪問(wèn)速度快：由于數(shù)組是順序存儲(chǔ)，可以通過(guò)索引直接訪問(wèn)數(shù)組中的元素，復(fù)雜度為O(1)

? ? ?2.易于實(shí)現(xiàn)：數(shù)組是一種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，容易實(shí)現(xiàn)和操作

數(shù)組缺點(diǎn)：

? ? ?1.大小固定：數(shù)組大小固定，不能動(dòng)態(tài)擴(kuò)展。如果需要更多的存儲(chǔ)空間，需要重新定義一個(gè)新的數(shù)組，會(huì)增加額外的開(kāi)銷。

? ? ?2.空間利用率低：由于數(shù)組是連續(xù)的的內(nèi)存空間，即使某些位置沒(méi)有被使用，也不能被其他數(shù)據(jù)結(jié)構(gòu)使用，導(dǎo)致空間利用率較低。

1.2? 隊(duì)列

? ? ?隊(duì)列是一種特殊的數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是先進(jìn)先出(FIFO)原則。隊(duì)列中的原色只能從一端(隊(duì)尾)加入，隊(duì)頭 刪除

? ? ?隊(duì)列特點(diǎn)：

? ? ? ?1.先進(jìn)先出：隊(duì)列中的元素遵守先進(jìn)先出的原則，即最早進(jìn)入的最先被刪除。

? ? ? ?2.插入和刪除發(fā)生在兩端：插入在隊(duì)尾，刪除在隊(duì)頭。

? ? ? ?3.無(wú)界隊(duì)列：隊(duì)列的長(zhǎng)度可以是任意整數(shù)，只要內(nèi)存空間夠。

   public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.add(1);queue.add(2);queue.add(3);System.out.println("隊(duì)列：" + queue);//隊(duì)列：[1, 2, 3]System.out.println("訪問(wèn)隊(duì)列頭：" + queue.peek());//訪問(wèn)隊(duì)列頭：1System.out.println("隊(duì)列：" + queue);//隊(duì)列：[1, 2, 3]System.out.println("刪除隊(duì)列頭：" + queue.poll());//刪除隊(duì)列頭：1System.out.println("隊(duì)列：" + queue);//隊(duì)列：[2, 3]}

1.3? 鏈表

? ? 鏈表是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)指針將一組零散的內(nèi)存塊串聯(lián)在一起。鏈表中的每個(gè)內(nèi)存塊被稱為節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外，還需要記錄鏈上的下一個(gè)節(jié)點(diǎn)的地址。

? ? 特點(diǎn)：

? ? ? 1.不需要連續(xù)的內(nèi)存空間

? ? ? 2.有指針引用

? ? ? 3.插入/刪除數(shù)據(jù)效率高，時(shí)間復(fù)雜度O(1) [只需要更改指針指向即可]；但是，隨機(jī)訪問(wèn)效率低，時(shí)間復(fù)雜度O(n) 級(jí)別[需要從鏈頭至鏈尾進(jìn)行遍歷]

? ? ? 4.和數(shù)組相比，內(nèi)存空間消耗更大，因?yàn)槊總€(gè)存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)都需要額外的空間存儲(chǔ)后繼指針。

? ? 鏈表包括 單向鏈表 ，雙向鏈表和循環(huán)鏈表等類型。其中

? ? ? ? ? ? ? 單向鏈表的節(jié)點(diǎn)只有一個(gè)后繼指針next指向后面的節(jié)點(diǎn)；

? ? ? ? ? ? ? 雙向鏈表的節(jié)點(diǎn)除了有一個(gè)后繼指針next指向后面的節(jié)點(diǎn)，還有一個(gè)前驅(qū)指針prev指向前面節(jié)點(diǎn)

? ? ? ? ? ? ?循環(huán)鏈表：與單向鏈表區(qū)別是尾節(jié)點(diǎn)的指針指向投節(jié)點(diǎn)，形成一個(gè)環(huán)

1.4? 棧

? ? ?棧（stack）是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，它只能在一端進(jìn)行插入和刪除操作，這一端被稱為棧頂，另外一端被稱為棧底。棧的元素之間存在一種順序關(guān)系，這種順序關(guān)系由元素的插入和刪除決定。

? ? 棧的主要操作：

? ? ? ?1.入棧（push）

? ? ? ?2.出棧（pop）:

? ? ? ?3.判斷?？?#xff08;is_empty）

? ? ? ?4.獲取棧頂元素（top）

二.非線性結(jié)構(gòu)

2.1? 樹

2.2? 二叉樹

2.3? AVL樹

2.4? 2-3-4樹

2.5 紅黑樹

2.6? B樹

2.7? B+樹