LinkedList 源码阅读记录

简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/81389523 LinkedListLinkedList是基于双向循环链表(从源码中可以很容易看出)实现的,除了可以当做链表来操作外,它还可以当做栈、队列和双端队列来使用。
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/81389523

大致 --- 图侵删

LinkedList

LinkedList是基于双向循环链表(从源码中可以很容易看出)实现的,除了可以当做链表来操作外,它还可以当做栈、队列和双端队列来使用。

  • LinkedList同样是非线程安全的,只在单线程下适合使用。

  • LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆。


先看LinkedList数据结构

JDK版本不同,数据结构也不同

/** 再看下这个节点吧
 *  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;
        }
    }

根据JDK版本的不同 ,构造方法也不同

/**
 * JDK1.8
 * Deque接口,Deque接口表示是一个双端队列,那么也意味着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);
    }



/**
 * 构造方法在1.6版本也不太一样
 *  默认构造函数:创建一个空的链表  
 */

public LinkedList() {  
    header.next = header.previous = header;  
}  
/**
 *  链表的表头,表头不包含任何数据。Entry是个链表类数据结构。 相当于1.8 Node
 */
private transient Entry<E> header = new Entry<E>(null, null, null); 
/**
 * 包含“集合”的构造函数:创建一个包含“集合”的LinkedList 
 */ 
public LinkedList(Collection<? extends E> c) {  
    this();  
    addAll(c);  
}  

/** 
 * 因为数据结构不大一样 所以add方式也不一样 
 * remove方式 实现方式有一点不一样
 */
 /**
  * JDK1.8 节点Node
  * Links e as last element.
  */
 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++;
 }
 /**
  * Unlinks non-null node 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;
  }

 /**
  * JDK1.6 节点Entry
  * 将节点(节点数据是e)添加到entry节点之前。  
  */
  private Entry<E> addBefore(E e, Entry<E> entry) {  
      // 新建节点newEntry,将newEntry插入到节点e之前;并且设置newEntry的数据是e  
      Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  
      newEntry.previous.next = newEntry;  
      newEntry.next.previous = newEntry;  
      // 修改LinkedList大小  
      size++;  
      // 修改LinkedList的修改统计数:用来实现fail-fast机制。  
      modCount++;  
      return newEntry;  
  }
  /**
   * 将节点从链表中删除    
   */   
 private E remove(Entry<E> e) {  
      if (e == header)  
          throw new NoSuchElementException();  

      E result = e.element;  
      e.previous.next = e.next;  
      e.next.previous = e.previous;  
      e.next = e.previous = null;  
      e.element = null;  
      size--;  
      modCount++;  
      return result;  
  }

Java 集合中常见 checkForComodification()方法的作用? modCount和expectedModCount作用?


Node的查找加速

/**
 * 源码中先将index与长度size的一半比较,if index < (size >> 1),就只从位置0往后遍历到位置index处,
 * 而如果index > (size >> 1),就只从位置size往前遍历到位置index处。 
 * 这样可以减少一部分不必要的遍历,从而提高一定的效率(实际上效率还是很低)。 
 * JDK1.8这里用的是位运算 , 而JDK1.6 用的是判断index<size/2
 * Returns the (non-null) Node at the specified element index.
 */
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;
    }
}

每次看都有新发现,都会更新记录!

目录
相关文章
|
3月前
|
存储 Java 索引
【Java集合类面试二十四】、ArrayList和LinkedList有什么区别?
ArrayList基于动态数组实现,支持快速随机访问;LinkedList基于双向链表实现,插入和删除操作更高效,但占用更多内存。
|
6月前
|
存储 缓存 Java
LinkedList 源码解读
LinkedList 源码解读
36 1
|
6月前
|
调度 uml 索引
|
11月前
|
存储 安全 Java
史上最全的Java容器集合之Vector和LinkedList(源码解读)
史上最全的Java容器集合之Vector和LinkedList(源码解读)
56 0
|
存储
看一看LinkedList的源码?
看一看LinkedList的源码?
63 0
看一看ArrayList的源码?
看一看ArrayList的源码?
106 0
|
存储 安全 Java
史上最全的Java容器集合之Vector和LinkedList(源码解读)(上)
前言 文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820… 种一棵树最好的时间是十年前,其次是现在
122 0
|
安全 Java 索引
史上最全的Java容器集合之Vector和LinkedList(源码解读)(下)
前言 文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820… 种一棵树最好的时间是十年前,其次是现在
137 0
|
前端开发 Java 容器
|
存储
[源码分析]ArrayList和LinkedList如何实现的?我看你还有机会!(二)
[源码分析]ArrayList和LinkedList如何实现的?我看你还有机会!
121 0
[源码分析]ArrayList和LinkedList如何实现的?我看你还有机会!(二)