江苏龙网

  1. 首页 > 人文 > >

关于LinkedList的详细阐述

第一章 LinkedList介绍1.1 引导语LinkedList 集合底层是一个双向链表结构 ， 具有增删快 ， 查询慢的忒点,内部包含大量操作首尾元素的方法 。 适用于集合元素先入先出和先入后出的场景 ， 在队列源码中被频繁使用 。
1.2 整体架构LinkedList 底层数据结构是一个双向链表 ， 整体结构如下图所示：
关于LinkedList的详细阐述文章插图
上图代表了一个双向链表结构 ， 可以通过前面的节点找到后面的节点,也可以通过后面的节点找到前面的节点
相关概念:

  • Node: 代表链中的每个节 ， Node 的 prev 属性 ， 代表前一个节点的地址 ， Node 的next 属性 ， 代表后一个节点的地址；
  • first :代表双向链表的头节点 ， 它的前一个节点是 null 。
  • last: 代表双向链表的尾节点 ， 它的后一个节点是 null；
  • 如果链表中没有任何数据时 ， 头节点first 和 尾节点last 是同一个节点 ， 前后指向都是 null；
  • 因为LinkedList集合是个双向链表 ， 所以机器只要有足够强大的内存 ， 对于LinkedList集合而言是没有大小限制的 。
链表中的元素被称为Node ，Node被定义成私有静态内部类,内容如下 ：
private static class Node {E item;// 节点中存储的数据Node next; // 下一个节点的地址Node prev; // 前一个节点的地址// 构造方法初始化参数顺序分别是：前一个节点的地址值、当前节点中存储的数据、后一个节点的地址值Node(Node prev, E element, Node next) {this.item = element;this.next = next;this.prev = prev;}}?第二章 LinkedList 源码解析2.1 添加（新增）节点如果想在LinkedList集合中添加节点 ， 我们把新加入的节点添加到链表头部 ， 也可以把新加入的节点添加添加到链表尾部 ， add 方法默认是从尾部开始添加 ， addFirst 方法是从头部开始添加 ， 下面分别来看下两种不同的添加方式：
从尾部添加（add）
// 从尾部开始添加节点void linkLast(E e) {// 把尾节点数据暂存final Node l = last;// 新建新的节点 ， 初始化入参含义：// l 是新节点的前一个节点 ， 当前值是尾节点值// e 表示当前新增节点 ， 当前新增节点后一个节点是 nullfinal Node newNode = new Node<>(l, e, null);// 新建节点添加到尾部last = newNode;//如果链表为空（l 是尾节点 ， 尾节点为空 ， 链表即空） ， 头部和尾部是同一个节点 ， 都是新建的节点if (l == null)first = newNode;//否则把前尾节点的下一个节点 ， 指向当前尾节点 。elsel.next = newNode;size++;//集合元素数量增加1modCount++;//实际修改次数增加1}从源码上来看 ， 尾部添加节点比较简单.
从头部添加（addFirst）
// 从头部添加private void linkFirst(E e) {// 头节点赋值给临时变量final Node f = first;// 新建节点 ， 前一个节点指向null ， e 是新建节点 ， f 是新建节点的下一个节点 ， 目前值是头节点的值final Node newNode = new Node<>(null, e, f);// 新建节点成为头节点first = newNode;// 头节点为空 ， 就是链表为空 ， 头尾节点是一个节点if (f == null)last = newNode;//上一个头节点的前一个节点指向当前节点elsef.prev = newNode;size++;modCount++;}头部添加节点和尾部添加节点非常类似 ， 只是前者是移动头节点的 prev 指向 ， 后者是移动尾节点的 next 指向 。
2.2 删除节点节点删除的方式和添加类似 ， 我们可以选择从头部删除 ， 也可以选择从尾部删除 ， 删除操作会把节点的值 ， 前后指向节点都置为 null ， 帮助 GC 进行回收 。
从头部删除
//从头删除节点 f 是链表头节点private E unlinkFirst(Node


推荐阅读


上一篇：关于List集合，这份总结很全面

下一篇：微信设置“小辫子昵称”，最近火了