jdk源码阅读笔记-LinkedList

一、LinkedList概述LinkedList的底层数据结构为双向链表结构,与ArrayList相同的是LinkedList也可以存储相同或null的元素。相对于ArrayList来说,LinkedList的插入与删除的速度更快,时间复杂度为O(1),查找的速度就相对比较慢了,因为每次遍历的时候都必须从链表的头部或者链表的尾部开始遍历,时间复杂度为O(n/2)。为了实现快速插入或删除数据,Lin...

jdk源码阅读笔记-LinkedList

  一、LinkedList概述

  LinkedList的底层数据结构为双向链表结构,与ArrayList相同的是LinkedList也可以存储相同或null的元素。相对于ArrayList来说,LinkedList的插入与删除的速度更快,时间复杂度为O(1),查找的速度就相对比较慢了,因为每次遍历的时候都必须从链表的头部或者链表的尾部开始遍历,时间复杂度为O(n/2)。为了实现快速插入或删除数据,LinkedList在每个节点都维护了一个前继节点和一个后续节点,这是一种典型的以时间换空间的思想。LinkedList同时也可以实现栈与队列的功能。

  二、LinkedList的结构图

  在LinkedList中每个节点有会有两个指针,一个指向前一个节点,另一个指向下一个节点。链表的头部的前指针为null,尾部的后指针也为null,因此也可以说明LinkedList(基于jdk1.8)是非循环双向链表结构。源码如下:

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属性

  1、size: 链表的长度

  2、first:链表的第一个节点

  3、last:链表的最后一个节点

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.  */

  四、添加节点

  1、链表头部添加新节点

/**  * Links e as first element.  *  链接头部  */ private void linkFirst(E e) {  //链表的第一个节点  final Node<E> f = first;  //创建节点  final Node<E> newNode = new Node<>(null, e, f);  //将新创建的节点放到链条头部  first = newNode;  //当链表为null时,链表头部和尾部都指向新节点  if (f == null)last = newNode;  elsef.prev = newNode;//把原本第一个节点的前一个节点指向新的节点  size  ;//链表长度加1  modCount  ;//链表修改次数加1 }

  当链表为空的时候比较简单,直接将链表的头部和尾部都指向新节点即可,下面我来说一下在非空的情况下头部插入新节点:

  2、往链表尾部插入新节点

/**  * Links e as last element.  */ void linkLast(E e) {  //原来的最后一个节点  final Node<E> l = last;  //创建新的节点,next为null  final Node<E> newNode = new Node<>(l, e, null);  //将新节点指向最后一个节点  last = newNode;  if (l == null)first = newNode;//链表为空时第一个节点也指向新节点  elsel.next = newNode;//将原最后一个节点的next指针指向新节点  size  ;  modCount  ; }

  具体流程:

  3、在指定节点之前插入新节点

/**  * Inserts element e before non-null Node succ.  *  指定节点之前插入新节点  */ 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;//如果指定节点为第一个节点,那么将节点设置为头部  elsepred.next = newNode;//否则将前一个的下一个节点指向新节点  size  ;  modCount  ; }

流程:

  

  五、删除节点

  1、删除第一个节点

/**  * Unlinks non-null first node f.  * 删除第一个节点  */ private E unlinkFirst(Node<E> f) {  // assert f == first && f != null;  //第一个节点  final E element = f.item;  //第一个节点的前一个节点  final Node<E> next = f.next;  //将前一个节点和原第一个节点掷为空,方便回收  f.item = null;  f.next = null; // help GC  //把原第一个节点设置成第一个节点  first = next;  //链表只有一个节点的情况  if (next == null)last = null;  elsenext.prev = null;//将原节点的下一个的前一个节点设置为null,因为该节点已经设置为第一个节点,而第一个节点的前一个节点为null  size--;  modCount  ;  return element; }

  流程:

  2、删除链表最后一个节点

/**  * Unlinks non-null last node l.  * 删除最后一个节点  */ private E unlinkLast(Node<E> l) {  // assert l == last && l != null;  //最后一个节点  final E element = l.item;  //最后一个节点的前一个节点  final Node<E> prev = l.prev;  l.item = null;  l.prev = null; // help GC  last = prev;  //只有一个节点的情况  if (prev == null)first = null;  elseprev.next = null;//将前一个节点的下一个节点掷为null  size--;  modCount  ;  return element; }

  流程:

源文地址:https://www.guoxiongfei.cn/cntech/3755.html