數(shù)據(jù)結(jié)構(gòu)之簡(jiǎn)單的數(shù)組
?作為一個(gè)技術(shù)博主，了不起不是在創(chuàng)作就是在創(chuàng)作的路上（當(dāng)然偶爾也會(huì)有點(diǎn)恰飯文~還指望大家多多支持），我們都知道，在寫代碼的過程中，很多時(shí)候能夠用到這個(gè)數(shù)據(jù)結(jié)構(gòu)，而大廠在面試的時(shí)候也是各種強(qiáng)調(diào)自己要求數(shù)據(jù)結(jié)構(gòu)如何如何的，然后通過問關(guān)于數(shù)據(jù)結(jié)構(gòu)的面試題來篩選面試者，那么今天了不起就來盤一下這個(gè)數(shù)據(jù)結(jié)構(gòu)。
什么是數(shù)據(jù)結(jié)構(gòu)
百度百科是這么解釋的：
數(shù)據(jù)結(jié)構(gòu)(data structure)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
其實(shí)我們總結(jié)一下的話，那真的太簡(jiǎn)單的，存在內(nèi)存的，而且是用來存數(shù)據(jù)的，它就可以理解為數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)的分類
我們?cè)陂_發(fā)中，也都經(jīng)常的用到數(shù)據(jù)結(jié)構(gòu)，只是不是很在意這個(gè)名詞，而是直接使用他們的另外的說法，比如：
- 數(shù)組
- 鏈表
- 堆
- 棧
上面的這四個(gè)數(shù)結(jié)構(gòu)，可以統(tǒng)稱為線性表。而除了線性表，我們還有其他的數(shù)據(jù)結(jié)構(gòu)，比如散列表，樹，還有圖。
散列表有：
- hash
- 位圖
樹有：
- 二叉樹
- 多路樹
- 堆
圖包含：
- 有向圖
- 無向圖
- 帶權(quán)圖
我們今天也別分析太多的內(nèi)容，我們從最熟悉的入手，那么什么是我們最熟悉的呢？毫無疑問，那就是線性表中的內(nèi)容，因?yàn)?數(shù)組，鏈表，堆，棧，這都是我們經(jīng)常會(huì)在面試中遇到的，而且也是在代碼中經(jīng)常能夠看到的，而有的同學(xué)會(huì)說，根本沒用過，那這就是有點(diǎn)不太理解了，畢竟你用的都是上層的封裝類，而不是具體的底層。
我們先說數(shù)組：
數(shù)組
數(shù)組（Array）是有限個(gè)相同類型的變量所組成的有序集合，數(shù)組中的每一個(gè)變量被稱為元素。數(shù)組是 最為簡(jiǎn)單、最為常用的數(shù)據(jù)結(jié)構(gòu)。
數(shù)組都是用一組連續(xù)的內(nèi)存空間來存儲(chǔ)一組具有相同類型的數(shù)據(jù)。
也就是在我們的內(nèi)存中位置，都是緊挨著的，
就比如下圖，灰色標(biāo)志的是被使用的內(nèi)存，而紅色格子表示的就是數(shù)組占用的連續(xù)內(nèi)存，而黃色格子表示的就是空閑的內(nèi)存。
上面這個(gè)圖，就是數(shù)組在內(nèi)存中的存儲(chǔ)空間示意圖，其實(shí)主要目的還是了不起想給大家說這個(gè)數(shù)組在內(nèi)存中存儲(chǔ)的時(shí)候，是一個(gè)連續(xù)的內(nèi)存空間，不會(huì)出現(xiàn)隔一個(gè)格子出現(xiàn)一個(gè)。
而數(shù)組呢，可以根據(jù)下標(biāo)隨機(jī)訪問數(shù)據(jù)，其實(shí)說隨機(jī)，而此隨機(jī)非彼隨機(jī)。
他說隨機(jī)，也只是說隨機(jī)元素尋址，而不是說隨機(jī)取數(shù)據(jù)。
比如我們的 int 是 4 字節(jié)，也就是(32位)，實(shí)際上內(nèi)存存儲(chǔ)的是位
如果這時(shí)候隨機(jī)元素尋址的話，
采用隨機(jī)元素尋址，那么就是
那么我們就得知道這個(gè)操作這個(gè)數(shù)組的內(nèi)存空間是都干了什么
第一步，讀取元素
第二步更新元素
讀取和更新都是可以隨機(jī)訪問的，時(shí)間復(fù)雜度大家可以猜測(cè)一下，歡迎在文章末尾回復(fù)。
那么插入元素的時(shí)候就會(huì)有三種情況了，尾部插入，中間插入，還有超范圍的插入。
那么什么是尾部插入呢？
尾部插入
其實(shí)尾部茶壺如是最簡(jiǎn)單的實(shí)現(xiàn)方式，
在數(shù)據(jù)的實(shí)際元素?cái)?shù)量小于數(shù)組長(zhǎng)度的情況下：直接把插入的元素放在數(shù)組尾部的空閑位置即可，等同于更新元素的操作
中間插入
在數(shù)據(jù)的實(shí)際元素?cái)?shù)量小于數(shù)組長(zhǎng)度的情況下：由于數(shù)組的每一個(gè)元素都有其固定下標(biāo)，所以首先把插入位置及后面的元素向后移動(dòng)，騰出地方， 再把要插入的元素放到對(duì)應(yīng)的數(shù)組位置上。
超范圍插入
假如現(xiàn)在有一個(gè)數(shù)組，已經(jīng)裝滿了元素，這時(shí)還想插入一個(gè)新元素，或者插入位置是越界的 這時(shí)就要對(duì)原數(shù)組進(jìn)行擴(kuò)容：可以創(chuàng)建一個(gè)新數(shù)組，長(zhǎng)度是舊數(shù)組的2倍，再把舊數(shù)組中的元素統(tǒng) 統(tǒng)復(fù)制過去，這樣就實(shí)現(xiàn)了數(shù)組的擴(kuò)容。
那么使用數(shù)組的優(yōu)缺點(diǎn)都有什么呢？
數(shù)組的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
數(shù)組擁有非常高效的隨機(jī)訪問能力，只要給出下標(biāo)，就可以用常量時(shí)間找到對(duì)應(yīng)元素
缺點(diǎn)：
插入和刪除元素方面。由于數(shù)組元素連續(xù)緊密地存儲(chǔ)在內(nèi)存中，插入、刪除元素都會(huì)導(dǎo)致大量元素被迫 移動(dòng)，影響效率。(ArrayList LinkedList ) 申請(qǐng)的空間必須是連續(xù)的，也就是說即使有空間也可能因?yàn)闆]有足夠的連續(xù)空間而創(chuàng)建失敗。
如果超出范圍，需要重新申請(qǐng)內(nèi)存進(jìn)行存儲(chǔ)，原空間就浪費(fèi)了
一般的，數(shù)組是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用太廣泛了，ArrayList、Redis、消息隊(duì)列等等，這些都是使用了數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)也是在面試的時(shí)候經(jīng)常會(huì)和其他的數(shù)據(jù)結(jié)構(gòu)拿出來做對(duì)比的，關(guān)于這個(gè)數(shù)據(jù)結(jié)構(gòu)的數(shù)組，你學(xué)會(huì)了么？
