LinkedList與ArrayList都是List接口的具體實(shí)現(xiàn)類。LinkedList與ArrayList在功能上也是大體一致，但是因?yàn)閮烧呔唧w的實(shí)現(xiàn)方式不一致，所以在進(jìn)行一些相同操作的時(shí)候，其效率也是有差別的。
對(duì)于抽象的數(shù)據(jù)結(jié)構(gòu)——線性表而言，線性表分為兩種，一種是順序存儲(chǔ)結(jié)構(gòu)的順序表，另一種是通過指針來描述其邏輯位置的鏈表。
針對(duì)于具體的Java實(shí)現(xiàn)：
順序存儲(chǔ)的順序表是用數(shù)組來實(shí)現(xiàn)的，以數(shù)組為基礎(chǔ)進(jìn)行封裝各種操作而形成的List為ArrayList
鏈表是用指針來描述其邏輯位置，在Java中以雙向鏈表為基礎(chǔ)進(jìn)行封裝各種操作而形成的List為L(zhǎng)inkedList
針對(duì)插入與刪除操作，ArrayList每插入一個(gè)元素，首先需要判斷數(shù)組的空間夠不夠，不夠要進(jìn)行擴(kuò)容，在有足夠的空間的基礎(chǔ)上，在指定的index位置上插入元素，但是該index及以后的元素都要后移。雖然刪除操作不需要判斷空間夠不夠，但同樣需要該index及以后的元素向前移動(dòng)，這些移動(dòng)的操作會(huì)增加時(shí)間的復(fù)雜度。但是對(duì)于LinkedList就不一樣，因?yàn)槭褂弥羔榿碇甘酒溥壿嫷奈恢?，所以插入與刪除的操作的時(shí)間復(fù)雜度都是 ** O(1) **
雖然對(duì)于ArrayList而言，插入與刪除的時(shí)間復(fù)雜度很高，但是對(duì)于查找指定位置的元素這種操作而言，就非常的快，因?yàn)榭梢酝ㄟ^數(shù)組直接得到該下標(biāo)對(duì)應(yīng)的元素。反而，LinkedList而言，無法直接返回指定位置的元素，需要一個(gè)個(gè)查詢，其時(shí)間的復(fù)雜度就是 ** O(n) **
與實(shí)現(xiàn)ArrayList教程一樣，實(shí)現(xiàn)的目的主要在于練手以及掌握官方實(shí)現(xiàn)的原理和一些技巧，因此很多需要與其他類配合的方法和功能，就先不在這里實(shí)現(xiàn)如iterator等
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式