登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›3.Java SDK源码分析系列笔记-LinkedList

3.Java SDK源码分析系列笔记-LinkedList

戟铵腴 2025-6-28 18:35:41
目录

  • 1. 是什么
  • 2. 如何使用
  • 3. 原理分析

    • 3.1. uml
    • 3.2. 构造方法

      • 3.2.1. 队列的节点Node

    • 3.3. add方法

      • 3.3.1. 插入到链表尾部
      • 3.3.2. 构造新节点【prev指向尾节点，next为null】
      • 3.3.3. 更新尾节点
      • 3.3.4. 更新size

    • 3.4. addLast方法
    • 3.5. addFirst方法

      • 3.5.1. 头部插入节点
      • 3.5.2. 构造新节点【prev指向null，next指向头节点】
      • 3.5.3. 更新头节点
      • 3.5.4. 更新size

    • 3.6. remove方法【根据下标删除】

      • 3.6.1. 遍历找到这个位置的元素
      • 3.6.2. 更新该节点前后节点的指针

    • 3.7. remove方法【按照元素删除】

      • 3.7.1. 遍历找到这个元素
      • 3.7.2. 更新该节点前后节点的指针

    • 3.8. remove方法【无参】

      • 3.8.1. 删除头部节点
      • 3.8.2. 把原来头节点的next节点更新为头节点

    • 3.9. removeLast方法

      • 3.9.1. 把原来尾节点的prev节点更新为尾节点



1. 是什么

底层由双向链表实现的顺序表
有序、可以重复
2. 如何使用
  1. public class LinkedListTest
  2. {
  3.     public static void main(String[] args)
  4.     {
  5.         LinkedList<String> list = new LinkedList<>();
  6.         list.add("1");
  7.         list.add("2");
  8.         list.addFirst("3");
  9.         list.addLast("4");
  10.         System.out.println(list);
  11.         list.remove(0);
  12.         list.remove("2");
  13.         list.remove();
  14.         list.removeFirst();
  15.         list.removeLast();
  18.     }
  19. }
复制代码
3. 原理分析

3.1. uml

1.png

可以看出LinkedList是个List、双端队列、可序列化、可克隆
3.2. 构造方法

由头节点、尾节点、长度构成
  1. public class LinkedList<E>
  2.     extends AbstractSequentialList<E>//提供了List的骨架实现
  3.     implements List<E>/*List接口*/, Deque<E>/*双端队列*/, Cloneable, java.io.Serializable
  4. {
  6.     //属性
  7.     transient int size = 0;//长度
  8.     transient Node<E> first;//头节点
  9.     transient Node<E> last;//尾节点
  11.     //构造方法
  12.     public LinkedList() {
  13.     }
  14. }
复制代码
3.2.1. 队列的节点Node
  1. private static class Node<E> {
  2.     E item;//数据
  3.     Node<E> next;//后指针
  4.     Node<E> prev;//前指针
  6.     Node(Node<E> prev, E element, Node<E> next) {
  7.         this.item = element;
  8.         this.next = next;
  9.         this.prev = prev;
  10.     }
  11. }
复制代码
结构如下图：
2.png

3.3. add方法


  • O（1）
  1. public boolean add(E e) {
  2.     //调用linkLast方法
  3.     linkLast(e);
  4.     return true;
  5. }
复制代码
3.3.1. 插入到链表尾部


  • linkLast
  1. void linkLast(E e) {
  2.         //保存尾节点
  3.     final Node<E> l = last;
  4.     //构造新的节点，prev指向last节点
  5.     final Node<E> newNode = new Node<>(l, e, null);
  6.     //把尾节点更新为新的节点
  7.     last = newNode;
  8.     //如果原来的尾节点为空，那么是第一个节点。此时更新first为新节点
  9.     if (l == null)
  10.         first = newNode;
  11.     else
  12.         //否则更新尾节点的next为新的节点
  13.         l.next = newNode;
  14.     size++;
  15.     modCount++;
  16. }
复制代码
3.3.2. 构造新节点【prev指向尾节点，next为null】
  1. //保存尾节点
  2. final Node<E> l = last;
  3. //构造新的节点，prev指向last节点
  4. final Node<E> newNode = new Node<>(l, e, null);
复制代码
3.3.3. 更新尾节点
  1. //如果原来的尾节点为空，那么是第一个节点。此时更新first为新节点
  2. if (l == null)
  3.     first = newNode;
  4. else
  5. //否则更新尾节点的next为新的节点
  6.     l.next = newNode;
复制代码
3.3.4. 更新size
  1. size++;
复制代码
3.4. addLast方法


  • O（1）
  1. public void addLast(E e) {
  2.         //调用linkLast
  3.     linkLast(e);
  4. }
复制代码

  • linkLast
    参考add方法
3.5. addFirst方法


  • O（1）
  1. public void addFirst(E e) {
  2.         //简单的调用linkFirst
  3.     linkFirst(e);
  4. }
复制代码
3.5.1. 头部插入节点


  • linkFirst
  1. private void linkFirst(E e) {
  2.         //先保存原头节点
  3.     final Node<E> f = first;
  4.     //新建节点，next指向原头节点
  5.     final Node<E> newNode = new Node<>(null, e, f);
  6.     //更新头节点为新的节点
  7.     first = newNode;
  8.     //如果原头节点为空，那么是第一个元素，更新last节点为新的节点
  9.     if (f == null)
  10.         last = newNode;
  11.     else
  12.     //否则更新原头节点的prev为新的节点
  13.         f.prev = newNode;
  14.         
  15.     size++;
  16.     modCount++;
  17. }
复制代码
3.5.2. 构造新节点【prev指向null，next指向头节点】
  1. //先保存原头节点
  2. final Node<E> f = first;
  3. //新建节点，next指向原头节点
  4. final Node<E> newNode = new Node<>(null, e, f);
复制代码
3.5.3. 更新头节点
  1. //如果原头节点为空，那么是第一个元素，更新last节点为新的节点
  2. if (f == null)
  3.     last = newNode;
  4. else
  5. //否则更新原头节点的prev为新的节点
  6.     f.prev = newNode;
复制代码
3.5.4. 更新size
  1. size++;
复制代码
3.6. remove方法【根据下标删除】


  • O（N）
  • 修改这个元素的前后元素的next和prev指针
  1. public E remove(int index) {
  2.                 //检查是否越界
  3.         checkElementIndex(index);
  4.             //根据下标找到相应的节点，并把这个节点删除
  5.         return unlink(node(index));
  6.     }
  7.    
复制代码
3.6.1. 遍历找到这个位置的元素


  • node
  1. Node<E> node(int index) {
  2.     // assert isElementIndex(index);
  4.         //索引在链表左半部分
  5.     if (index < (size >> 1)) {
  6.             //从头节点往右找
  7.         Node<E> x = first;
  8.         for (int i = 0; i < index; i++)
  9.             x = x.next;
  10.         return x;
  11.     //索引在链表右半部分
  12.     } else {
  13.             //从尾节点往左找
  14.         Node<E> x = last;
  15.         for (int i = size - 1; i > index; i--)
  16.             x = x.prev;
  17.         return x;
  18.     }
  19. }
复制代码
3.6.2. 更新该节点前后节点的指针
  1. E unlink(Node<E> x) {
  2.     // assert x != null;
  3.     //首先保存当前节点的prev，next，和item值
  4.     final E element = x.item;
  5.     final Node<E> next = x.next;
  6.     final Node<E> prev = x.prev;
  8.         //更新prev
  9.     if (prev == null) {
  10.             //前一个节点为空（说明当前节点是头节点），那么把first指向当前节点的下一个节点即可
  11.         first = next;
  12.     } else {
  13.             //前一个节点的next指向当前节点的下一个节点
  14.         prev.next = next;
  15.         //help gc
  16.         x.prev = null;
  17.     }
  19.         //更新next
  20.     if (next == null) {
  21.             //后一个节点为空（说明当前节点是尾节点），那么把last指向当前节点的上一个节点即可
  22.         last = prev;
  23.     } else {
  24.             //后一个节点的prev指向当前节点的上一个节点
  25.         next.prev = prev;
  26.         //help gc
  27.         x.next = null;
  28.     }
  30.         //help gc
  31.     x.item = null;
  32.     size--;//更新size
  33.     modCount++;
  34.     return element;
  35. }
复制代码
3.7. remove方法【按照元素删除】


  • O（N）
  1. public boolean remove(Object o) {
  2.         //==null
  3.     if (o == null) {
  4.             //遍历找到node
  5.         for (Node<E> x = first; x != null; x = x.next) {
  6.             if (x.item == null) {
  7.                 unlink(x);
  8.                 return true;
  9.             }
  10.         }
  11.     //equals
  12.     } else {
  13.             //遍历找到node
  14.         for (Node<E> x = first; x != null; x = x.next) {
  15.             if (o.equals(x.item)) {
  16.                 unlink(x);
  17.                 return true;
  18.             }
  19.         }
  20.     }
  21.     return false;
  22. }
复制代码
3.7.1. 遍历找到这个元素
  1. for (Node<E> x = first; x != null; x = x.next)
  2. {
  3.     //...
  4. }
复制代码
3.7.2. 更新该节点前后节点的指针

3.8. remove方法【无参】


  • O（1）
  1. public E remove() {
  2.         //简单调用removeFirst
  3.     return removeFirst();
  4. }
复制代码
3.8.1. 删除头部节点


  • removeFirst
  1. public E removeFirst() {
  2.         //头节点
  3.     final Node<E> f = first;
  4.     if (f == null)
  5.             //为null直接抛出异常
  6.         throw new NoSuchElementException();
  7.     //调用unlinkFirst从链表删除头节点
  8.     return unlinkFirst(f);
  9. }
复制代码
3.8.2. 把原来头节点的next节点更新为头节点


  • unlinkFirst
  1. private E unlinkFirst(Node<E> f) {
  2.     // assert f == first && f != null;
  3.     //保存item，next
  4.     final E element = f.item;
  5.     final Node<E> next = f.next;
  6.        
  7.         // help GC   
  8.     f.item = null;
  9.     f.next = null;
  10.    
  11.     //first直接指向头节点的next
  12.     first = next;
  13.     //如果头节点的next为空，说明链表中只有一个节点
  14.     if (next == null)
  15.             //更新last指向null
  16.         last = null;
  17.     else
  18.             //否则更新头节点的next节点的prev指针
  19.         next.prev = null;
  20.     size--;
  21.     modCount++;
  22.     return element;
  23. }
复制代码
3.9. removeLast方法


  • O（1）
  1. public E removeLast() {
  2.         final Node<E> l = last;
  3.         if (l == null)
  4.             throw new NoSuchElementException();
  5.         return unlinkLast(l);
  6.     }
复制代码
3.9.1. 把原来尾节点的prev节点更新为尾节点


  • unlinkLast
  1. private E unlinkLast(Node<E> l) {
  2.     // assert l == last && l != null;
  3.     //保存尾节点的item值和prev
  4.     final E element = l.item;
  5.     final Node<E> prev = l.prev;
  6.     // help GC
  7.     l.item = null;
  8.     l.prev = null;
  9.     //更新last为原尾节点的prev
  10.     last = prev;
  11.     //只有一个元素
  12.     if (prev == null)
  13.         first = null;
  14.     else
  15.         prev.next = null;
  16.     size--;
  17.     modCount++;
  18.     return element;
  19. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
戟铵腴
2025-6-28 18:35:41

0

粉丝关注

13

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫