LinkedList是Java List類型的集合類的一種實現(xiàn)，此外，LinkedList還實現(xiàn)了Deque接口。本文基于Java1.8，對于LinkedList的實現(xiàn)原理做一下詳細講解。

一、LinkedList實現(xiàn)原理總結

LinkedList的實現(xiàn)原理總結如下：

①數據存儲是基于雙向鏈表實現(xiàn)的。

②插入數據很快。先是在雙向鏈表中找到要插入節(jié)點的位置index，找到之后，再插入一個新節(jié)點。雙向鏈表查找index位置的節(jié)點時，有一個加速動作：若index<雙向鏈表長度的1/2，則從前向后查找;否則，從后向前查找。

③刪除數據很快。先是在雙向鏈表中找到要插入節(jié)點的位置index，找到之后，進行如下操作：node.previous.next=node.next;node.next.previous=node.previous;node=null。查找節(jié)點過程和插入一樣。

④獲取數據很慢，需要從Head節(jié)點進行查找。

⑤遍歷數據很慢，每次獲取數據都需要從頭開始。

二、ArrayList的實現(xiàn)原理詳解

1.LinkedList概述：

List接口的鏈接列表實現(xiàn)。實現(xiàn)所有可選的列表操作，并且允許所有元素（包括null）。除了實現(xiàn)List接口外，LinkedList類還為在列表的開頭及結尾get、remove和insert元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。

此類實現(xiàn)Deque接口，為add、poll提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。

所有操作都是按照雙重鏈接列表的需要執(zhí)行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。

注意，此實現(xiàn)不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結構上修改了該列表，則它必須保持外部同步。（結構修改指添加或刪除一個或多個元素的任何操作；僅設置元素的值不是結構修改。）這一般通過對自然封裝該列表的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用Collections.synchronizedList方法來“包裝”該列表。最好在創(chuàng)建時完成這一操作，以防止對列表進行意外的不同步訪問，如下所示：

List list=Collections.synchronizedList(new LinkedList(...));

此類的iterator和listIterator方法返回的迭代器是快速失敗的：在迭代器創(chuàng)建之后，如果從結構上對列表進行修改，除非通過迭代器自身的remove或add方法，其他任何時間任何方式的修改，迭代器都將拋出ConcurrentModificationException。因此，面對并發(fā)的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發(fā)生不確定行為的風險。

注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發(fā)修改時，不可能作出任何硬性保證。快速失敗迭代器盡最大努力拋出ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。

以上就是動力節(jié)點java培訓機構的小編針對“java中的linkedlist的實現(xiàn)原理”的內容進行的回答，希望對大家有所幫助，如有疑問，請在線咨詢，有專業(yè)老師隨時為你服務。