當前位置:網站首頁>數組與鏈錶
數組與鏈錶
2022-01-26 23:12:25 【智慧的人不要禿頭】
作為線性錶的兩種存儲方式 —— 鏈錶和數組,這對相愛相殺的好基友有著各自的優缺點。
數組:
數組,所有元素都連續的存儲於一段內存中,且每個元素占用的內存大小相同。這使得數組具備了通過下標快速訪問數據的能力。
但連續存儲的缺點也很明顯,增加容量,增删元素的成本很高,時間複雜度均為 O(n)。
增加數組容量需要先申請一塊新的內存,然後複制原有的元素。如果需要的話,可能還要删除原先的內存。
删除元素時需要移動被删除元素之後的所有元素以保證所有元素是連續的。
增加元素時需要移動指定比特置及之後的所有元素,然後將新增元素插入到指定比特置,如果容量不足的話還需要先進行擴容操作。
數組的優缺點:
- 優點:可以根據偏移實現快速的隨機讀寫。
- 缺點:擴容,增删元素極慢。
鏈錶:
由若幹個結點組成,每個結點包含數據域和指針域。(頭節點、尾節點)
鏈錶的存儲方式使得它可以高效的在指定比特置插入與删除,時間複雜度均為 O(1)。
鏈錶的優缺點:
優點:
(1)插入和删除速度快,保留原有的物理順序,在插入或者删除一個元素的時候,只需要改變指針指向即可。
(2)沒有空間限制,存儲元素無上限,只與內存空間大小有關.
(3)動態分配內存空間,不用事先開辟內存
(4)是內存的利用率變高
缺點:
(1)占用額外的空間以存儲指針,比較浪費空間,不連續存儲,malloc函數開辟空間碎片比較多)
(2)查找速度比較慢,因為在查找時,需要循環鏈錶。查找操作為O(n)
面試問題總結
無法高效獲取長度,無法根據偏移快速訪問元素,是鏈錶的兩個劣勢。
然而面試的時候經常碰見諸如獲取倒數第k個元素,獲取中間比特置的元素,判斷鏈錶是否存在環,判斷環的長度等和長度與比特置有關的問題。這些問題都可以通過靈活運用雙指針來解决。
如果存在環,如何判斷環的長度呢?快慢指針相遇後繼續移動,直到第二次相遇。兩次相遇間的移動次數即為環的長度。
參考:來自 <力扣>
版權聲明
本文為[智慧的人不要禿頭]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201262312247099.html
邊欄推薦
猜你喜歡
隨機推薦
- uniapp上傳圖片及組件傳值
- 瑞利年金險資金保障安全嗎?收益高不高啊?
- 華為手機USB連不上電腦的解决方法
- Flutter 2,移動金融應用開發
- 關於st25系列NFC標簽簡單介紹及st25TV系列用於門禁讀取時的注意事項總結
- 關於用ffmpeg轉手機視頻發現視頻長寬倒了的問題
- 函數 / 類模板--模板2
- 數組中的第k個最大的元素--優先級隊列、排序、堆、排序
- 單片機實例27——ADC0809A/D轉換器基本應用技術(硬件電路圖+匯編程序+C語言程序)
- Collection集合的學習
- 一場面試結束,某度員工從事Android 5年為何還是初級工程師?
- 3本書閱讀筆記【人月神話-Go語言實戰-研發能力持續成長路線】01
- PHP垃圾回收機制
- 【電子技術】什麼是LFSR?
- 死鎖?如何定比特到死鎖?如何修複死鎖?(jps和jstack兩個工具)
- 快樂寒假 22/01/20
- image
- 噴程序員?SURE?
- LDO分壓電阻計算小工具
- 面試之求一串字符串中每個字符的出現次數
- 【ISO15765_UDS&OBD診斷】-01-概述
- 【Mysql上分之路】第九篇:Mysql存儲引擎
- RHCE 第一次作業
- 2021.10.16我的第一篇博客:一切皆有可能!
- CTA-敏感行為-讀取IMEI
- 面試被問怎麼排查平時遇到的系統CPU飆高和頻繁GC,該怎麼回答?
- nuxt項目總結-綜合
- 自然語言處理學習筆記(一)
- C語言第一課
- 各比特大佬,Spark的重點難點系列暫時更新完畢
- 基於 esbuild 的 universal bundler 設計
- XCTFre逆向(四):insanity
- 理解什麼是真正的並發數
- JVM腦圖
- 【Pytorch(四)】學習如何使用 PyTorch 讀取並處理數據集
- 函數棧幀的創建與銷毀
- 構建神經網絡- 手寫字體識別案例
- 多模態生成模型ERNIE-VILG
- kotlin不容忽視的小細節
- 備戰一年,終於斬獲騰訊T3,我堅信成功是可以複制的