快捷導(dǎo)航

Java的List集合框架之LinkedList詳細(xì)解析

更新時(shí)間：2023年11月16日 10:17:11 作者：進(jìn)擊的貓

這篇文章主要介紹了Java的List集合框架之LinkedList詳細(xì)解析,LinkedList底層是內(nèi)部Node類的存儲,prev、next、item值,同時(shí)最外層還有first、last節(jié)點(diǎn),需要的朋友可以參考下

(一)List子父層級：

LinkedList繼承實(shí)現(xiàn)關(guān)系

List接口繼承于Collection，Collection繼承Iterable;
LIst接口實(shí)現(xiàn)類分為：Vector、ArrayList、LinkedList;

(二)List實(shí)現(xiàn)類

1、LinkedList實(shí)現(xiàn)類

（1）LinkedList底層是內(nèi)部Node類的存儲，prev、next、item值，同時(shí)最外層還有first、last節(jié)點(diǎn)；

（2）LinkedList是線程不安全的，多線程環(huán)境會報(bào)并發(fā)修改異常java.util.ConcurrentModificationException。

（3）LinkedList無擴(kuò)容機(jī)制，底層是雙向鏈表結(jié)構(gòu)，內(nèi)部是Node結(jié)構(gòu)，外部是first、last首尾節(jié)點(diǎn)。

2、常見源碼

（1）構(gòu)造方法：

//無參構(gòu)造，有參構(gòu)造是將一個(gè)LinkedList對象傳入進(jìn)行追加（數(shù)據(jù)復(fù)制）
	public LinkedList() {   }

（2）add方法：

   public boolean add(E e) {
      linkLast(e);//將e以尾插法入鏈表
      return true;
    }
    //新數(shù)據(jù)入鏈表
    void linkLast(E e) {
        final Node<E> l = last;//獲取尾節(jié)點(diǎn)
        final Node<E> newNode = new Node<>(l, e, null);//調(diào)用Node構(gòu)造方法進(jìn)行入鏈表
        last = newNode;//修改最新尾節(jié)點(diǎn)
        if (l == null)//判定是否為第一個(gè)鏈表節(jié)點(diǎn)
            first = newNode;//設(shè)置為第一個(gè)節(jié)點(diǎn)
        else
            l.next = newNode;//將新節(jié)點(diǎn)與舊節(jié)點(diǎn)相連
        size++;//數(shù)量自增
        modCount++;//操作鏈表自增
    }
    //內(nèi)部類Node，用于鏈表底層數(shù)據(jù)存儲
    private static class Node<E> {
        E item;//存儲值類型泛型
        Node<E> next;//下一節(jié)點(diǎn)
        Node<E> prev;//上一節(jié)點(diǎn)
        //基于構(gòu)造方法進(jìn)行鏈表構(gòu)造
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;//當(dāng)前節(jié)點(diǎn)存儲值
            this.next = next;//設(shè)置當(dāng)前新節(jié)點(diǎn)的下一節(jié)點(diǎn)值
            this.prev = prev;//設(shè)置當(dāng)前新節(jié)點(diǎn)的上一節(jié)點(diǎn)值
        }
    }

（3）remove方法：

 //列舉根據(jù)值刪除,不列舉按索引刪除remove，邏輯大體差不多
  public boolean remove(Object o) {
     if (o == null) {//空值刪除
         for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null) {
                 unlink(x);//調(diào)用刪除方法
                 return true;
             }
         }
     } else {
         for (Node<E> x = first; x != null; x = x.next) {
             if (o.equals(x.item)) {
                 unlink(x);//調(diào)用刪除方法
                 return true;
             }
         }
     }
     return false;
   }
   //刪除節(jié)點(diǎn)方法，將節(jié)點(diǎn)的前后節(jié)點(diǎn)進(jìn)行連接，然后將自身置空，其中判定首節(jié)點(diǎn)和尾節(jié)點(diǎn)為空處理
   E unlink(Node<E> x) {
       final E element = x.item;//刪除節(jié)點(diǎn)值
       final Node<E> next = x.next;//刪除節(jié)點(diǎn)的下一節(jié)點(diǎn)
       final Node<E> prev = x.prev;//刪除節(jié)點(diǎn)的上一節(jié)點(diǎn)
       if (prev == null) {//上一節(jié)點(diǎn)那為空
           first = next;//設(shè)置新的首節(jié)點(diǎn)
       } else {
           prev.next = next;//將刪節(jié)點(diǎn)的前后鏈接（前節(jié)點(diǎn)）
           x.prev = null;//置空當(dāng)前節(jié)點(diǎn)的prev值
       }
       if (next == null) {//刪除節(jié)點(diǎn)下一節(jié)點(diǎn)為空
           last = prev;//設(shè)置新的尾節(jié)點(diǎn)
       } else {
           next.prev = prev;//刪除節(jié)點(diǎn)的前后鏈接（針對后節(jié)點(diǎn)）
           x.next = null;//置空當(dāng)前節(jié)點(diǎn)的next值
       }
       x.item = null;//置空當(dāng)前節(jié)點(diǎn)值
       size--;//數(shù)量減一
       modCount++;//操作次數(shù)自增
       return element;//返回刪除節(jié)點(diǎn)值
   }

（4）get方法：

 public E get(int index) {
    checkElementIndex(index);//是否在正常范圍內(nèi)，index>=0&&index<size
     return node(index).item;//返回指定索引節(jié)點(diǎn)值
 }
 //根據(jù)索引值返回節(jié)點(diǎn),根據(jù)二分法(折半)查找
 Node<E> node(int index) {
     if (index < (size >> 1)) {//前半部分查找
         Node<E> x = first;//首節(jié)點(diǎn)
         for (int i = 0; i < index; i++)
             x = x.next;//獲得指定索引節(jié)點(diǎn)
         return x;//返回節(jié)點(diǎn)
     } else {
         Node<E> x = last;//尾節(jié)點(diǎn)
         for (int i = size - 1; i > index; i--)
             x = x.prev;//從后往前查找，找到指定索引節(jié)點(diǎn)
         return x;//返回節(jié)點(diǎn)
     }
 }

（5）set方法：

 //指定索引位置進(jìn)行設(shè)值
  public E set(int index, E element) {
      checkElementIndex(index);//檢查索引是否合法
      Node<E> x = node(index);//獲取索引節(jié)點(diǎn)
      E oldVal = x.item;//原索引節(jié)點(diǎn)值
      x.item = element;//設(shè)值
      return oldVal;//返回舊值
  }