快捷導(dǎo)航

Java容器源碼LinkedList原理解析

更新時(shí)間：2020年11月18日 09:14:54 投稿：yaominghui

這篇文章主要介紹了Java容器源碼LinkedList原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

LinkedList簡(jiǎn)介

LinkedList是一個(gè)使用雙向鏈表結(jié)構(gòu)實(shí)現(xiàn)的容器，與ArrayList一樣，它能動(dòng)態(tài)擴(kuò)充其長(zhǎng)度，LinkedList相較于ArrayList，其任意位置插入速度比ArrayList要快，但是其查詢速度要比ArrayList要慢；LinkedList繼承自AbstractSequentialList，實(shí)現(xiàn)了List、Deque、Cloneable、Serializable接口。

LinkedList UML圖如下：

和ArrayList一樣，LinkedList也不是一個(gè)線程安全的容器。

LinkedList源碼分析

構(gòu)造方法

LinkedList有兩個(gè)構(gòu)造方法：

public LinkedList() {
}

//從已有的一個(gè)容器創(chuàng)建一個(gè)LinkedList對(duì)象
public LinkedList(Collection<? extends E> c) {
  this();
  addAll(c);
}

addAll()方法：

public boolean addAll(Collection<? extends E> c) {
  return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
  //檢查index是否溢出
  checkPositionIndex(index);
  
  Object[] a = c.toArray();
  int numNew = a.length;
  if (numNew == 0)
    return false;
  //獲取第index位置的node元素和node的前一個(gè)元素
  //succ：第index位置的node元素
  //pred：index位置前一個(gè)node元素
  Node<E> pred, succ;
  if (index == size) {
    succ = null;
    pred = last;
  } else {
    succ = node(index);
    pred = succ.prev;
  }

  //遍歷，將元素插入鏈表中
  for (Object o : a) {
    @SuppressWarnings("unchecked") E e = (E) o;
    Node<E> newNode = new Node<>(pred, e, null);
    if (pred == null)
      first = newNode;
    else
      pred.next = newNode;
    pred = newNode;
  }

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

  size += numNew;
  modCount++;
  return true;
}

add方法

LinkedList也有兩個(gè)add方法，如下：

public boolean add(E e) {
  //添加元素到隊(duì)尾
  linkLast(e);
  return true;
}

public void add(int index, E element) {
  //檢查index是否溢出
  checkPositionIndex(index);

  if (index == size)
    //index == size，直接添加到隊(duì)尾
    linkLast(element);
  else
    //index != size，添加元素到index位置
    linkBefore(element, node(index));
}

linkLast方法：

void linkLast(E e) {
  final Node<E> l = last;
  //新建一個(gè)node，將其前一個(gè)元素指針指向原鏈表的最后一個(gè)元素
  final Node<E> newNode = new Node<>(l, e, null);
  //更新尾指針
  last = newNode;
  if (l == null)
    //若原last==null說(shuō)明此時(shí)鏈表就一個(gè)元素
    first = newNode;
  else
    //更新原鏈表尾元素指針
    l.next = newNode;
  size++;
  modCount++;
}

linkBefore方法：

void linkBefore(E e, Node<E> succ) {
  // assert succ != null;
  //獲取指定位node元素的前一個(gè)元素pred
  final Node<E> pred = succ.prev;
  //新建一個(gè)node，將其前指針指向pred元素
  final Node<E> newNode = new Node<>(pred, e, succ);
  //將指定位置的node元素的前指針指向新元素，完成插入
  succ.prev = newNode;
  if (pred == null)
    first = newNode;
  else
    pred.next = newNode;
  size++;
  modCount++;
}

獲取指定位置node指針?lè)椒╪ode：

Node<E> node(int index) {
  // assert isElementIndex(index);
  //index > size/2時(shí)，說(shuō)明在鏈表前半段，從前往后搜索
  if (index < (size >> 1)) {
    Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  //index < size/2時(shí)，從后往前搜索
  } else {
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

get方法也比較簡(jiǎn)單，首先檢測(cè)index是否溢出，然后直接找到index位置的元素，并返回其item。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: