Java中LinkedList的详解：从头到尾了解

原创

喵手

发布于 2023-11-17 11:40:21

2300

发布于 2023-11-17 11:40:21

文章被收录于专栏：Java进阶实战

theme: healer-readable

highlight: a11y-dark

哈喽，各位小伙伴们，你们好呀，我是喵手。

今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

如下是Java集合体系架构图，近期几期内容都是围绕该体系进行知识讲解，以便于同学们学习Java集合篇知识能够系统化而不零散。

前言

在Java开发中，数据结构是必不可少的一部分。数据结构的选择和使用对程序的性能和可维护性有很大的影响。LinkedList是Java中的一种重要的数据结构，它不仅可以存储数据，还可以支持插入、删除等操作。

摘要

本文主要介绍LinkedList的概念、原理、源代码解析、应用场景案例、优缺点分析以及类代码方法介绍，同时给出相应的测试用例。

LinkedList集合

简介

LinkedList是Java中的一个类，它实现了List接口和Deque接口。LinkedList底层是基于链表实现的，因此它可以支持高效的插入和删除操作。LinkedList还支持快速访问链表的第一个和最后一个元素。

源代码解析

LinkedList的源代码实现主要包括以下几个部分：

Node节点类

LinkedList中的每个元素被封装成一个Node对象，每个Node对象包含一个数据域和两个指针域（prev和next），指向前一个节点和后一个节点。

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

涉及源码如下：

链表头和尾的指针

在LinkedList中，我们还需要维护两个指针，分别指向链表的头部和尾部。

transient Node<E> first;
transient Node<E> last;

添加元素

向LinkedList中添加元素时，需要考虑以下几种情况：

链表为空，直接把新元素设置为第一个元素。
新元素需要插入到链表头部。
新元素需要插入到链表尾部。
新元素需要插入到链表中间。

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
}

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

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
}

删除元素

从LinkedList中删除元素时，需要考虑以下几种情况：

链表为空。
待删除元素是第一个元素。
待删除元素是最后一个元素。
待删除元素在链表中间。

private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; 
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    return element;
}

private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; 
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    return element;
}

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

更多的你们可以去看看它的源码，这里就不多多介绍了：

应用场景案例

LinkedList主要适用于以下场景：

需要频繁地进行插入和删除操作。
不需要对元素进行排序或者特定位置的访问操作。

LinkedList常被用于实现栈和队列等数据结构，以及基于事件的程序（如GUI应用程序）。

优缺点分析

优点

支持高效的插入和删除操作。
可以方便地实现栈和队列等数据结构。
支持快速访问链表的第一个和最后一个元素。

缺点

不支持快速访问链表中的特定元素。
需要额外的内存空间来存储节点的指针。

类代码方法介绍

以下是LinkedList类中部分常用方法的介绍：

add(E e)：将元素添加到链表尾部。
addFirst(E e)：将元素添加到链表头部。
addLast(E e)：将元素添加到链表尾部。
remove()：删除并返回链表的首元素。
removeFirst()：删除并返回链表的首元素。
removeLast()：删除并返回链表的尾元素。
size()：返回链表中元素的个数。
get(int index)：返回链表中指定位置的元素。

测试用例

以下是对LinkedList类进行测试的代码：

测试代码

package com.example.javase.collection;

import java.util.LinkedList;

/**
 * @Author ms
 * @Date 2023-10-20 19:50
 */
public class LinkedListTest {

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

        // Add elements to the list
        list.add(1);
        list.add(2);
        list.add(3);

        // Test the addFirst method
        list.addFirst(0);
        System.out.println(list);

        // Test the addLast method
        list.addLast(4);
        System.out.println(list);

        // Test the remove method
        list.remove();
        System.out.println(list);

        // Test the removeFirst method
        list.removeFirst();
        System.out.println(list);

        // Test the removeLast method
        list.removeLast();
        System.out.println(list);

        // Test the size method
        System.out.println("Size of the list: " + list.size());

        // Test the get method
        System.out.println("Element at index 1: " + list.get(1));
    }
}

测试结果

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

测试代码分析

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

全文小结

本文介绍了Java中的LinkedList类，包括其概念、原理、源代码解析、应用场景案例、优缺点分析以及类代码方法介绍。通过测试用例的演示，展示了LinkedList类的基本使用方法。LinkedList类是Java中非常实用的数据结构，可以方便地进行插入和删除操作，适用于很多场景。同时，它也有一些缺点需要注意。在实际开发中，我们需要根据具体的需求选择合适的数据结构。

总结

本文主要介绍了Java中的LinkedList类，包括其概念、原理、源代码解析、应用场景案例、优缺点分析以及类代码方法介绍。LinkedList底层基于链表实现，支持高效的插入和删除操作，常被用于实现栈和队列等数据结构，以及基于事件的程序。其优点包括支持高效的插入和删除操作，可以方便地实现栈和队列等数据结构，支持快速访问链表的第一个和最后一个元素。缺点包括不支持快速访问链表中的特定元素，需要额外的内存空间来存储节点的指针。常用方法包括add、remove、size、get等。在实际开发中，我们需要根据具体的需求选择合适的数据结构。

... ...

文末

好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。

... ...

学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！

wished for you successed ！！！

⭐️若喜欢我，就请关注我叭。

⭐️若对您有用，就请点赞叭。

⭐️若有疑问，就请评论留言告诉我叭。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

2023腾讯·技术创作特训营第三期

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

2023腾讯·技术创作特训营第三期

登录后参与评论

0 条评论

热度