數(shù)組

一嵌巷、數(shù)組（Array）

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

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

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

我們知道汉形，計算機會給每個內(nèi)存單元分配一個地址，計算機通過地址來訪問內(nèi)存中的數(shù)據(jù)倍阐。當計算機需要隨機訪問數(shù)組中的某個元素時概疆，它會首先通過下面的尋址公式，計算出該元素存儲的內(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 這部分的元素都順序地往后挪一位鞠柄。平均情況時間復雜度為 O(n)

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

如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當作一個存儲數(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)被刪除秦忿。當數(shù)組沒有更多空間存儲數(shù)據(jù)時麦射，我們再觸發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導致的數(shù)據(jù)搬移灯谣。

六法褥、動態(tài)擴容

數(shù)組本身在定義的時候需要預先指定大小，因為需要分配連續(xù)的內(nèi)存空間酬屉。如果我們申請了大小為 10 的數(shù)組半等，當?shù)?11 個數(shù)據(jù)需要存儲到數(shù)組中時，我們就需要重新分配一塊更大的空間呐萨，將原來的數(shù)據(jù)復制過去杀饵，然后再將新的數(shù)據(jù)插入。

鏈表

一谬擦、什么是鏈表切距？

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

二辙培、為什么使用鏈表蔑水？即鏈表的特點

1.插入、刪除數(shù)據(jù)效率高O(1)級別（只需更改指針指向即可）扬蕊，隨機訪問效率低O(n)級別（需要從鏈頭至鏈尾進行遍歷）搀别。
2.和數(shù)組相比，內(nèi)存空間消耗更大尾抑，因為每個存儲數(shù)據(jù)的節(jié)點都需要額外的空間存儲后繼指針歇父。

3.雙向鏈表

• 節(jié)點除了存儲數(shù)據(jù)外，還有兩個指針分別指向前一個節(jié)點地址（前驅(qū)指針prev）和下一個節(jié)點地址（后繼指針next）蛮穿。
• 首節(jié)點的前驅(qū)指針prev和尾節(jié)點的后繼指針均指向空地址庶骄。
• 性能特點：
  • 和單鏈表相比，存儲相同的數(shù)據(jù)践磅，需要消耗更多的存儲空間。
  • 插入灸异、刪除操作比單鏈表效率更高O(1)級別府适。
    以刪除操作為例羔飞，刪除操作分為2種情況：
    1、給定數(shù)據(jù)值刪除對應(yīng)節(jié)點檐春，單鏈表和雙向鏈表都需要從頭到尾進行遍歷從而找到對應(yīng)節(jié)點進行刪除逻淌，時間復雜度為O(n)。
    2疟暖、給定節(jié)點地址刪除節(jié)點卡儒，要進行刪除操作必須找到前驅(qū)節(jié)點，單鏈表需要從頭到尾進行遍歷直到p->next = q俐巴，時間復雜度為O(n)骨望，而雙向鏈表可以直接找到前驅(qū)節(jié)點，時間復雜度為O(1)欣舵。
    • 對于一個有序鏈表擎鸠，雙向鏈表的按值查詢效率要比單鏈表高一些。因為我們可以記錄上次查找的位置p缘圈，每一次查詢時劣光，根據(jù)要查找的值與p的大小

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

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

當訪問的數(shù)據(jù)沒有存儲在緩存的鏈表中時绢涡，直接將數(shù)據(jù)插入鏈表尾部，時間復雜度為O(1)遣疯；當訪問的數(shù)據(jù)存在于存儲的鏈表中時垂寥，將該數(shù)據(jù)對應(yīng)的節(jié)點，插入到鏈表尾部,時間復雜度為O(n)另锋。如果緩存被占滿滞项，則從鏈表頭部的數(shù)據(jù)開始清理，時間復雜度為O(1)夭坪。

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

①使用雙向鏈表存儲數(shù)據(jù)，鏈表中每個節(jié)點存儲數(shù)據(jù)（data）室梅、前驅(qū)指針（prev）戏仓、后繼指針（next）之外，還新增了一個特殊的字段 hnext亡鼠。
②散列表通過鏈表法解決散列沖突赏殃，所以每個節(jié)點都會在兩條鏈中。一條鏈是雙向鏈表间涵，另一條鏈是散列表中的拉鏈仁热。前驅(qū)和后繼指針是為了將節(jié)點串在雙向鏈表中，hnext指針是為了將節(jié)點串在散列表的拉鏈中勾哩。
③LRU緩存淘汰算法的3個主要操作如何做到時間復雜度為O(1)呢抗蠢？
首先举哟，我們明確一點就是鏈表本身插入和刪除一個節(jié)點的時間復雜度為O(1)，因為只需更改幾個指針指向即可迅矛。
接著妨猩，來分析查找操作的時間復雜度。當要查找一個數(shù)據(jù)時秽褒，通過散列表可實現(xiàn)在O(1)時間復雜度找到該數(shù)據(jù)壶硅，再加上前面說的插入或刪除的時間復雜度是O(1)，所以我們總操作的時間復雜度就是O(1)销斟。

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

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

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

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

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

2.插入、刪除和隨機訪問的時間復雜度

數(shù)組：插入宙搬、刪除的時間復雜度是O(n)笨腥，隨機訪問的時間復雜度是O(1)。
鏈表：插入勇垛、刪除的時間復雜度是O(1)脖母，隨機訪問的時間復雜端是O(n)。

3.數(shù)組缺點

1）若申請內(nèi)存空間很大闲孤，比如100M谆级，但若內(nèi)存空間沒有100M的連續(xù)空間時，則會申請失敗，盡管內(nèi)存可用空間超過100M哨苛。
2）大小固定鸽凶，若存儲空間不足币砂，需進行擴容建峭，一旦擴容就要進行數(shù)據(jù)復制，而這時非常費時的决摧。

4.鏈表缺點

1）內(nèi)存空間消耗更大亿蒸，因為需要額外的空間存儲指針信息。
2）對鏈表進行頻繁的插入和刪除操作掌桩，會導致頻繁的內(nèi)存申請和釋放边锁，容易造成內(nèi)存碎片，如果是Java語言波岛，還可能會造成頻繁的GC（自動垃圾回收器）操作茅坛。

5.如何選擇？

數(shù)組簡單易用则拷，在實現(xiàn)上使用連續(xù)的內(nèi)存空間贡蓖，可以借助CPU的緩沖機制預讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高煌茬，而鏈表在內(nèi)存中并不是連續(xù)存儲斥铺，所以對CPU緩存不友好，沒辦法預讀坛善。
如果代碼對內(nèi)存的使用非沉乐苛刻，那數(shù)組就更適合眠屎。