linkedList是Java List類型的集合類的一種實現(xiàn)，此外，linkedList還實現(xiàn)了Deque接口。本文基于Java1.8，對于linkedList的實現(xiàn)原理做一下詳細講解。
一、linkedList實現(xiàn)原理總結(jié)
linkedList的實現(xiàn)原理總結(jié)如下：
①數(shù)據(jù)存儲是基于雙向鏈表實現(xiàn)的。
②插入數(shù)據(jù)很快。先是在雙向鏈表中找到要插入節(jié)點的位置index，找到之后，再插入一個新節(jié)點。雙向鏈表查找index位置的節(jié)點時，有一個加速動作：若index<雙向鏈表長度的1/2，則從前向后查找;否則，從后向前查找。
③刪除數(shù)據(jù)很快。先是在雙向鏈表中找到要插入節(jié)點的位置index，找到之后，進行如下操作：node.previous.next=node.next;node.next.previous=node.previous;node=null。查找節(jié)點過程和插入一樣。
④獲取數(shù)據(jù)很慢，需要從Head節(jié)點進行查找。
⑤遍歷數(shù)據(jù)很慢，每次獲取數(shù)據(jù)都需要從頭開始。
二、ArrayList的實現(xiàn)原理詳解
1.linkedList概述：
List接口的鏈接列表實現(xiàn)。實現(xiàn)所有可選的列表操作，并且允許所有元素（包括null）。除了實現(xiàn)List接口外，linkedList類還為在列表的開頭及結(jié)尾get、remove和insert元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。
此類實現(xiàn)Deque接口，為add、poll提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。
所有操作都是按照雙重鏈接列表的需要執(zhí)行的。在列表中編索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）。
注意，此實現(xiàn)不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結(jié)構(gòu)上修改了該列表，則它必須保持外部同步。（結(jié)構(gòu)修改指添加或刪除一個或多個元素的任何操作；僅設(shè)置元素的值不是結(jié)構(gòu)修改。）這一般通過對自然封裝該列表的對象進行同步操作來完成。如果不存在這樣的對象，則應(yīng)該使用Collections.synchronizedList方法來“包裝”該列表。最好在創(chuàng)建時完成這一操作，以防止對列表進行意外的不同步訪問，如下所示：
List list=Collections.synchronizedList(new linkedList(...));
此類的iterator和listIterator方法返回的迭代器是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對列表進行修改，除非通過迭代器自身的remove或add方法，其他任何時間任何方式的修改，迭代器都將拋出ConcurrentModificationException。因此，面對并發(fā)的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發(fā)生不確定行為的風(fēng)險。
注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發(fā)修改時，不可能作出任何硬性保證?？焖偈〉鞅M最大努力拋出ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯誤。
以上就是長沙牛耳教育java培訓(xùn)機構(gòu)的小編針對“java中的linkedlist的實現(xiàn)原理”的內(nèi)容進行的回答，希望對大家有所幫助，如有疑問，請在線咨詢，有專業(yè)老師隨時為你服務(wù)。
