鏈表特點:
通過指針將不連續(xù)內(nèi)存整合起來的數(shù)據(jù)結(jié)構(gòu)妻率,不需要連續(xù)內(nèi)存
鏈表的分類:
單向鏈表乱顾,雙向鏈表,循環(huán)鏈表
查找復(fù)雜度:
刪除新增操作時間復(fù)雜度O(1) 但是等值查詢時間復(fù)雜度O(n)
應(yīng)用場景:
LRU緩存淘汰策略宫静,實現(xiàn)一個雙向鏈表走净,每次插入數(shù)據(jù)時候,先刪除鏈表中的此元素孤里,然后往表頭添加數(shù)據(jù)伏伯,表尾的數(shù)據(jù)就是最少使用的。