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

一、LinkedList實(shí)現(xiàn)原理總結(jié)

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

①數(shù)據(jù)存儲(chǔ)是基于雙向鏈表實(shí)現(xiàn)的。

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

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

④獲取數(shù)據(jù)很慢，需要從Head節(jié)點(diǎn)進(jìn)行查找。

⑤遍歷數(shù)據(jù)很慢，每次獲取數(shù)據(jù)都需要從頭開(kāi)始。

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

1.LinkedList概述：

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

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

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

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

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

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

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

以上就是動(dòng)力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)的小編針對(duì)“java中的linkedlist的實(shí)現(xiàn)原理”的內(nèi)容進(jìn)行的回答，希望對(duì)大家有所幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢(xún)，有專(zhuān)業(yè)老師隨時(shí)為你服務(wù)。