Java集合篇之深入解析LinkedList

这篇具有很好参考价值的文章主要介绍了Java集合篇之深入解析LinkedList。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在开头

作为ArrayList的同门师兄弟,LinkedList的师门地位逊色不少,除了在做算法题的时候我们会用到它之外,在实际的开发工作中我们极少使用它,就连它的创造者都说:“I wrote it,and I never use it”,想想颇有点好笑,但这并不影响我们去学习它,个人认为它底层的链表逻辑对于我们代码思想的培养还是挺有帮助的。Java集合篇之深入解析LinkedList,Java成长计划,java,开发语言

源码解析

看过build哥文章的同学应该都知道,俺喜欢通过源码去学习和分析对象或代码逻辑,因此,话不多说,直接上源码!

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  //...
}

如上为JDK8中LinkedList的继承实现关系,通过这些关系我们可以大致分析出它所具备的特性:

  1. 实现List接口 表明它是一个列表,支持添加、删除、查找等操作,并且可以通过下标进行访问;
  2. Deque继承自 Queue 接口,具有双端队列的特性,支持从两端插入和删除元素,方便实现栈和队列等数据结构;
  3. Cloneable :表明它具有拷贝能力,可以进行深拷贝或浅拷贝操作;
  4. Serializable : 表明它可以进行序列化操作,也就是可以将对象转换为字节流进行持久化存储或网络传输,非常方便。

LinkedList提供了非常多的方法供我们使用,继续阅读源码可以看到

// 在链表尾部插入元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在链表指定位置插入元素
public void add(int index, E element) {
    // 下标越界检查
    checkPositionIndex(index);

    // 判断 index 是不是链表尾部位置
    if (index == size)
        // 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可
        linkLast(element);
    else
        // 如果不是则调用 linkBefore 方法将其插入指定元素之前
        linkBefore(element, node(index));
}

// 将元素节点插入到链表尾部
void linkLast(E e) {
    // 将最后一个元素赋值(引用传递)给节点 l
    final Node<E> l = last;
    // 创建节点,并指定节点前驱为链表尾节点 last,后继引用为空
    final Node<E> newNode = new Node<>(l, e, null);
    // 将 last 引用指向新节点
    last = newNode;
    // 判断尾节点是否为空
    // 如果 l 是null 意味着这是第一次添加元素
    if (l == null)
        // 如果是第一次添加,将first赋值为新节点,此时链表只有一个元素
        first = newNode;
    else
        // 如果不是第一次添加,将新节点赋值给l(添加前的最后一个元素)的next
        l.next = newNode;
    size++;
    modCount++;
}

// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;断言 succ不为 null
    // 定义一个节点元素保存 succ 的 prev 引用,也就是它的前一节点信息
    final Node<E> pred = succ.prev;
    // 初始化节点,并指明前驱和后继节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将 succ 节点前驱引用 prev 指向新节点
    succ.prev = newNode;
    // 判断尾节点是否为空,为空表示当前链表还没有节点
    if (pred == null)
        first = newNode;
    else
        // succ 节点前驱的后继引用指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}
// 获取链表的第一个元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

// 获取链表的最后一个元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

// 获取链表指定位置的元素
public E get(int index) {
  // 下标越界检查,如果越界就抛异常
  checkElementIndex(index);
  // 返回链表中对应下标的元素
  return node(index).item;
}

Java集合篇之深入解析LinkedList,Java成长计划,java,开发语言
更多的API方法可以参考:LinkedList全量方法

使用LinkedList

在Java中我们写一个小测试代码来用一下LinkedList的增删改查

【代码示例1】

  // 创建LinkedList集合
  LinkedList link = new LinkedList();
  // 1、添加元素
  link.add("happy");
  link.add("new");
  link.offer("year"); // 向集合尾部追加元素
  link.push("javabuild"); // 向集合头部添加元素
  System.out.println(link); // 输出集合中的元素
  // 2、获取元素
  Object object = link.peek(); //获取集合第一个元素
  System.out.println(object); // 输出集合中的元素
  // 3、删除元素
  link.removeFirst(); // 删除集合第一个元素
  link.pollLast(); // 删除集合最后一个元素
  System.out.println(link);

输出:

[javabuild, happy, new, year]
javabuild
[happy, new]

对比ArrayList

  1. ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;
  2. ArrayList 底层使用的是 Object 数组;LinkedList 底层使用的是双向链表数据结构;
  3. LinkedList 不支持高效的随机元素访问,而 ArrayList(实现了 RandomAccess 接口) 支持。
  4. ArrayList存在扩容问题,LinkedList不存在,直接放在集合尾部,修改指针即可;

提问:为什么LinkedList不支持高效的随机访问,或者说为什么不去实现RandomAccess 接口?

我们看过RandomAccess 接口的底层的同学知道,这个接口也是个标识性接口,只要实现了这个接口就意味着支持通过索引访问元素。由于 LinkedList 底层数据结构是链表,内存地址不连续,只能通过指针来定位,不支持随机快速访问,所以不能实现 RandomAccess 接口。
但是!
在LinkedList中依旧提供了get(int index):获取链表指定位置的元素。

// 获取链表指定位置的元素
public E get(int index) {
  // 下标越界检查,如果越界就抛异常
  checkElementIndex(index);
  // 返回链表中对应下标的元素
  return node(index).item;
}

源码中get方法实现通过位置获取元素的核心是node(index)方法,我们跟进去继续看一下!

// 返回指定下标的非空节点
Node<E> node(int index) {
    // 断言下标未越界
    // assert isElementIndex(index);
    // 如果index小于size的二分之一  从前开始查找(向后查找)  反之向前查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 遍历,循环向后查找,直至 i == index
        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;
    }
}

该方法中通过传入的index参数和size的1/2进行比较,小于则从链表头向后查找,否则从链表尾向前遍历查找,这与ArrayList中的get(index)方法还是有本质上的区别!

结尾彩蛋

如果本篇博客对您有一定的帮助,大家记得留言+点赞+收藏呀。原创不易,转载请联系Build哥!

Java集合篇之深入解析LinkedList,Java成长计划,java,开发语言文章来源地址https://www.toymoban.com/news/detail-825559.html

到了这里,关于Java集合篇之深入解析LinkedList的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java:ArrayList集合、LinkedList(链表)集合的底层原理及应用场景

    入队 出队 压栈(push),addFirst可以替换成push,官方专门为压栈写了push的API 出栈(pop),removeFirst可以替换成pop,官方专门为出栈写了pop的API

    2024年02月12日
    浏览(40)
  • java源码----集合系列1----ArrayList,linkedList

    底层是一个object数组 Arraylist 是java里面Collection  标准的一个集合,其 底层是一个object数组 。当new一个空参的ArrayList的时候,会默认生成一个空数组。 Arraylist上限是 Integer.MAX_VALUE - 8(Integer.MAX_VALUE  =  2^31-1) ; 超过上限会报内存溢出 这里为什么是Integer.MAX_VALUE-8  ,源码上的解

    2024年02月03日
    浏览(44)
  • java集合框架(二)LinkedList常见方法的使用

    @[toc] ## 一、什么是LinkedList LinkedList是Java中的一个双向链表。 它实现了List和Deque接口,在使用时可以像List一样使用元素索引,也可以像Deque一样使用队列操作。 LinkedList每个节点都包含了前一个和后一个节点的引用,因此可以很方便地在其中进行节点的插入、删除和移动。 相

    2024年02月05日
    浏览(45)
  • Java基础——LinkedList集合实现栈和队列

    (1)LinkedList的特点: 底层数据结构是双链表,查询慢,首尾操作的速度是极快的,所以多了很多首位操作的特有API。 (2)LinkedList集合的特有功能: 方法名称 说明 public void addFirst(E e) 在该列表开头插入指定的元素 public void addLast(E e) 将指定的元素追加到此列表的末尾 publ

    2023年04月12日
    浏览(45)
  • 【JAVA语言-第15话】集合框架(二)——List、ArrayList、LinkedList、Vector集合

    目录 List集合 1.1 概述 1.2 特点 1.3 常用方法 1.4 ArrayList集合 1.4.1 概述  1.4.2 练习 1.5 LinkedList集合  1.5.1 概述 1.5.2 特点 1.5.3 常用方法 1.5.4 练习 1.6 Vector类 1.6.1 概述 1.6.2 练习 1.7 List实现类的异同点         java.util.List: List是一个接口,它继承自Collection接口。 常用的实现

    2024年01月25日
    浏览(57)
  • 【JAVA学习笔记】53 - 集合-List类及其子类Collection、ArrayList、LinkedList类

    https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter14/src/com/yinhai/collection_ https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter14/src/com/yinhai/list_ 目录 项目代码 集合 一、引入 数组 集合 二、集合的框架体系 单列集合        双列集合        Collection类 一、Collection类接

    2024年02月06日
    浏览(55)
  • 深入理解Java LinkedList:使用场景与实际应用

    在Java的世界里,集合框架是不可或缺的一部分,它提供了一系列用于存储和操作数据集合的接口和类。其中, LinkedList 作为List接口的一个实现,经常被拿来与 ArrayList 做对比。尽管在实际业务开发中 LinkedList 的使用频率可能不如 ArrayList 高,但这并不意味着它是一个冷门或无

    2024年01月24日
    浏览(59)
  • 集合-LinkedList

    LinkedList的底层使用双向链表实现。 链表是一种线性数据结构,其中每个元素都是一个单独的对象,包含一个指向列表中下一个节点的引用。 它可以用于实现各种抽象数据类型,例如列表、堆栈、队列等。 优点 插入和删除操作的时间复杂度为O(1),相比于数组的O(n)更加高效。

    2023年04月17日
    浏览(45)
  • 【JavaDS】浅谈集合LinkedList的使用

    ✨ 博客主页: XIN-XIANG荣 ✨ 系列专栏: 【Java实现数据结构】 ✨ 一句短话: 难在坚持,贵在坚持,成在坚持! LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元

    2024年02月22日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包