鏈表和數(shù)組

數(shù)組

  • 數(shù)組是一種順序存儲(chǔ)結(jié)構(gòu)陶耍,它需要一個(gè)連續(xù)的內(nèi)存空間來(lái)存放數(shù)據(jù)奋蔚。
  • 數(shù)組隨機(jī)訪問(wèn)一個(gè)元素時(shí),可以通過(guò)下標(biāo)直接訪問(wèn)任意元素物臂,因?yàn)閿?shù)組是連續(xù)存儲(chǔ)的旺拉,所以就可以通過(guò)偏移量快速計(jì)算出元素的地址,因此數(shù)組訪問(wèn)元素的復(fù)雜度是O(1)棵磷。
  • 數(shù)組插入和刪除需要移動(dòng)大量其他元素蛾狗, 因?yàn)樗麄兪琼樞虼鎯?chǔ)的, 所以當(dāng)插入或刪除的時(shí)候仪媒,都需要給它的到來(lái)騰位置沉桌,所以復(fù)雜度是O(n)谢鹊。

鏈表

  • 鏈表是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),它不需要連續(xù)的內(nèi)存空間留凭,而是通過(guò)指針將一系列零散的內(nèi)存空間串聯(lián)起來(lái)佃扼。
  • 鏈表隨機(jī)訪問(wèn)一個(gè)元素時(shí),我們需要從節(jié)點(diǎn)開始順序遍歷整個(gè)鏈表蔼夜,直到找個(gè)目標(biāo)元素兼耀,因?yàn)樗欠沁B續(xù)存儲(chǔ)的,找的當(dāng)前元素必須找到上一個(gè)元素求冷,找到上一個(gè)元素必須又找到更上一級(jí)的元素瘤运,以此類推。 因此鏈表隨機(jī)訪問(wèn)元素的復(fù)雜度是O(n)匠题。
  • 鏈表插入和刪除元素只需要修改相鄰節(jié)點(diǎn)足以拯坟,所以復(fù)雜度是O(1)。

使用JS實(shí)現(xiàn)一個(gè)鏈表

  • 首先鏈表我們知道的它是按照順序韭山,上一個(gè)指向下一個(gè)的郁季,所以我們需要有個(gè)類來(lái)生成鏈表的數(shù)據(jù)結(jié)構(gòu)。
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
  • 然后開始實(shí)現(xiàn)一個(gè)簡(jiǎn)單的鏈表钱磅,append和print方法梦裂。當(dāng)我們第一次append的時(shí)候,這時(shí)候head是沒(méi)有值的续搀,所以我們需要生成一個(gè)head塞琼,然后到后面添加的時(shí)候,我們需要淺拷貝一個(gè)head禁舷,然后while循環(huán),找到這個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)毅往,把當(dāng)前的值賦值給最后一個(gè)節(jié)點(diǎn)的next牵咙。
class LinkNodeList {
  constructor() {
    this.head = null;
  }

  append(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      return;
    }

    let current = this.head;
    //找到鏈表最后一個(gè)節(jié)點(diǎn)
    while (current.next) {
      current = current.next;
    }

    //給最后一個(gè)節(jié)點(diǎn)的next賦值
    current.next = newNode;
  }

  print() {
    let current = this.head;
    let ret = '';
    if (!this.head) {
      console.log('No data');
      return;
    }
    while (current) {
      ret += `${current.val} -> `;
      current = current.next;
    }
    console.log(ret);
  }
}

const linkList = new LinkNodeList();

linkList.append(1);
linkList.append(2);
linkList.append(3);
linkList.append(4);
linkList.print();

203. 移除鏈表元素

image.png

這里有一個(gè)新的概念,哨兵元素攀唯,就在鏈表的頭洁桌,設(shè)置一個(gè)哨兵,它是肯定存在的侯嘀。然后使用while循環(huán)另凌,如果next值等于這個(gè)val,那么就指向下下個(gè)戒幔。

var removeElements = function (head, val) {
    let ele = {
        next: head
    }
    let p = ele
    while (p.next) {
        if (p.next.val === val) {
            p.next = p.next.next
        } else {
            p = p.next
        }
    }
    return ele.next
}; 

141. 環(huán)形鏈表

image.png

這個(gè)題就有兩個(gè)思路

  • 我們每次將值存在集合中吠谢,當(dāng)集合中存在重復(fù)的時(shí)候,就return true诗茎,否則就往里面添加工坊。
  • 快慢指針,如果是環(huán)形,兩者終能相遇王污。
var hasCycle = function (head) {
    // const cache = new Set()
    // while (head) {
    //     if (cache.has(head)) {
    //         return true;
    //     } else {
    //         cache.add(head)
    //     }
    //     head = head.next
    // }
    // return false

    let slow = head
    let fast = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if(slow === fast) return true
    }
    return false
};

146. LRU 緩存

首先我們需要知道LRU緩存是什么罢吃,LRU 是 Least Recently Used(最近最少使用)的縮寫,是一種常用的緩存淘汰策略昭齐。當(dāng)我們經(jīng)常使用的我們會(huì)放在最前面尿招,然后當(dāng)超過(guò)最大緩存數(shù)的時(shí)候,我們會(huì)淘汰最不常使用的阱驾,也就是最后一項(xiàng)數(shù)據(jù)就谜。

我們?cè)贘S中,我們可以使用到Map的數(shù)據(jù)結(jié)構(gòu)啊易,因?yàn)檫@個(gè)Map吁伺,當(dāng)我們set的時(shí)候,他是存儲(chǔ)到末尾的租谈,所以我們可以跟我們上述介紹的概念反過(guò)來(lái)篮奄。

當(dāng)我們get讀取緩存的時(shí)候,如果我們緩存有值割去,那么我們就delete當(dāng)前key窟却,然后重新set。這樣就保證我們最近使用的值在末尾呻逆。
當(dāng)我們put存值的時(shí)候夸赫,如果有值开缎,我們同樣需要?jiǎng)h除當(dāng)前key诉瓦,然后重新set, 當(dāng)我們需要Put一個(gè)新的值化戳,但是大于緩存數(shù)的時(shí)候宜雀,我們就可以淘汰Map數(shù)據(jù)結(jié)構(gòu)的第一個(gè)值(this.cache.keys().next().value)切平,然后再set新的值

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.cache = new Map()
    this.max = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (this.cache.has(key)) {
        const tmp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key,tmp)
        return tmp
    }
    return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key)
    } else if (this.cache.size >= this.max) {
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
};


/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市辐董,隨后出現(xiàn)的幾起案子悴品,更是在濱河造成了極大的恐慌,老刑警劉巖简烘,帶你破解...
    沈念sama閱讀 216,402評(píng)論 6 499
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件苔严,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡孤澎,警方通過(guò)查閱死者的電腦和手機(jī)届氢,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,377評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)亥至,“玉大人悼沈,你說(shuō)我怎么就攤上這事贱迟。” “怎么了絮供?”我有些...
    開封第一講書人閱讀 162,483評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵衣吠,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我壤靶,道長(zhǎng)缚俏,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,165評(píng)論 1 292
  • 正文 為了忘掉前任贮乳,我火速辦了婚禮忧换,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘向拆。我一直安慰自己亚茬,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,176評(píng)論 6 388
  • 文/花漫 我一把揭開白布浓恳。 她就那樣靜靜地躺著刹缝,像睡著了一般。 火紅的嫁衣襯著肌膚如雪颈将。 梳的紋絲不亂的頭發(fā)上梢夯,一...
    開封第一講書人閱讀 51,146評(píng)論 1 297
  • 那天,我揣著相機(jī)與錄音晴圾,去河邊找鬼颂砸。 笑死,一個(gè)胖子當(dāng)著我的面吹牛死姚,可吹牛的內(nèi)容都是我干的人乓。 我是一名探鬼主播,決...
    沈念sama閱讀 40,032評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼都毒,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼撒蟀!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起温鸽,我...
    開封第一講書人閱讀 38,896評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎手负,沒(méi)想到半個(gè)月后涤垫,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,311評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡竟终,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,536評(píng)論 2 332
  • 正文 我和宋清朗相戀三年蝠猬,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片统捶。...
    茶點(diǎn)故事閱讀 39,696評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡榆芦,死狀恐怖柄粹,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情匆绣,我是刑警寧澤驻右,帶...
    沈念sama閱讀 35,413評(píng)論 5 343
  • 正文 年R本政府宣布,位于F島的核電站崎淳,受9級(jí)特大地震影響堪夭,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜拣凹,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,008評(píng)論 3 325
  • 文/蒙蒙 一森爽、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧嚣镜,春花似錦爬迟、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至捧请,卻和暖如春凡涩,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背疹蛉。 一陣腳步聲響...
    開封第一講書人閱讀 32,815評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工活箕, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人可款。 一個(gè)月前我還...
    沈念sama閱讀 47,698評(píng)論 2 368
  • 正文 我出身青樓育韩,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親闺鲸。 傳聞我的和親對(duì)象是個(gè)殘疾皇子筋讨,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,592評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容

  • 1. 遍歷速度 雖然遍歷數(shù)組和鏈表的時(shí)間復(fù)雜度都是O(n),但是在實(shí)際中數(shù)組的速度要比鏈表快,這是為什么呢摸恍? 數(shù)組...
    cxq要努力閱讀 504評(píng)論 0 0
  • 鏈表 鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)悉罕,是用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)數(shù)據(jù),存儲(chǔ)單元不一定是連續(xù)的立镶。數(shù)據(jù)元素隨機(jī)存儲(chǔ)壁袄,并通...
    小李不木閱讀 736評(píng)論 0 0
  • 1鏈表是什么? 鏈表是一種上一個(gè)元素的引用指向下一個(gè)元素的存儲(chǔ)結(jié)構(gòu)媚媒,鏈表通過(guò)指針來(lái)連接元素與元素嗜逻; 鏈表是線性表的...
    大寶的愛情閱讀 294評(píng)論 0 1
  • 二者都屬于一種數(shù)據(jù)結(jié)構(gòu) 從邏輯結(jié)構(gòu)來(lái)看 1. 數(shù)組必須事先定義固定的長(zhǎng)度(元素個(gè)數(shù)),不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況...
    Lee堅(jiān)武閱讀 1,216評(píng)論 0 50
  • 數(shù)組和列表很相似缭召,都是有序的元素集合栈顷。他們之間的特點(diǎn)列在了下面: 數(shù)組 array 數(shù)組在內(nèi)存中逆日,數(shù)組是一塊連續(xù)的...
    無(wú)敵的肉包閱讀 307評(píng)論 0 1