滚雪球学Java(59):从基础到高阶:Java中LinkedList的操作指南

简介: 【6月更文挑战第13天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!

在这里插入图片描述

  咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE相关知识点了,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~

在这里插入图片描述


🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!

环境说明:Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

@[toc]

前言

  在Java开发中,LinkedList是一个非常常见的数据结构,常用于实现栈、队列等数据结构。本文将从Java中LinkedList的基本概念和操作开始,逐步深入,介绍Linkedlist的源代码解析、应用场景案例、优缺点分析以及类代码方法介绍等内容,最后给出测试用例和全文小结。

摘要

  本文将介绍Java中LinkedList的基础知识,包括数据结构定义、基本操作、源代码解析等;随后将介绍LinkedList的应用场景案例、优缺点分析以及类代码方法介绍等内容。本文将帮助读者全面了解LinkedList,在实际开发中灵活运用,提升代码效率和质量。

LinkedList

概述

  LinkedList属于Java中的集合,是一种线性结构,可以存储不同类型的元素,并且可以动态改变元素数量。LinkedList采用链表的数据结构实现,它的每个节点都保存了下一个节点的内存地址,因此可以实现动态添加、删除和查找等操作。在实际开发中,LinkedList被广泛应用于栈、队列等数据结构的实现;同时也可以用于缓存、列表等场景中。

源代码解析

  LinkedList是Java中的一个双向链表实现的集合类,它实现了List和Deque接口,提供了插入、删除、查找等操作方法。接下来我们来分析一下LinkedList的源码。

1. 定义

LinkedList的源码位于java.util包下,其定义如下:

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

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

    //...省略部分代码
}

  可以看到LinkedList定义了三个成员变量:size表示链表的大小,first表示第一个节点,last表示最后一个节点,这三个变量都是transient类型的,表示不会被序列化。由于LinkedList实现了List接口,因此还需要实现List接口中的抽象方法,这里就不一一列出了。

2. 节点类Node

  LinkedList中的元素都被封装成Node对象,其定义如下:

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;
    }
}

  每个节点包含三个属性:item表示节点存储的元素,next表示下一个节点,prev表示上一个节点。节点类使用了private修饰符,表示只能在LinkedList内部访问。

3. add方法

  add方法是LinkedList中最基本的方法之一,用于在链表尾部添加一个元素,其源码如下:

public boolean add(E e) {
   
   
    linkLast(e);
    return true;
}

void linkLast(E e) {
   
   
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
}

  可以看到,linkLast方法是用于在链表尾部插入节点的,它首先得到链表最后一个节点l,然后创建一个新的节点newNode,并将之前的last节点的next指向newNode。如果链表为空,newNode就成为了第一个节点,否则就将newNode连接在l之后。最后,链表的长度加1。

4. get方法

  get方法用于获取链表中指定位置的元素,其源码如下:

public E get(int index) {
   
   
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
   
   
    if (index < (size >> 1)) {
   
   
        Node<E> x = first;
        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;
    }
}

  可以看到,get方法首先调用了checkElementIndex方法,用于检查index是否越界。然后调用node方法,获取指定位置的节点。node方法根据index的值,选择从头部或尾部开始遍历链表,找到目标节点并返回其元素值。

5. remove方法

  remove方法用于从链表中删除指定位置的元素,其源码如下:

public E remove(int index) {
   
   
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
   
   
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
   
   
        first = next;
    } else {
   
   
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
   
   
        last = prev;
    } else {
   
   
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    return element;
}

  可以看到,remove方法首先调用了checkElementIndex方法,用于检查index是否越界。然后调用unlink方法,用于删除指定节点。unlink方法首先保存了目标节点的前一个节点和后一个节点,然后将它们连接起来,去除目标节点的引用,最后返回目标节点的元素值。

  以上是LinkedList的源码分析,通过了解LinkedList的实现原理,我们可以更好地利用它来实现一些需求。

  如下是部分源码截图:

在这里插入图片描述

存储结构

  LinkedList采用链表的数据结构实现,将每个元素封装成一个Node节点,每个节点都有两个属性:元素值和指向下一个节点的指针。因此,每个节点在内存中都是相互独立的,可以独立增删,设计上也更灵活。

基本操作

  Linkedlist提供了一系列基本操作,包括添加元素、删除元素、查找元素、获取元素等。其中较为常见的操作有以下几种:

  • add(E e):在LinkedList的末尾添加一个元素。
  • addFirst(E e):在LinkedList的开头添加一个元素。
  • addLast(E e):在LinkedList的末尾添加一个元素。
  • remove():删除LinkedList中的第一个元素。
  • remove(Object o):删除LinkedList中指定的元素。
  • removeFirst():删除LinkedList中的第一个元素。
  • removeLast():删除LinkedList中的最后一个元素。
  • size():获取LinkedList的元素数量。
  • get(int index):根据下标获取LinkedList中指定的元素。
  • set(int index, E element):替换LinkedList中指定下标的元素。

  如下是部分源码截图:

在这里插入图片描述

应用场景案例

LinkedList的应用场景非常丰富,主要包括以下几种:

  • 实现栈和队列:LinkedList可以作为栈和队列的底层数据结构,实现入栈、出栈、入队、出队等功能。
  • 缓存:如果需要存储大量的数据,并且需要快速访问最近使用的数据,可以使用LinkedList实现缓存,将最近访问的数据放在LinkedList的头部,当缓存已满时,将最久未使用的数据删除。
  • 列表:LinkedList可以用来存储和操作列表数据,如添加、删除和移动元素等。
  • 循环链表:LinkedList可以实现循环链表,即最后一个节点指向第一个节点,可以实现循环遍历和处理操作。

优缺点分析

LinkedList的优点如下:

  • 可以动态添加、删除元素,在元素数量未知或者动态变化的情况下使用更为灵活。
  • 添加、删除元素时,不需要移动其他元素,操作效率较高。
  • 可以存储不同类型的元素,具有较高的灵活性。

LinkedList的缺点如下:

  • 查找、访问LinkedList中的元素时,需要遍历LinkedList,效率较低。
  • 需要额外的内存空间来存储节点的指针信息。

类代码方法介绍

LinkedList类的主要方法如下:

public boolean add(E e);              // 添加元素到LinkedList的末尾
public void add(int index, E element);// 添加元素到LinkedList的指定位置
public void addFirst(E e);           // 添加元素到LinkedList的开头
public void addLast(E e);            // 添加元素到LinkedList的末尾
public void clear();                 // 清空LinkedList中的所有元素
public Object clone();               // 复制LinkedList
public boolean contains(Object o);   // 判断LinkedList中是否包含指定元素
public E get(int index);             // 获取LinkedList中指定位置的元素
public E getFirst();                 // 获取LinkedList中的第一个元素
public E getLast();                  // 获取LinkedList中的最后一个元素
public int indexOf(Object o);        // 获取LinkedList中指定元素的下标
public boolean isEmpty();            // 判断LinkedList是否为空
public Iterator<E> iterator();       // 获取LinkedList的迭代器
public int lastIndexOf(Object o);    // 获取LinkedList中指定元素最后一次出现的下标
public ListIterator<E> listIterator();// 获取LinkedList的列表迭代器
public boolean remove(Object o);     // 删除LinkedList中指定元素
public E remove(int index);          // 删除LinkedList中指定下标的元素
public E removeFirst();              // 删除LinkedList中的第一个元素
public boolean removeFirstOccurrence(Object o);// 删除LinkedList中第一次出现的指定元素
public E removeLast();               // 删除LinkedList中的最后一个元素
public boolean removeLastOccurrence(Object o);// 删除LinkedList中最后一次出现的指定元素
public int size();                   // 获取LinkedList中的元素数量
public Object[] toArray();           // 将LinkedList转化为数组

代码分析

  LinkedList是Java集合框架中的一种双向链表实现的列表,支持快速的增删改查操作。其常用方法包括:

  1. add(E e):在列表末尾添加元素,返回是否添加成功。
  2. add(int index, E element):在指定位置插入元素,返回是否插入成功。
  3. addFirst(E e):在列表开头插入元素。
  4. addLast(E e):在列表末尾插入元素。
  5. clear():清空列表中的所有元素。
  6. clone():克隆一个新的LinkedList。
  7. contains(Object o):判断列表中是否包含指定元素。
  8. get(int index):获取指定位置的元素。
  9. getFirst():获取列表中的第一个元素。
  10. getLast():获取列表中的最后一个元素。
  11. indexOf(Object o):返回指定元素在列表中的首次出现位置的索引,若不存在则返回-1。
  12. isEmpty():判断列表是否为空。
  13. iterator():返回一个迭代器,用于遍历列表中的元素。
  14. lastIndexOf(Object o):返回指定元素在列表中最后一次出现位置的索引,若不存在则返回-1。
  15. listIterator():返回一个列表迭代器,用于遍历列表中的元素。
  16. remove(Object o):移除列表中的指定元素,返回是否移除成功。
  17. remove(int index):移除列表中指定位置的元素,返回被移除的元素。
  18. removeFirst():移除列表中第一个元素。
  19. removeFirstOccurrence(Object o):移除列表中第一次出现的指定元素,返回是否移除成功。
  20. removeLast():移除列表中的最后一个元素。
  21. removeLastOccurrence(Object o):移除列表中最后一次出现的指定元素,返回是否移除成功。
  22. size():返回列表中的元素个数。
  23. toArray():将列表转换为一个数组。

测试用例

测试代码演示

下面给出LinkedList的一个简单测试用例:

package com.demo.javase.day59;

import java.util.LinkedList;

/**
 * @Author bug菌
 * @Date 2023-11-05 23:48
 */
public class LinkedListTest {
   
   

    public static void main(String[] args) {
   
   
        LinkedList<String> linkedList = new LinkedList<String>();

        // 添加元素到LinkedList
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");

        // 打印LinkedList中的元素
        System.out.println(linkedList);

        // 在LinkedList的开头和末尾添加元素
        linkedList.addFirst("D");
        linkedList.addLast("E");

        // 打印LinkedList中的元素
        System.out.println(linkedList);

        // 删除LinkedList中的第一个和最后一个元素
        linkedList.removeFirst();
        linkedList.removeLast();

        // 打印LinkedList中的元素
        System.out.println(linkedList);

        // 获取LinkedList中的元素数量
        int size = linkedList.size();
        System.out.println("size: " + size);

        // 根据下标获取LinkedList中指定的元素
        String element = linkedList.get(1);
        System.out.println("element: " + element);

        // 替换LinkedList中指定下标的元素
        linkedList.set(1, "F");

        // 打印LinkedList中的元素
        System.out.println(linkedList);
    }
}

测试结果

  根据如上测试用例,本地测试结果如下,仅供参考,你们也可以自行修改测试用例或者添加更多的测试数据或测试方法,进行熟练学习以此加深理解。

在这里插入图片描述

测试代码分析

  根据如上测试用例,在此我给大家进行深入详细的解读一下测试代码,以便于更多的同学能够理解并加深印象。

这是一个使用Java中的LinkedList类进行操作的示例代码。主要实现了以下功能:

  1. 创建一个空的LinkedList对象。
  2. 向LinkedList中添加元素。
  3. 在LinkedList的开头和末尾添加元素。
  4. 删除LinkedList中的第一个和最后一个元素。
  5. 获取LinkedList中的元素数量。
  6. 根据下标获取LinkedList中指定的元素。
  7. 替换LinkedList中指定下标的元素。

运行代码后,会输出LinkedList中的元素以及各种操作后的结果。

全文小结

  本文对Java中LinkedList的基础概念和操作进行了详细介绍,包括存储结构、基本操作、应用场景案例、优缺点分析以及类代码方法介绍等内容。希望读者可以通过本文全面了解并掌握LinkedList的使用方法,提升在实际开发中的应用能力和水平。

总结

  LinkedList是Java中常用的一种集合,可用于实现栈、队列、缓存、列表等场景中。LinkedList采用链式存储结构实现,每个节点都保存了下一个节点的内存地址,因此可以实现动态添加、删除和查找等操作。在使用LinkedList时需要注意

  ...
  好啦,这期的内容就基本接近尾声啦,若你想学习更多,可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》,本专栏致力打造最硬核 Java 零基础系列学习内容,🚀打造全网精品硬核专栏,带你直线超车;欢迎大家订阅持续学习。

附录源码

  如上涉及所有源码均已上传同步在「Gitee」,提供给同学们一对一参考学习,辅助你更迅速的掌握。

☀️建议/推荐你


  无论你是计算机专业的学生,还是对编程有兴趣的小伙伴,都建议直接毫无顾忌的学习此专栏「滚雪球学Java」,bug菌郑重承诺,凡是学习此专栏的同学,均能获取到所需的知识和技能,全网最快速入门Java编程,就像滚雪球一样,越滚越大,指数级提升。

  最后,如果这篇文章对你有所帮助,帮忙给作者来个一键三连,关注、点赞、收藏,您的支持就是我坚持写作最大的动力。


目录
相关文章
|
8天前
|
Java BI 数据处理
如何在Java中实现Excel操作
如何在Java中实现Excel操作
|
15天前
|
存储 Java
java用modbus4j的RTU去操作那些寄存器(线圈,保持,输入,离散输入寄存器)
java用modbus4j的RTU去操作那些寄存器(线圈,保持,输入,离散输入寄存器)
37 0
|
23天前
|
Java 数据库 数据安全/隐私保护
Java操作Excel文件导入导出【内含有 jxl.jar 】
Java操作Excel文件导入导出【内含有 jxl.jar 】
28 0
|
22天前
|
存储 Java 测试技术
滚雪球学Java(67):深入理解 TreeMap:Java 中的有序键值映射表
【6月更文挑战第21天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
21 2
滚雪球学Java(67):深入理解 TreeMap:Java 中的有序键值映射表
|
23天前
|
存储 Java 测试技术
滚雪球学Java(66):Java之HashMap详解:深入剖析其底层实现与源码分析
【6月更文挑战第20天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
21 3
滚雪球学Java(66):Java之HashMap详解:深入剖析其底层实现与源码分析
|
5天前
|
SQL 缓存 Java
使用MyBatis优化Java持久层操作
使用MyBatis优化Java持久层操作
|
10天前
|
Java API 开发者
Java中的文件I/O操作详解
Java中的文件I/O操作详解
|
10天前
|
Java BI 数据处理
如何在Java中实现Excel操作
如何在Java中实现Excel操作
|
17天前
|
Java
使用kafka-clients操作数据(java)
使用kafka-clients操作数据(java)
19 6
|
19天前
|
安全 Java 程序员
在Java中,finalization是一种机制,允许对象在被垃圾收集器回收之前执行一些清理操作。
【6月更文挑战第24天】Java中的finalization机制允许对象在被垃圾收集前执行清理,以释放系统资源或处理敏感信息。`finalize()`方法用于定义此类操作,但它不是可靠的资源管理策略,因为调用时机不确定且可能影响性能。尽管可用于清理外部资源或作为保护措施,但应避免依赖finalization,而应优先采用手动资源管理,遵循“创建者负责”原则。
14 1