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

2023-11-17 11:40:21 浏览数 (1)


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),指向前一个节点和后一个节点。

代码语言:java复制
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中,我们还需要维护两个指针,分别指向链表的头部和尾部。

代码语言:java复制
transient Node<E> first;
transient Node<E> last;

添加元素

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

  • 链表为空,直接把新元素设置为第一个元素。
  • 新元素需要插入到链表头部。
  • 新元素需要插入到链表尾部。
  • 新元素需要插入到链表中间。
代码语言:java复制
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中删除元素时,需要考虑以下几种情况:

  • 链表为空。
  • 待删除元素是第一个元素。
  • 待删除元素是最后一个元素。
  • 待删除元素在链表中间。
代码语言:java复制
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类进行测试的代码:

测试代码

代码语言:java复制
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腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!

0 人点赞