• Java集合之ArrayList与LinkedList

    前言

    对于Java程序员，可以说对于 ArrayList 和 LinkedList 可谓是十分熟悉了

    对于ArrayList和LinkedList，他们都是List接口的一个实现类，并且我们知道他们的实现方式各不相同，例如ArrayList底层实现是一个数组，而LinkedList底层实现是链表，对于数组来说，插入慢但是查询快，而对于链表来说查询慢，插入快

    今天我们就来分析分析他们的源码

    ArrayList

    我们先看一看ArrayList的类图。他继承于AbstractList，而这个类是List类的的骨架，可以说这个类是List类的基石

    成员属性

    1. class="prettyprint hljs gradle" deep="5" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">/**
    2. 序列化ID
    3. **/
    4. private static final long serialVersionUID = 8683452581122892189L;
    5. /**
    6. 默认容量
    7. **/
    8. private static final int DEFAULT_CAPACITY = 10;
    9. /**
    10. 如果传入的容量为0，那么将使用这个空元素数组
    11. **/
    12. private static final Object[] EMPTY_ELEMENTDATA = {};
    13. /**
    14. 默认空元素数组，长度为0，传入元素时会初始化为默认元素大小
    15. **/
    16. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    17. /**
    18. 真正存储数据的数组
    19. **/
    20. transient Object[] elementData;
    21. /**
    22. 列表中元素的个数
    23. **/
    24. private int size;

    这里需要主要关注的成员属性为 size 和 elementData ，一个是元素个数，一个是真正存储数据的数组

    构造函数

    1. class="prettyprint hljs cpp" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">/**
    2. 指定数组长度构造
    3. **/
    4. public ArrayList(int initialCapacity) {
    5.     if (initialCapacity > 0) {
    6.         this.elementData = new Object[initialCapacity];
    7.     } else if (initialCapacity == 0) {
    8.         this.elementData = EMPTY_ELEMENTDATA;
    9.     } else {
    10.         throw new IllegalArgumentException("Illegal Capacity: "+
    11.                                            initialCapacity);
    12.     }
    13. }
    14. /**
    15. 空参构造
    16. **/
    17. public ArrayList() {
    18.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    19. }
    20. /**
    21. 传入一个集合，将该集合的元素初始化到ArrayList种
    22. **/
    23. public ArrayList(Collection c) {
    24.     elementData = c.toArray();
    25.     if ((size = elementData.length) != 0) {
    26.         // c.toArray might (incorrectly) not return Object[] (see 6260652)
    27.         if (elementData.getClass() != Object[].class)
    28.             elementData = Arrays.copyOf(elementData, size, Object[].class);
    29.     } else {
    30.         // replace with empty array.
    31.         this.elementData = EMPTY_ELEMENTDATA;
    32.     }
    33. }

    扩容机制

    我们知道ArrayList是一个动态数组，但是他的底层实现是一个数组，那他是怎样保证动态的呢？

    ArrayList每次添加元素之前，都会检查添加元素后的元素个数是否超过数组长度，如果超出，那么就会进行扩容，而数组扩容通过一个公开的方法实现，我们也可以手动进行扩容

    1. class="prettyprint hljs cpp" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public void ensureCapacity(int minCapacity) {
    2.         //判断数组是否等于默认空数组，不等于则给minExpand赋值为10
    3.         int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    4.             ? 0 : DEFAULT_CAPACITY;
    5.         //判断参数是否大于minExpand大于的时候才会去扩容
    6.         if (minCapacity > minExpand) {           
    7.             ensureExplicitCapacity(minCapacity);
    8.         }
    9.     }
    10.     private void ensureExplicitCapacity(int minCapacity) {
    11.         modCount++;//记录数组修改次数 + 1
    12.         if (minCapacity - elementData.length > 0)
    13.             grow(minCapacity);
    14.     }
    15.     //真正扩容的方法
    16.     private void grow(int minCapacity) {
    17.         //获取原来的容量
    18.         int oldCapacity = elementData.length;
    19.         //计算新容量，新容量大小 = 旧容量大小的1.5倍
    20.         int newCapacity = oldCapacity + (oldCapacity >> 1);
    21.         //如果需要的容量比新容量还小就用需要的容量
    22.         if (newCapacity - minCapacity < 0)
    23.             newCapacity = minCapacity;
    24.         //如果新容量大于最大容量就用最大的容量
    25.         if (newCapacity - MAX_ARRAY_SIZE > 0)
    26.             newCapacity = hugeCapacity(minCapacity);
    27.         //数据拷贝
    28.         elementData = Arrays.copyOf(elementData, newCapacity);
    29.     }

    我们可以发现每次扩容，ArrayList都会扩容1.5倍，通过位运算完成计算扩容大小的，我们知道，扩容之后进行数据迁移这个操作是很费时间的，比如我们有10w条数据，这样的话，进行数据迁移的时候，我们会耗费很长时间，所以我们建议再初始化的时候就定义一个容量，这样可以让ArrayList的效率提高很多

    add方法

    1. class="prettyprint hljs gradle" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">//添加元素到尾部
    2. public boolean add(E e) {
    3.     //检查是否需要扩容
    4.     ensureCapacityInternal(size + 1); 
    5.     //将元素添加到数组末尾，并把size++
    6.     elementData[size++] = e;
    7.     return true;
    8. }
    9. //添加元素到指定索引
    10. public void add(int index, E element) {
    11.     //检查index是否越界
    12.     rangeCheckForAdd(index);
    13.     //检查是否需要扩容
    14.     ensureCapacityInternal(size + 1);
    15.     //将index以及之后的元素向后挪动一位
    16.     //这样index就能添加元素了
    17.     System.arraycopy(elementData, index, elementData, index + 1,
    18.                      size - index);
    19.     //添加元素到index的位置
    20.     elementData[index] = element;
    21.     size++;
    22. }
    23. //将集合c的元素添加到list中
    24. public boolean addAll(Collectionextends E> c) {
    25.     //把c转换为数组
    26.     Object[] a = c.toArray();
    27.     //拿到c的长度
    28.     int numNew = a.length;
    29.     //检查是否需要扩容
    30.     ensureCapacityInternal(size + numNew);  // Increments modCount
    31.     //将a数组拷贝到原来数组的末尾
    32.     System.arraycopy(a, 0, elementData, size, numNew);
    33.     size += numNew;
    34.     return numNew != 0;
    35. }
    36. //将集合c的元素从index位置开始添加到list中
    37. public boolean addAll(int index, Collectionextends E> c) {
    38.     //检查index是否越界
    39.     rangeCheckForAdd(index);
    40.     //将c转换为数组
    41.     Object[] a = c.toArray();
    42.     //获取数组a的长度
    43.     int numNew = a.length;
    44.     //检查是否需要扩容
    45.     ensureCapacityInternal(size + numNew);  // Increments modCount
    46.     //计算需要移动的长度
    47.     int numMoved = size - index;
    48.     if (numMoved > 0)
    49.         //向后移动
    50.         System.arraycopy(elementData, index, elementData, index + numNew,
    51.                          numMoved);
    52.     将数组a拷贝到原数组中
    53.     System.arraycopy(a, 0, elementData, index, numNew);
    54.     size += numNew;
    55.     return numNew != 0;
    56. }

    get方法

    1. "prettyprint hljs kotlin" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public E get(int index) {
    2.     //检查index是否越界
    3.     rangeCheck(index);
    4.     //返回对应数组中指定索引的元素
    5.     return elementData(index);
    6. }

    remove方法

    1. class="prettyprint hljs gradle" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">//删除指定索引的元素
    2. public E remove(int index) {
    3.     //判断index是否越界
    4.     rangeCheck(index);
    5.     //将数组修改次数+1
    6.     modCount++;
    7.     //拿到对应索引的元素
    8.     E oldValue = elementData(index);
    9.     计算移动位置
    10.     int numMoved = size - index - 1;
    11.     if (numMoved > 0)
    12.         //移动数组
    13.         System.arraycopy(elementData, index+1, elementData, index,
    14.                          numMoved);
    15.     //size-1，并把尾部元素置为null，这里把尾部置为null主要是为了让GC起作用
    16.     elementData[--size] = null;
    17.  
    18.     return oldValue;
    19. }
    20. //删除第一个满足o.equals(elementData[index]的元素
    21. public boolean remove(Object o) {
    22.     if (o == null) {
    23.         //如果o为null使用==进行判断
    24.         //从索引为0的元素开始寻找
    25.         for (int index = 0; index < size; index++)
    26.             if (elementData[index] == null) {
    27.                 fastRemove(index);
    28.                 return true;
    29.             }
    30.     } else {
    31.         //否则使用equals判断
    32.         //从索引为0的元素开始寻找
    33.         for (int index = 0; index < size; index++)
    34.             if (o.equals(elementData[index])) {
    35.                 fastRemove(index);
    36.                 return true;
    37.             }
    38.     }
    39.     return false;
    40. }

    小结

    <pre class="hljs less" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 0.75em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Collections.synchronizedList(list)

    LinkedList

    对于LinkedList，它同样继承与AbstractList，在前面已经说过了，AbstractList是List的骨架，我们还可以看到它实现了Deque，所以LinkedList既可以看做一个链表也可以看做是一个队列，同样也可以看做一个栈，所以LinkedList比较全能

    Node类

    我们知道LinkedList是一个双向链表，那么肯定有一个个的Node，所以我们先来看一看Node类

    1. <pre class="prettyprint hljs gradle" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">private static class Node<E> {
    2.     E item;
    3.     Node<E> next;
    4.     Node<E> prev;
    5.  
    6.     Node(Node<E> prev, E element, Node<E> next) {
    7.         this.item = element;
    8.         this.next = next;
    9.         this.prev = prev;
    10.     }
    11. }

    这部分代码比较简单就简单说一下，Node节点有三个成员属性，分别是value，前驱指针，后继指针，以及一个全参构造方法

    成员属性

    1. class="prettyprint hljs gradle" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">/**
    2. 元素个数
    3.  */
    4. transient int size = 0;
    5. /**
    6. 指向链表头结点
    7.  */
    8. transient Node first;
    9. /**
    10. 指向链表尾节点
    11.  */
    12. transient Node last;
    13. /**
    14. 序列化ID
    15.  */
    16. private static final long serialVersionUID = 876323262645176354L;

    构造函数

    1. class="prettyprint hljs cpp" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">//空参构造，没什么好说的
    2. public LinkedList() {
    3. }
    4. //将集合c的元素添加到链表中
    5. public LinkedList(Collection c) {
    6.     //调用空参构造
    7.     this();
    8.     //调用addAll()这个方法在下面讲述
    9.     addAll(c);
    10. }

    添加

    1. class="prettyprint hljs gradle" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public boolean add(E e) {
    2.     linkLast(e);//添加元素到末尾
    3.     return true;
    4. }
    5. //将元素添加到指定index位置
    6. public void add(int index, E element) {
    7.     //检查索引是否大于size或者小于0
    8.     checkPositionIndex(index);
    9.     //如果索引位置和size相等添加到末尾
    10.     if (index == size)
    11.         linkLast(element);
    12.     else
    13.         //添加到指定位置
    14.         linkBefore(element, node(index));
    15. }
    16. public void addFirst(E e) {
    17.     linkFirst(e);//添加元素到头部
    18. }
    19. public void addLast(E e) {
    20.     linkLast(e);//添加元素到末尾
    21. }
    22. //添加到头部
    23. private void linkFirst(E e) {
    24.      //拿到头指针
    25.     final Node f = first;
    26.     //new一个Node节点，值为e，next为头指针，pre为null
    27.     final Node newNode = new Node<>(null, e, f);
    28.     //将头指针替换为新的
    29.     first = newNode;
    30.     //将f的pre修改为现在的头指针
    31.     if (f == null)
    32.         last = newNode;
    33.     else
    34.         f.prev = newNode;
    35.     size++;
    36.     modCount++;
    37. }
    38. //添加到末尾
    39. void linkLast(E e) {
    40.     //拿到尾指针
    41.     final Node l = last;
    42.     //new一个Node节点，值为e，next为null，pre为尾指针
    43.     final Node newNode = new Node<>(l, e, null);
    44.     //替换尾指针
    45.     last = newNode;
    46.     //将l的next修改为现在的尾指针
    47.     if (l == null)
    48.         first = newNode;
    49.     else
    50.         l.next = newNode;
    51.     size++;
    52.     modCount++;
    53. }
    54. //将集合c的元素添加到list中
    55. public boolean addAll(Collectionextends E> c) {
    56.     //从尾部开始添加
    57.     return addAll(size, c);
    58. }
    59. //真正的addAll方法
    60. public boolean addAll(int index, Collectionextends E> c) {
    61.     //检查index正确
    62.     checkPositionIndex(index);
    63.     //先把c转换为数组
    64.     Object[] a = c.toArray();
    65.     //拿到c的长度
    66.     int numNew = a.length;
    67.     if (numNew == 0)
    68.         return false;
    69.     //定义两个指针，一个前驱一个后继
    70.     Node pred, succ;
    71.     if (index == size) {
    72.         succ = null;
    73.         pred = last;
    74.     } else {
    75.         succ = node(index);
    76.         pred = succ.prev;
    77.     }
    78.     //遍历数组a
    79.     for (Object o : a) {
    80.         @SuppressWarnings("unchecked") E e = (E) o;
    81.         //new一个Node节点，值为e，前驱为pred，后继为null
    82.         Node newNode = new Node<>(pred, e, null);
    83.         //pred为null，证明前驱为null，当前节点为链表的头结点
    84.         if (pred == null)
    85.             first = newNode;
    86.         else
    87.             //前驱节点后继指针指向头结点
    88.             pred.next = newNode;
    89.         //前驱节点后移
    90.         pred = newNode;
    91.     }
    92.     //succ为null证明index索引位于链表最后
    93.     if (succ == null) {
    94.         last = pred;
    95.     } else {
    96.         //pred的后继节点为succ
    97.         pred.next = succ;
    98.         //succ的前驱节点为pred
    99.         succ.prev = pred;
    100.     }
    101.  
    102.     size += numNew;
    103.     modCount++;
    104.     return true;
    105. }

    获取

    1. class="prettyprint hljs java" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">//这个方法是Node类的方法，我们可以看到上面的addAll方法也使用了这个方法
    2. //这个方法作用是返回指定索引的非空节点
    3. Node node(int index) {
    4.     //判断该索引位于前半段还是后半段
    5.     if (index < (size >> 1)) {
    6.         Node x = first;
    7.         //前半段：从头部向后搜索
    8.         for (int i = 0; i < index; i++)
    9.             x = x.next;
    10.         return x;
    11.     } else {
    12.         Node x = last;
    13.         //后半段：从尾部向前搜索
    14.         for (int i = size - 1; i > index; i--)
    15.             x = x.prev;
    16.         return x;
    17.     }
    18. }
    19. //获取index位置的元素
    20. public E get(int index) {
    21.     //检查索引是否正常
    22.     checkElementIndex(index);
    23.     return node(index).item;
    24. }
    25. //获取头部元素
    26. public E getFirst() {
    27.     final Node f = first;
    28.     if (f == null)
    29.         throw new NoSuchElementException();
    30.     return f.item;
    31. }
    32. //获取尾部元素
    33. public E getLast() {
    34.     final Node l = last;
    35.     if (l == null)
    36.         throw new NoSuchElementException();
    37.     return l.item;
    38. }

    删除

    1. "prettyprint hljs gradle" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">//删除index位置的元素
    2. public E remove(int index) {
    3.     //检查索引是否大于size或者小于0
    4.     checkElementIndex(index);
    5.     //删除index位置的元素
    6.     return unlink(node(index));
    7. }
    8. //删除头部元素，这个方法是Node类的方法
    9. private E unlinkFirst(Node f) {
    10.     //拿到头节点的值
    11.     final E element = f.item;
    12.     //拿到头结点的next值
    13.     final Node next = f.next;
    14.     //将头结点的值置为null(帮助GC)
    15.     f.item = null;
    16.     //将头结点的next置为null(帮助GC)
    17.     f.next = null;
    18.     //将头结点修改为next
    19.     first = next;
    20.     if (next == null)
    21.         //此时链表没有元素了
    22.         last = null;
    23.     else
    24.         next.prev = null;
    25.     size--;
    26.     modCount++;
    27.     return element;
    28. }
    29. //删除尾部元素，这个方法是Node类的方法
    30. private E unlinkLast(Node l) {
    31.     //拿到尾节点的值
    32.     final E element = l.item;
    33.     //拿到尾节点的前驱
    34.     final Node prev = l.prev;
    35.     //将尾结点的值置为null(帮助GC)
    36.     l.item = null;
    37.     //将尾结点的next置为null(帮助GC)
    38.     l.prev = null;
    39.     //将尾指针修改为prev
    40.     last = prev;
    41.     if (prev == null)
    42.         //此时链表没有元素了
    43.         first = null;
    44.     else
    45.         prev.next = null;
    46.     size--;
    47.     modCount++;
    48.     return element;
    49. }

    小结

    • 虽然说链表的删除的效率为O(1),但是在LinkedList中我们需要先利用node方法查询到指定节点的位置，然后再去删除，所以千万不要误认为LinkedList的remove方法是O(1)
    • LinkedList删除头部和尾部的元素效率为O(1)
  • 相关阅读:
    ROS2 中的轻量级、自动化、受控回放
    量化金融-分类数据的检验
    长链贪心+虚树+类直径合并性+分块建树维护ST表：1008T4
    【深入浅出玩转FPGA9------经验点滴】
    机器学习基础介绍
    工具篇--分布式定时任务springBoot 整合 elasticjob使用（3）
    MyBatis工作原理
    MySQL系列——MySQL8+keepalived双主热备高可用
    Linux 进程切换与命令行参数
    【行为型模式】解释器模式
  • 原文地址：https://blog.csdn.net/weixin_62421895/article/details/126263651