數(shù)組

一、數(shù)組（Array）

是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)，最大的特點(diǎn)就是支持隨機(jī)訪問，但插入、刪除操作也因此變得比較低效，平均情況時間復(fù)雜度為 O(n)

• 第一是線性表（Linear List）。顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。其實(shí)除了數(shù)組，鏈表、隊(duì)列、棧等也是線性表結(jié)構(gòu)。
• 第二個是連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)。正是因?yàn)檫@兩個限制，它才有了一個堪稱“殺手锏”的特性：“隨機(jī)訪問”。但有利就有弊，這兩個限制也讓數(shù)組的很多操作變得非常低效，比如要想在數(shù)組中刪除、插入一個數(shù)據(jù)，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作。

二、隨機(jī)訪問數(shù)組中的某個元素

我們知道，計(jì)算機(jī)會給每個內(nèi)存單元分配一個地址，計(jì)算機(jī)通過地址來訪問內(nèi)存中的數(shù)據(jù)。當(dāng)計(jì)算機(jī)需要隨機(jī)訪問數(shù)組中的某個元素時，它會首先通過下面的尋址公式，計(jì)算出該元素存儲的內(nèi)存地址：

a[i]_address = base_address + i * data_type_size

三、插入操作和刪除操作

假設(shè)數(shù)組的長度為 n，現(xiàn)在，如果我們需要將一個數(shù)據(jù)插入到數(shù)組中的第 k 個位置。為了把第 k 個位置騰出來，給新來的數(shù)據(jù)，我們需要將第 k～n 這部分的元素都順序地往后挪一位。平均情況時間復(fù)雜度為 O(n)

四、插入優(yōu)化：

如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當(dāng)作一個存儲數(shù)據(jù)的集合。在這種情況下，如果要將某個數(shù)據(jù)插入到第 k 個位置，為了避免大規(guī)模的數(shù)據(jù)搬移，我們還有一個簡單的辦法就是，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個位置。

五、刪除優(yōu)化：

可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒有更多空間存儲數(shù)據(jù)時，我們再觸發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

六、動態(tài)擴(kuò)容

數(shù)組本身在定義的時候需要預(yù)先指定大小，因?yàn)樾枰峙溥B續(xù)的內(nèi)存空間。如果我們申請了大小為 10 的數(shù)組，當(dāng)?shù)?11 個數(shù)據(jù)需要存儲到數(shù)組中時，我們就需要重新分配一塊更大的空間，將原來的數(shù)據(jù)復(fù)制過去，然后再將新的數(shù)據(jù)插入。

鏈表

一、什么是鏈表？

1.和數(shù)組一樣，鏈表也是一種線性表。
2.從內(nèi)存結(jié)構(gòu)來看，鏈表的內(nèi)存結(jié)構(gòu)是不連續(xù)的內(nèi)存空間，是將一組零散的內(nèi)存塊串聯(lián)起來，從而進(jìn)行數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)。
3.鏈表中的每一個內(nèi)存塊被稱為節(jié)點(diǎn)Node。節(jié)點(diǎn)除了存儲數(shù)據(jù)外，還需記錄鏈上下一個節(jié)點(diǎn)的地址，即后繼指針next。

二、為什么使用鏈表？即鏈表的特點(diǎn)

1.插入、刪除數(shù)據(jù)效率高O(1)級別（只需更改指針指向即可），隨機(jī)訪問效率低O(n)級別（需要從鏈頭至鏈尾進(jìn)行遍歷）。
2.和數(shù)組相比，內(nèi)存空間消耗更大，因?yàn)槊總€存儲數(shù)據(jù)的節(jié)點(diǎn)都需要額外的空間存儲后繼指針。

3.雙向鏈表

• 節(jié)點(diǎn)除了存儲數(shù)據(jù)外，還有兩個指針分別指向前一個節(jié)點(diǎn)地址（前驅(qū)指針prev）和下一個節(jié)點(diǎn)地址（后繼指針next）。
• 首節(jié)點(diǎn)的前驅(qū)指針prev和尾節(jié)點(diǎn)的后繼指針均指向空地址。
• 性能特點(diǎn)：
  • 和單鏈表相比，存儲相同的數(shù)據(jù)，需要消耗更多的存儲空間。
  • 插入、刪除操作比單鏈表效率更高O(1)級別。
    以刪除操作為例，刪除操作分為2種情況：
    1、給定數(shù)據(jù)值刪除對應(yīng)節(jié)點(diǎn)，單鏈表和雙向鏈表都需要從頭到尾進(jìn)行遍歷從而找到對應(yīng)節(jié)點(diǎn)進(jìn)行刪除，時間復(fù)雜度為O(n)。
    2、給定節(jié)點(diǎn)地址刪除節(jié)點(diǎn)，要進(jìn)行刪除操作必須找到前驅(qū)節(jié)點(diǎn)，單鏈表需要從頭到尾進(jìn)行遍歷直到p->next = q，時間復(fù)雜度為O(n)，而雙向鏈表可以直接找到前驅(qū)節(jié)點(diǎn)，時間復(fù)雜度為O(1)。
    • 對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因?yàn)槲覀兛梢杂涗浬洗尾檎业奈恢胮，每一次查詢時，根據(jù)要查找的值與p的大小

三、如何分別用鏈表和數(shù)組實(shí)現(xiàn)LRU緩沖淘汰策略（最近最少使用策略LRU）（Least Recently Used）？

鏈表實(shí)現(xiàn)LRU緩存淘汰策略

當(dāng)訪問的數(shù)據(jù)沒有存儲在緩存的鏈表中時，直接將數(shù)據(jù)插入鏈表尾部，時間復(fù)雜度為O(1)；當(dāng)訪問的數(shù)據(jù)存在于存儲的鏈表中時，將該數(shù)據(jù)對應(yīng)的節(jié)點(diǎn)，插入到鏈表尾部,時間復(fù)雜度為O(n)。如果緩存被占滿，則從鏈表頭部的數(shù)據(jù)開始清理，時間復(fù)雜度為O(1)。

使用散列表和鏈表實(shí)現(xiàn)LRU緩存淘汰算法？

①使用雙向鏈表存儲數(shù)據(jù)，鏈表中每個節(jié)點(diǎn)存儲數(shù)據(jù)（data）、前驅(qū)指針（prev）、后繼指針（next）之外，還新增了一個特殊的字段 hnext。
②散列表通過鏈表法解決散列沖突，所以每個節(jié)點(diǎn)都會在兩條鏈中。一條鏈?zhǔn)请p向鏈表，另一條鏈?zhǔn)巧⒘斜碇械睦?。前?qū)和后繼指針是為了將節(jié)點(diǎn)串在雙向鏈表中，hnext指針是為了將節(jié)點(diǎn)串在散列表的拉鏈中。
③LRU緩存淘汰算法的3個主要操作如何做到時間復(fù)雜度為O(1)呢？
首先，我們明確一點(diǎn)就是鏈表本身插入和刪除一個節(jié)點(diǎn)的時間復(fù)雜度為O(1)，因?yàn)橹恍韪膸讉€指針指向即可。
接著，來分析查找操作的時間復(fù)雜度。當(dāng)要查找一個數(shù)據(jù)時，通過散列表可實(shí)現(xiàn)在O(1)時間復(fù)雜度找到該數(shù)據(jù)，再加上前面說的插入或刪除的時間復(fù)雜度是O(1)，所以我們總操作的時間復(fù)雜度就是O(1)。

數(shù)組實(shí)現(xiàn)LRU緩存淘汰策略

首位置優(yōu)先清理，末尾位置保存最新訪問數(shù)據(jù)
當(dāng)訪問的數(shù)據(jù)未存在于緩存的數(shù)組中時，直接將數(shù)據(jù)添加進(jìn)數(shù)組作為當(dāng)前最后一個元素時間復(fù)雜度為O(1)；當(dāng)訪問的數(shù)據(jù)存在于緩存的數(shù)組中時，查找到數(shù)據(jù)并將其插入當(dāng)前數(shù)組最后一個元素的位置，此時亦需移動數(shù)組元素，時間復(fù)雜度為O(n)。緩存用滿時，則清理掉數(shù)組首位置的元素，且剩余數(shù)組元素需整體前移一位，時間復(fù)雜度為O(n)。（優(yōu)化：清理的時候可以考慮一次性清理一定數(shù)量，從而降低清理次數(shù)，提高性能。）

總結(jié)：選擇數(shù)組還是鏈表？

1、數(shù)組和鏈表的區(qū)別：

鏈表適合插入、刪除，時間復(fù)雜度 O(1)
數(shù)組支持隨機(jī)訪問，根據(jù)下標(biāo)隨機(jī)訪問的時間復(fù)雜度為 O(1)

2.插入、刪除和隨機(jī)訪問的時間復(fù)雜度

數(shù)組：插入、刪除的時間復(fù)雜度是O(n)，隨機(jī)訪問的時間復(fù)雜度是O(1)。
鏈表：插入、刪除的時間復(fù)雜度是O(1)，隨機(jī)訪問的時間復(fù)雜端是O(n)。

3.數(shù)組缺點(diǎn)

1）若申請內(nèi)存空間很大，比如100M，但若內(nèi)存空間沒有100M的連續(xù)空間時，則會申請失敗，盡管內(nèi)存可用空間超過100M。
2）大小固定，若存儲空間不足，需進(jìn)行擴(kuò)容，一旦擴(kuò)容就要進(jìn)行數(shù)據(jù)復(fù)制，而這時非常費(fèi)時的。

4.鏈表缺點(diǎn)

1）內(nèi)存空間消耗更大，因?yàn)樾枰~外的空間存儲指針信息。
2）對鏈表進(jìn)行頻繁的插入和刪除操作，會導(dǎo)致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。

5.如何選擇？

數(shù)組簡單易用，在實(shí)現(xiàn)上使用連續(xù)的內(nèi)存空間，可以借助CPU的緩沖機(jī)制預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高，而鏈表在內(nèi)存中并不是連續(xù)存儲，所以對CPU緩存不友好，沒辦法預(yù)讀。
如果代碼對內(nèi)存的使用非?？量蹋菙?shù)組就更適合。