摘要:經(jīng)常和一起被提及。本文分析的具體實(shí)現(xiàn)。其中是雙端隊(duì)列接口,所以可以當(dāng)作是棧隊(duì)列或者雙端隊(duì)隊(duì)列。注意最后一個(gè)方法,這個(gè)方法是在指定的位置插入元素。首先判斷位置是否越界,然后判斷是不是最后一個(gè)位置。
簡(jiǎn)介
LinkedList是一個(gè)常用的集合類,用于順序存儲(chǔ)元素。LinkedList經(jīng)常和ArrayList一起被提及。大部分人應(yīng)該都知道ArrayList內(nèi)部采用數(shù)組保存元素,適合用于隨機(jī)訪問比較多的場(chǎng)景,而隨機(jī)插入、刪除等操作因?yàn)橐苿?dòng)元素而比較慢。LinkedList內(nèi)部采用鏈表的形式存儲(chǔ)元素,隨機(jī)訪問比較慢,但是插入、刪除元素比較快,一般認(rèn)為時(shí)間復(fù)雜都是O(1)(需要查找元素時(shí)就不是了,下面會(huì)說(shuō)明)。本文分析LinkedList的具體實(shí)現(xiàn)。
繼承關(guān)系public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable
LinkedList繼承了一個(gè)抽象類AbstractSequentialList,這個(gè)類就是用調(diào)用ListIterator實(shí)現(xiàn)了元素的增刪查改,比如add方法:
public void add(int index, E element) { try { listIterator(index).add(element); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } }
不過(guò)這些方法在LinkedList中被復(fù)寫了。
LinkedList實(shí)現(xiàn)了List、Deque、Cloneable以及Serializable接口。其中Deque是雙端隊(duì)列接口,所以LinkedList可以當(dāng)作是棧、隊(duì)列或者雙端隊(duì)隊(duì)列。
內(nèi)部變量transient int size = 0; transient Nodefirst; transient Node last;
總共就三個(gè)內(nèi)部變量,size是元素個(gè)數(shù),first是指向第一個(gè)元素的指針,last則指向最后一個(gè)。元素在內(nèi)部被封裝成Node對(duì)象,這是一個(gè)內(nèi)部類,看一下它的代碼:
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
可以看到這是一個(gè)雙向鏈表的結(jié)構(gòu),每個(gè)節(jié)點(diǎn)保存它的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。
私有方法LinkedList內(nèi)部有幾個(gè)關(guān)鍵的私有方法,它們實(shí)現(xiàn)了鏈表的插入、刪除等操作。比如在表頭插入:
private void linkFirst(E e) { final Nodef = first; //先保存當(dāng)前頭節(jié)點(diǎn) //創(chuàng)建一個(gè)新節(jié)點(diǎn),節(jié)點(diǎn)值為e,前驅(qū)節(jié)點(diǎn)為空,后繼節(jié)點(diǎn)為當(dāng)前頭節(jié)點(diǎn) final Node newNode = new Node<>(null, e, f); first = newNode; //讓first指向新節(jié)點(diǎn) if (f == null) //如果鏈表原來(lái)為空,把last指向這個(gè)唯一的節(jié)點(diǎn) last = newNode; else · //否則原來(lái)的頭節(jié)點(diǎn)的前驅(qū)指向新的頭節(jié)點(diǎn) f.prev = newNode; size++; modCount++; }
其實(shí)就是雙向鏈表的插入操作,調(diào)整指針的指向,時(shí)間復(fù)雜度為O(1),學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的應(yīng)該很容易看懂。其它還有幾個(gè)類似的方法:
//尾部插入 void linkLast(E e) { final Node公開方法l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) //如果鏈表原來(lái)為空,讓first指向這個(gè)唯一的節(jié)點(diǎn) first = newNode; else l.next = newNode; size++; modCount++; } //中間插入 void linkBefore(E e, Node succ) { // assert succ != null; final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } //刪除頭節(jié)點(diǎn) private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; //先保存下一個(gè)節(jié)點(diǎn) f.item = null; f.next = null; // help GC first = next; //讓first指向下一個(gè)節(jié)點(diǎn) if (next == null) //如果下一個(gè)節(jié)點(diǎn)為空,說(shuō)明鏈表原來(lái)只有一個(gè)節(jié)點(diǎn),現(xiàn)在成空鏈表了,要把last指向null last = null; else //否則下一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)要置為null next.prev = null; size--; modCount++; return element; } //刪除尾節(jié)點(diǎn) private E unlinkLast(Node l) { // assert l == last && l != null; final E element = l.item; final Node prev = l.prev; //保存前一個(gè)節(jié)點(diǎn) l.item = null; l.prev = null; // help GC last = prev; //last指向前一個(gè)節(jié)點(diǎn) if (prev == null) //與頭節(jié)點(diǎn)刪除一樣,判斷是否為空 first = null; else prev.next = null; size--; modCount++; return element; } //從鏈表中間刪除節(jié)點(diǎn) E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; //保存前驅(qū)節(jié)點(diǎn) final Node prev = x.prev; //保存后繼節(jié)點(diǎn) if (prev == null) { //前驅(qū)為空,說(shuō)明刪除的是頭節(jié)點(diǎn),first要指向下一個(gè)節(jié)點(diǎn) first = next; } else { //否則前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)變?yōu)楫?dāng)前刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) prev.next = next; x.prev = null; } if (next == null) { //判斷后繼是否為空,與前驅(qū)節(jié)點(diǎn)是否為空的邏輯類似 last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
公開的方法幾乎都是調(diào)用上面幾個(gè)方法實(shí)現(xiàn)的,例如add方法:
public boolean add(E e) { linkLast(e); return true; } public boolean add(E e) { linkLast(e); return true; } public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
這些方法的實(shí)現(xiàn)都很簡(jiǎn)單。注意最后一個(gè)方法add(int index, E element),這個(gè)方法是在指定的位置插入元素。首先判斷位置是否越界,然后判斷是不是最后一個(gè)位置。如果是就直接插入鏈表末尾,否則調(diào)用linkBefore(element, node(index)方法。這里在傳參數(shù)的時(shí)候又調(diào)用了node(index),這個(gè)方法的目的是找到這個(gè)位置的節(jié)點(diǎn)對(duì)象,代碼如下:
Nodenode(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
這里有個(gè)小技巧是先判斷位置是在鏈表的前半段還是后半段,然后決定從鏈表的頭還是尾去尋找節(jié)點(diǎn)。要注意的是遍歷鏈表尋找節(jié)點(diǎn)的時(shí)間復(fù)雜度是O(n),即使做了位置的判斷,最壞情況下也要遍歷鏈表中一半的元素。所以此時(shí)插入操作的時(shí)間復(fù)雜度就不是O(1),而是O(n/2)+O(1)。用于查找指定位置元素的get(int index)方法便是調(diào)用node實(shí)現(xiàn)的:
public E get(int index) { checkElementIndex(index); return node(index).item; }
再看一下remove方法:
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } public boolean remove(Object o) { if (o == null) { for (Nodex = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
第一個(gè)remove(int index)方法同樣要調(diào)用node(index)尋找節(jié)點(diǎn)。而第二個(gè)方法remove(Object o)是刪除指定元素,這個(gè)方法要依次遍歷節(jié)點(diǎn)進(jìn)行元素的比較,最壞情況下要比較到最后一個(gè)元素,比調(diào)用node方法更慢,時(shí)間復(fù)雜度為O(n)。另外從這個(gè)方法可以看出LinkedList的元素可以是null。
總結(jié)LinkedList基于雙向鏈表實(shí)現(xiàn),元素可以為null。
LinkedList插入、刪除元素比較快,如果只要調(diào)整指針的指向那么時(shí)間復(fù)雜度是O(1),但是如果針對(duì)特定位置需要遍歷時(shí),時(shí)間復(fù)雜度是O(n)。
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/65406.html
摘要:刪除元素作為雙端隊(duì)列,刪除元素也有兩種方式,一種是隊(duì)列首刪除元素,一種是隊(duì)列尾刪除元素。作為,又要支持中間刪除元素,所以刪除元素一個(gè)有三個(gè)方法,分別如下。在中間刪除元素比較低效,首先要找到刪除位置的節(jié)點(diǎn),再修改前后指針,時(shí)間復(fù)雜度為。 介紹 LinkedList是一個(gè)以雙向鏈表實(shí)現(xiàn)的List,它除了作為L(zhǎng)ist使用,還可以作為隊(duì)列或者棧來(lái)使用,它是怎么實(shí)現(xiàn)的呢?讓我們一起來(lái)學(xué)習(xí)吧。 繼...
摘要:前言在上篇文章中我們對(duì)對(duì)了詳細(xì)的分析,今天我們來(lái)說(shuō)一說(shuō)。他們之間有什么區(qū)別呢最大的區(qū)別就是底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)不一樣,是數(shù)組實(shí)現(xiàn)的具體看上一篇文章,是鏈表實(shí)現(xiàn)的。至于其他的一些區(qū)別,可以說(shuō)大部分都是由于本質(zhì)不同衍生出來(lái)的不同應(yīng)用。 前言 在上篇文章中我們對(duì)ArrayList對(duì)了詳細(xì)的分析,今天我們來(lái)說(shuō)一說(shuō)LinkedList。他們之間有什么區(qū)別呢?最大的區(qū)別就是底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)不一樣,...
摘要:表明該類是可以序列化的。與對(duì)比并沒有實(shí)現(xiàn),而實(shí)現(xiàn)表明其支持快速通常是固定時(shí)間隨機(jī)訪問。此接口的主要目的是允許一般的算法更改其行為,從而在將其應(yīng)用到隨機(jī)或連續(xù)訪問列表時(shí)能提供良好的性能。這是隨機(jī)訪問效率低的原因之一。指定節(jié)點(diǎn)不能為。 總覽 showImg(https://segmentfault.com/img/bVbsIzr?w=1007&h=600); 定義 public class...
摘要:常用集合使用場(chǎng)景分析過(guò)年前的最后一篇,本章通過(guò)介紹,,,底層實(shí)現(xiàn)原理和四個(gè)集合的區(qū)別。和都是線程安全的,不同的是前者使用類,后者使用關(guān)鍵字。面試官會(huì)認(rèn)為你是一個(gè)基礎(chǔ)扎實(shí),內(nèi)功深厚的人才到這里常用集合使用場(chǎng)景分析就結(jié)束了。 Java 常用List集合使用場(chǎng)景分析 過(guò)年前的最后一篇,本章通過(guò)介紹ArrayList,LinkedList,Vector,CopyOnWriteArrayList...
摘要:一源碼分析本文分析雙向鏈表的查詢操作源碼實(shí)現(xiàn)。中源程序中,的查詢操作,通過(guò)函數(shù)實(shí)現(xiàn)。源程序中使用循環(huán)進(jìn)行遍歷。表示鏈表元素索引,初值為。針對(duì)空元素的情況,用循環(huán)遍歷,查找元素為的節(jié)點(diǎn),并返回索引。 一、contains源碼分析 本文分析雙向鏈表LinkedList的查詢操作源碼實(shí)現(xiàn)。jdk中源程序中,LinkedList的查詢操作,通過(guò)contains(Object o)函數(shù)實(shí)現(xiàn)。具體...
閱讀 1399·2021-09-02 09:53
閱讀 2667·2021-07-29 13:50
閱讀 1715·2019-08-30 11:07
閱讀 1571·2019-08-30 11:00
閱讀 1450·2019-08-29 14:00
閱讀 1844·2019-08-29 12:52
閱讀 2560·2019-08-29 11:11
閱讀 3415·2019-08-26 12:23