欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java中集合LinkedList的原理與使用方法

 更新時間:2019年06月30日 08:43:35   作者:工匠初心  
這篇文章主要給大家介紹了關于Java中集合LinkedList的原理與使用方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面來一起學習學習吧

前言

LinkedList和ArrayList一樣是集合List的實現(xiàn)類,雖然較之ArrayList,其使用場景并不多,但同樣有用到的時候,那么接下來,我們來認識一下它。

一. 定義一個LinkedList

public static void main(String[] args) {
 List<String> stringList = new LinkedList<>();
 List<String> tempList = new ArrayList<>();
 tempList.add("牛魔王");
 tempList.add("蛟魔王");
 tempList.add("鵬魔王");
 tempList.add("獅駝王");
 tempList.add("獼猴王");
 tempList.add("禺賊王");
 tempList.add("美猴王");
 List<String> stringList2 = new LinkedList<>(tempList);
}

上面代碼中采用了兩種方式來定義LinkedList,可以定義一個空集合,也可以傳遞已有的集合,將其轉化為LinkedList。我們看一下源碼

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
 transient int size = 0;

 /**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 * (first.prev == null && first.item != null)
 */
 transient Node<E> first;

 /**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 * (last.next == null && last.item != null)
 */
 transient Node<E> last;

 /**
 * Constructs an empty list.
 */
 public LinkedList() {
 }

 /**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
 public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }
}

LinkedList繼承了AbstractSequentialList類,實現(xiàn)了List接口,AbstractSequentialList中已經實現(xiàn)了很多方法,如get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index),這些方法是我們集合操作時使用最多的,不過這些方法在LinkedList中都已經被重寫了,而抽象方法在LinkedList中有了具體實現(xiàn)。因此我們回到LinkedList類

LinkedList類中定義了三個變量

size:集合的長度

first:雙向鏈表頭部節(jié)點

last:雙向鏈表尾部節(jié)點

針對first變量和last變量,我們看到是Node類的實體,這是一個靜態(tài)內部類,關于靜態(tài)內部類的講解,我們在static五大應用場景一章已經有說明

private static class Node<E> {
 E item;
 Node<E> next;
 Node<E> prev;
 Node(Node<E> prev, E element, Node<E> next) {
 this.item = element;
 this.next = next;
 this.prev = prev;
 }
}

我們知道LinkedList是通過雙向鏈表實現(xiàn)的,而雙向鏈表就是通過Node類來體現(xiàn)的,類中通過item變量保存了當前節(jié)點的值,通過next變量指向下一個節(jié)點,通過prev變量指向上一個節(jié)點。

二. LinkedList常用方法

1. get(int index)

我們知道隨機讀取元素不是LinkedList所擅長的,讀取效率比起ArrayList也低得多,那么我來看一下為什么

public E get(int index) {
 checkElementIndex(index);
 return node(index).item;
}

/**
 * 返回一個指定索引的非空節(jié)點.
 */
Node<E> node(int index) {
 // assert isElementIndex(index);

 if (index < (size >> 1)) {
 Node<E> x = first;
 for (int i = 0; i < index; i++)
 x = x.next;
 return x;
 } else {
 Node<E> x = last;
 for (int i = size - 1; i > index; i--)
 x = x.prev;
 return x;
 }
}

從上述代碼中我們可以看到get(int index)方法是通過node(int index)來實現(xiàn)的,它的實現(xiàn)機制是:

比較傳入的索引參數(shù)index與集合長度size/2,如果是index小,那么從第一個順序循環(huán),直到找到為止;如果index大,那么從最后一個倒序循環(huán),直到找到為止。也就是說越靠近中間的元素,調用get(int index方法遍歷的次數(shù)越多,效率也就越低,而且隨著集合的越來越大,get(int index)執(zhí)行性能也會指數(shù)級降低。因此在使用LinkedList的時候,我們不建議使用這種方式讀取數(shù)據,可以使用getFirst(),getLast()方法,將直接用到類中的first和last變量。

2. add(E e) 和 add(int index, E element)

大家都在說LinkedList插入、刪除操作效率比較高,以stringList.add(“豬八戒”)為例來看到底發(fā)生了什么?

在LinkedList中我們找到add(E e)方法的源碼

public boolean add(E e) {
 linkLast(e);
 return true;
}

/**
 * 設置元素e為最后一個元素
*/
void linkLast(E e) {
 final Node<E> l = last;
 final Node<E> newNode = new Node<>(l, e, null);
 last = newNode;
 if (l == null)
 first = newNode;
 else
 l.next = newNode;
 size++;
 modCount++;
}

很好理解:

情況1:假如stringList為空,那么添加進來的node就是first,也是last,這個node的prev和next都為null;

情況2:假如stringList不為空,那么添加進來的node就是last,node的prev指向以前的最后一個元素,node的next為null;同時以前的最后一個元素的next.

而如果通過stringList.add(1, “豬八戒”)這種方式將元素添加到集合中呢?

//在指定位置添加一個元素
public void add(int index, E element) {
 checkPositionIndex(index);
 if (index == size)
 linkLast(element);
 else
 linkBefore(element, node(index));
}

/**
 * 在一個非空節(jié)點前插入一個元素
 */
void linkBefore(E e, Node<E> succ) {
 // assert succ != null;
 final Node<E> pred = succ.prev;
 final Node<E> newNode = new Node<>(pred, e, succ);
 succ.prev = newNode;
 if (pred == null)
 first = newNode;
 else
 pred.next = newNode;
 size++;
 modCount++;
}

其實從代碼中看到和add(E e)的代碼實現(xiàn)沒有本質區(qū)別,都是通過新建一個Node實體,同時指定其prev和next來實現(xiàn),不同點在于需要調用node(int index)通過傳入的index來定位到要插入的位置,這個也是比較耗時的,參考上面的get(int index)方法。

其實看到這里,大家也都明白了。

LinkedList插入效率高是相對的,因為它省去了ArrayList插入數(shù)據可能的數(shù)組擴容和數(shù)據元素移動時所造成的開銷,但數(shù)據擴容和數(shù)據元素移動卻并不是時時刻刻都在發(fā)生的。

3. remove(Object o) 和 remove(int index)

這里removeFirst()和removeLast()就不多說了,會用到類中定義的first和last變量,非常簡單,我們看一下remove(Object o) 和 remove(int index)源碼

//刪除某個對象
public boolean remove(Object o) {
 if (o == null) {
 for (Node<E> x = first; x != null; x = x.next) {
 if (x.item == null) {
 unlink(x);
 return true;
 }
 }
 } else {
 for (Node<E> x = first; x != null; x = x.next) {
 if (o.equals(x.item)) {
 unlink(x);
 return true;
 }
 }
 }
 return false;
}
//刪除某個位置的元素
public E remove(int index) {
 checkElementIndex(index);
 return unlink(node(index));
}
//刪除某節(jié)點,并將該節(jié)點的上一個節(jié)點(如果有)和下一個節(jié)點(如果有)關聯(lián)起來
E unlink(Node<E> x) {
 final E element = x.item;
 final Node<E> next = x.next;
 final Node<E> prev = x.prev;

 if (prev == null) {
 first = next;
 } else {
 prev.next = next;
 x.prev = null;
 }

 if (next == null) {
 last = prev;
 } else {
 next.prev = prev;
 x.next = null;
 }

 x.item = null;
 size--;
 modCount++;
 return element;
}

其實實現(xiàn)都非常簡單,先找到要刪除的節(jié)點,remove(Object o)方法遍歷整個集合,通過 == 或 equals方法進行判斷;remove(int index)通過node(index)方法。

4. LinkedList遍歷

我們主要列舉一下三種常用的遍歷方式,

普通for循環(huán),增強for循環(huán),Iterator迭代器

public static void main(String[] args) {
 LinkedList<Integer> list = getLinkedList();
 //通過快速隨機訪問遍歷LinkedList
 listByNormalFor(list);
 //通過增強for循環(huán)遍歷LinkedList
 listByStrengThenFor(list);
 //通過快迭代器遍歷LinkedList
 listByIterator(list);
}

/**
 * 構建一個LinkedList集合,包含元素50000個
 * @return
 */
private static LinkedList<Integer> getLinkedList() {
 LinkedList list = new LinkedList();
 for (int i = 0; i < 50000; i++){
 list.add(i);
 }
 return list;
}

/**
 * 通過快速隨機訪問遍歷LinkedList
 */
private static void listByNormalFor(LinkedList<Integer> list) {
 // 記錄開始時間
 long start = System.currentTimeMillis();
 int size = list.size();
 for (int i = 0; i < size; i++) {
 list.get(i);
 }
 // 記錄用時
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByNormalFor:" + interval + " ms");
}

/**
 * 通過增強for循環(huán)遍歷LinkedList
 * @param list
 */
public static void listByStrengThenFor(LinkedList<Integer> list){
 // 記錄開始時間
 long start = System.currentTimeMillis();
 for (Integer i : list) { }
 // 記錄用時
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByStrengThenFor:" + interval + " ms");
}

/**
 * 通過快迭代器遍歷LinkedList
 */
private static void listByIterator(LinkedList<Integer> list) {
 // 記錄開始時間
 long start = System.currentTimeMillis();
 for(Iterator iter = list.iterator(); iter.hasNext();) {
 iter.next();
 }
 // 記錄用時
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByIterator:" + interval + " ms");
}

執(zhí)行結果如下:

listByNormalFor:1067 ms
listByStrengThenFor:3 ms
listByIterator:2 ms

通過普通for循環(huán)隨機訪問的方式執(zhí)行時間遠遠大于迭代器訪問方式,這個我們可以理解,在前面的get(int index)方法中已經有過說明,那么為什么增強for循環(huán)能做到迭代器遍歷差不多的效率?

通過反編譯工具后得到如下代碼

public static void listByStrengThenFor(LinkedList<Integer> list)
 {
 long start = System.currentTimeMillis();
 Integer localInteger;
 for (Iterator localIterator = list.iterator(); localIterator.hasNext(); 
 localInteger = (Integer)localIterator.next()) {}
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByStrengThenFor:" + interval + " ms");
}

很明顯了,增強for循環(huán)遍歷時也調用了迭代器Iterator,不過多了一個賦值的過程。

還有類似于pollFirst(),pollLast()取值后刪除的方法也能達到部分的遍歷效果。

三. 總結

本文基于java8從定義一個LinkList入手,逐步展開,從源碼角度分析LinkedList雙向鏈表的結構是如何構建的,同時針對其常用方法進行分析,包括get,add,remove以及常用的遍歷方法,并簡單的說明了它的插入、刪除操作為何相對高效,而取值操作性能相對較低,若有不對之處,請批評指正,望共同進步,謝謝!

好了,以上就是這篇文章的全部內容了,希望本文的內容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對腳本之家的支持。

相關文章

  • java統(tǒng)計字符串中重復字符出現(xiàn)次數(shù)的方法

    java統(tǒng)計字符串中重復字符出現(xiàn)次數(shù)的方法

    這篇文章主要介紹了java統(tǒng)計字符串中重復字符出現(xiàn)次數(shù)的方法,涉及java針對字符串的遍歷與判斷相關操作技巧,需要的朋友可以參考下
    2016-08-08
  • 解析Spring中面向切面編程

    解析Spring中面向切面編程

    如果說 IoC 是 Spring 的核心,那么面向切面編程就是 Spring 最為重要的功能之一了,在數(shù)據庫事務中切面編程被廣泛使用
    2021-06-06
  • java stringbuffer的用法示例

    java stringbuffer的用法示例

    這篇文章主要介紹了java stringbuffer的用法示例,字符串緩沖區(qū),是一個容器(當返回到的是String時而且長度不確定,數(shù)據類型不確定時就可以用StringBuffer)其實底層還是數(shù)組,只是被封裝了,對外提供了方法,初始容量為16個字符
    2014-01-01
  • spring-boot整合Micrometer+Prometheus的詳細過程

    spring-boot整合Micrometer+Prometheus的詳細過程

    這篇文章主要介紹了springboot整合Micrometer+Prometheus的詳細過程,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧
    2024-05-05
  • java基礎之類初始化順序示例解析

    java基礎之類初始化順序示例解析

    這篇文章主要為大家介紹了java基礎之類初始化順序示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-10-10
  • java實現(xiàn)圖片轉base64字符串 java實現(xiàn)base64字符串轉圖片

    java實現(xiàn)圖片轉base64字符串 java實現(xiàn)base64字符串轉圖片

    這篇文章主要為大家詳細介紹了java實現(xiàn)圖片轉base64字符串,java實現(xiàn)base64字符串轉圖片,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-02-02
  • Async的線程池使用選擇解析

    Async的線程池使用選擇解析

    這篇文章主要為大家介紹了Async的線程池使用選擇解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-06-06
  • java實現(xiàn)上傳網絡圖片到微信臨時素材

    java實現(xiàn)上傳網絡圖片到微信臨時素材

    這篇文章主要為大家詳細介紹了java實現(xiàn)上傳網絡圖片到微信臨時素材,網絡圖片上傳到微信服務器,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-07-07
  • java自定義序列化的具體使用

    java自定義序列化的具體使用

    本文主要介紹了java自定義序列化的具體使用,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-11-11
  • Java使用ffmpeg和mencoder實現(xiàn)視頻轉碼

    Java使用ffmpeg和mencoder實現(xiàn)視頻轉碼

    這篇文章主要為大家詳細介紹了Java使用ffmpeg和mencoder實現(xiàn)視頻轉碼,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-12-12

最新評論