国内一区二区在线,日韩高清不卡一区二区,久久免费福利视频

LinkedList是Java集合框架中List接口的實現之一，它以雙向鏈表的形式存儲元素。與傳統的數組相比，鏈表具有更高的靈活性，特別適用于頻繁的插入和刪除操作。讓我們從底層實現開始深

LinkedList是Java集合框架中List接口的實現之一，它以雙向鏈表的形式存儲元素。與傳統的數組相比，鏈表具有更高的靈活性，特別適用于頻繁的插入和刪除操作。讓我們從底層實現開始深入了解這個強大的數據結構。

底層數據結構

LinkedList的底層數據結構是雙向鏈表。每個節點都包含一個數據元素以及兩個引用，一個指向前一個節點（prev），一個指向下一個節點（next）。這種結構使得在鏈表中進行插入和刪除操作變得非常高效。

LinkedList的屬性及Node源碼如下：

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

    transient Node<E> first;

    transient Node<E> last;

    public LinkedList() {
    }
    
    ...
    
      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包含兩個重要的實例變量：first和last，分別指向鏈表的頭節點和尾節點。這兩個節點使得在鏈表的兩端進行操作更為高效。

size字段表示鏈表中元素的數量，通過它我們可以隨時獲取鏈表的大小。

Node類是LinkedList數據結構的基礎。每個節點都包含一個數據元素、一個指向下一個節點的引用（next），以及一個指向前一個節點的引用（prev）。

item：當前節點的數據元素。
next：下一個節點的引用。
prev：前一個節點的引用。

操作方法

篇幅有限，我們在這詳細解釋下常用的幾個方法，別的方法家人們可自行閱讀源碼

add(E e): 在鏈表尾部添加元素

add(E e): 在鏈表尾部添加元素。

// LinkedList類中的add方法
public boolean add(E e) {
    linkLast(e);
    return true;
}

linkLast(e)

// 在鏈表尾部鏈接新節點的方法
void linkLast(E e) {
    // 獲取尾節點的引用
    final Node<E> l = last;
    // 創建新節點，其前一個節點是尾節點，后一個節點為null
    final Node<E> newNode = new Node<>(l, e, null);
     // 將新節點更新為尾節點
    last = newNode;
    
    if (l == null)
        // 如果鏈表為空，同時將新節點設置為頭節點
        first = newNode;
    else
        // 否則，將原尾節點的next指向新的尾節點
        l.next = newNode;
    // 增加鏈表的大小
    size++;
    //修改計數器
    modCount++;
}

源碼詳解：

final Node<E> l = last;

通過last字段獲取鏈表的尾節點引用。這一步是為了后續創建新節點時能夠將其連接到鏈表的尾部。
final Node<E> newNode = new Node<>(l, e, null);

使用Node類的構造方法創建一個新節點，其前一個節點是鏈表的尾節點l，后一個節點為null，因為這是新的尾節點。
last = newNode;

將鏈表的last字段更新為新創建的節點，使其成為新的尾節點。

if (l == null) first = newNode;

如果鏈表為空（即尾節點為null），則將頭節點first指向新節點。因為在空鏈表中添加元素時，頭節點和尾節點都是新節點。
else l.next = newNode;

如果鏈表非空，將原尾節點的next引用指向新節點，以完成新節點的插入。

size++;

每次成功添加一個元素后，增加鏈表的大小。
modCount++;

modCount是用于迭代器的修改計數器，用于在迭代時檢測是否有其他線程修改了集合。每次對鏈表結構進行修改時，都會增加modCount的值。modCount是用于迭代器的修改計數器，用于在迭代時檢測是否有其他線程修改了集合。每次對鏈表結構進行修改時，都會增加modCount的值。

add(int index, E element): 在指定位置插入元素

  //在指定位置插入元素的方法
  public void add(int index, E element) {
  
    //參數檢查
    checkPositionIndex(index);
    //鏈表尾部插入元素
    if (index == size)
        linkLast(element);
    // 非尾部插入的情況
    else
        linkBefore(element, node(index));
}

checkPositionIndex()：參數檢查

//參數檢查
private void checkPositionIndex(int index) {
  if (!isPositionIndex(index))
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

isPositionIndex():判斷指定下標是否合法

//判斷指定下標是否合法
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

node(int index)：獲取指定位置的節點

Node<E> node(int index) {
    // assert isElementIndex(index);
     //判斷索引位置(判斷索引位于鏈表的前半部分還是后半部分，提高元素獲取的性能)
    if (index < (size >> 1)) {
        //前半部分的話從頭節點開始遍歷，通過節點的next一直查找到當前索引所在的元素
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
                                  
       //后半部分的話從尾始遍歷，通過節點的prev一直查找到當前索引所在的元素                         
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

源碼詳解：

if (index < (size >> 1)) {

>>帶符號右移運算符，一個數的二進制表示向右移動指定的位數，左側空出的位置使用原始數值的最高位進行填充。這個操作相當于將數值除以2的指定次方并向下取整。右移一位相當于除以2。

這行代碼是判斷索引位置,即判斷索引位于鏈表的前半部分還是后半部分來決定是從前往后還是從后往前遍歷鏈表，以提高元素獲取的性能。

Node<E> x = first; for (int i = 0; i < index; i++) x = x.next;

如果目標節點在鏈表的前半部分，就從頭節點 first 開始，通過next往后遍歷，找到對應索引的節點并返回。

Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev;

如果目標節點在鏈表的后半部分，就從尾節點 last 開始,通過prev往前遍歷，找到對應索引的節點并返回。

linkBefore():非尾部插入元素

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++;
}

源碼詳解：

final Node<E> pred = succ.prev;

通過 succ 節點的 prev 引用，獲取插入位置的前一個節點 pred。
final Node<E> newNode = new Node<>(pred, e, succ);

使用 Node 類的構造方法創建一個新的節點，其前一個節點是 pred，后一個節點是 succ。
succ.prev = newNode;

將后繼節點 succ 的前驅引用指向新節點 newNode，確保新節點的插入。
if (pred == null) first = newNode;

如果前驅節點為空，說明新節點插入的位置是鏈表的頭部，將鏈表的頭節點 first 指向新節點 newNode。
else pred.next = newNode;

如果前驅節點非空，將前驅節點的 next 引用指向新節點 newNode，完成新節點的插入。
size++;

每次成功添加一個元素后，增加鏈表的大小。

modCount++;

modCount是用于迭代器的修改計數器，用于在迭代時檢測是否有其他線程修改了集合。每次對鏈表結構進行修改時，都會增加modCount的值。modCount是用于迭代器的修改計數器，用于在迭代時檢測是否有其他線程修改了集合。每次對鏈表結構進行修改時，都會增加modCount的值。

remove(Object o): 從鏈表中移除指定元素

public boolean remove(Object o) {
  //處理刪除元素為null的情況
  if (o == null) {
      //遍歷鏈表
      for (Node<E> x = first; x != null; x = x.next) {
          //獲取到第一個為null的元素
          if (x.item == null) {
              //刪除元素
              unlink(x);
              return true;
          }
      }
   //處理刪除元素非null的情況
  } else {
      //遍歷鏈表
      for (Node<E> x = first; x != null; x = x.next) {
          //獲取到要刪除的元素
          if (o.equals(x.item)) {
              //刪除元素
              unlink(x);
              return true;
          }
      }
  }
  return false;
}

源碼解析：

if (o == null) {

這里首先檢查傳入的參數 o 是否為 null，分別處理 null 和非 null 兩種情況。

if (o == null) { for (Node<E> x = first; x != null; x = x.next) {...

如果要刪除的元素是 null，則通過遍歷鏈表找到第一個值為 null 的節點，然后調用 unlink(x) 方法刪除該節點。刪除成功后返回 true。如果要刪除的元素是 null，則通過遍歷鏈表找到第一個值為 null 的節點，然后調用 unlink(x) 方法刪除該節點。刪除成功后返回 true。

else { for (Node<E> x = first; x != null; x = x.next) { ...

如果要刪除的元素不為 null，則通過遍歷鏈表找到第一個值與參數 o 相等的節點，然后調用 unlink(x) 方法刪除該節點。刪除成功后返回 true。

return false;

如果遍歷完整個鏈表都沒有找到要刪除的元素，則返回 false 表示刪除失敗。

unlink(Node<E> x)：實際執行節點刪除的方法

E unlink(Node<E> x) {
  // assert x != null;
  //獲取要刪除的元素
  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;
}

源碼詳解：

final E element = x.item;

通過 x 節點的 item 字段獲取節點的數據元素，即要刪除的元素。
final Node<E> next = x.next; final Node<E> prev = x.prev;

通過 x 節點的 next 和 prev 字段獲取目標節點的后繼節點和前驅節點。

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

如果前驅節點為空，說明要刪除的節點是鏈表的頭節點，將目標節點的后繼節點 next設置為鏈表的頭節點 first 。如果前驅節點非空，將前驅節點的 next 引用指向目標節點的后繼節點，同時將目標節點的 prev 引用置為 null。
if (next == null) { last = prev; else { next.prev = prev; x.next = null; }

如果后繼節點為空，說明要刪除的節點是鏈表的尾節點，將鏈表的尾節點 last 指向目標節點的前驅節點 prev。如果后繼節點非空，將后繼節點的 prev 引用指向目標節點的前驅節點，同時將目標節點的 next 引用置為 null。

x.item = null;

將目標節點的 item 字段置為 null，幫助垃圾回收系統回收節點的數據元素。

size--; modCount++;

每次成功刪除一個節點后，減小鏈表的大小，并更新修改計數器。
return element;

最后，返回被刪除節點的數據元素。

LinkedList的優勢和劣勢

優勢

動態大小：鏈表可以動態地分配內存，不需要預先指定大小。
插入和刪除：在鏈表中插入和刪除元素更為高效，因為只需要調整節點的引用。

劣勢

隨機訪問困難：在鏈表中要訪問特定位置的元素，必須從頭結點開始遍歷，效率相對較低。
額外空間：鏈表每個節點需要額外的空間存儲引用，相比數組會占用更多的內存。

使用場景

LinkedList適用于以下場景：

頻繁的插入和刪除操作：由于鏈表的節點可以方便地插入和刪除，適用于這類操作頻繁的場景。
不需要頻繁隨機訪問：如果主要操作是在鏈表兩端進行，而不是在中間進行隨機訪問，那么鏈表是一個不錯的選擇。

總結

LinkedList作為Java集合框架中的一個重要成員，為開發者提供了一種靈活而高效的數據結構。通過深入了解其底層實現和基本特性，我們能夠更好地在實際應用中選擇和使用這一數據結構，從而優化程序的性能和效率。希望這篇文章能夠幫助你更好地理解和使用LinkedList。

聲明：所有內容來自互聯網搜索結果,不保證100%準確性,僅供參考。如若本站內容侵犯了原著者的合法權益，可聯系我們進行處理。

深度解析LinkedList

底層數據結構

操作方法

add(E e): 在鏈表尾部添加元素

add(int index, E element): 在指定位置插入元素

remove(Object o): 從鏈表中移除指定元素

LinkedList的優勢和劣勢

優勢

劣勢

使用場景

總結

小程序swiper輪播CSS3動畫及跳轉到指定swiper-item的使用

cPanel虛擬主機優化數據庫圖解

Java集合根據某個字段去重數據

windows安全中心打開一片空白怎么回事【詳解】

什么是JavaScript中的服務器發送事件？含代碼

常用數據庫連接池

優雅校驗：Guava Preconditions使用指南