国产免费观看嫩草影院,国产欧美另类第一页,91福利国产在线观一区二区

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

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

底層數(shù)據(jù)結構

LinkedList的底層數(shù)據(jù)結構是雙向鏈表。每個節(jié)點都包含一個數(shù)據(jù)元素以及兩個引用，一個指向前一個節(jié)點（prev），一個指向下一個節(jié)點（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，分別指向鏈表的頭節(jié)點和尾節(jié)點。這兩個節(jié)點使得在鏈表的兩端進行操作更為高效。

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

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

item：當前節(jié)點的數(shù)據(jù)元素。
next：下一個節(jié)點的引用。
prev：前一個節(jié)點的引用。

操作方法

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

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

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

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

linkLast(e)

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

源碼詳解：

final Node<E> l = last;

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

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

將鏈表的last字段更新為新創(chuàng)建的節(jié)點，使其成為新的尾節(jié)點。

if (l == null) first = newNode;

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

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

size++;

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

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

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

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

checkPositionIndex()：參數(shù)檢查

//參數(shù)檢查
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)：獲取指定位置的節(jié)點

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

源碼詳解：

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

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

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

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

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

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

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

linkBefore():非尾部插入元素

void linkBefore(E e, Node<E> succ) {
  // assert succ != null;
  //獲取到要插入位置元素的前驅引用
  final Node<E> pred = succ.prev;
  // 創(chuàng)建新節(jié)點，其前驅引用是插入位置原節(jié)點的前驅引用，后驅引用為插入位置原節(jié)點
  final Node<E> newNode = new Node<>(pred, e, succ);
  //更新插入位置原節(jié)點的前驅引用為插入節(jié)點
  succ.prev = newNode;
  //處理前驅節(jié)點為空的情況
  if (pred == null)
      first = newNode;
  //處理前驅節(jié)點非空的情況
  else
      pred.next = newNode;
  // 增加鏈表的大小
  size++;
  //修改計數(shù)器
  modCount++;
}

源碼詳解：

final Node<E> pred = succ.prev;

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

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

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

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

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

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

modCount++;

modCount是用于迭代器的修改計數(shù)器，用于在迭代時檢測是否有其他線程修改了集合。每次對鏈表結構進行修改時，都會增加modCount的值。modCount是用于迭代器的修改計數(shù)器，用于在迭代時檢測是否有其他線程修改了集合。每次對鏈表結構進行修改時，都會增加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) {

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

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

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

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

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

return false;

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

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

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;

  //處理前驅節(jié)點為空的情況
  if (prev == null) {
      first = next;
  //前驅節(jié)點非空則處理前驅的后繼
  } else {
      prev.next = next;
      x.prev = null;
  }
 //處理后繼節(jié)點為空的情況
  if (next == null) {
      last = prev;
 //后繼節(jié)點非空則處理后繼的前驅
  } else {
      next.prev = prev;
      x.next = null;
  }
  //清空目標節(jié)點的數(shù)據(jù)元素
  x.item = null;
  //減小鏈表的大小
  size--;
  //更新修改計數(shù)器
  modCount++;
  return element;
}

源碼詳解：

final E element = x.item;

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

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

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

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

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

x.item = null;

將目標節(jié)點的 item 字段置為 null，幫助垃圾回收系統(tǒng)回收節(jié)點的數(shù)據(jù)元素。

size--; modCount++;

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

最后，返回被刪除節(jié)點的數(shù)據(jù)元素。

LinkedList的優(yōu)勢和劣勢

優(yōu)勢

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

劣勢

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

使用場景

LinkedList適用于以下場景：

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

總結

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

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

深度解析LinkedList

底層數(shù)據(jù)結構

操作方法

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

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

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

LinkedList的優(yōu)勢和劣勢

優(yōu)勢

劣勢

使用場景

總結

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

Android 教程含代碼

HTML5教程含代碼

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

zabbix_senderzabbix發(fā)送器工具的命令 – Linux

常用數(shù)據(jù)庫連接池

優(yōu)雅校驗：Guava Preconditions使用指南