Java链式存储LinkedList—-与ArrayList比较

在这里插入图片描述

作为一名对技术充满热情的学习者,我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代,我远非专家,而是一位不断追求进步的旅行者。通过这篇博客,我想分享我在某个领域的学习经验,与大家共同探讨、共同成长。请大家以开放的心态阅读,相信你们也会在这段知识之旅中找到启示。

文章目录

  • 前言
  • 一、LinkedList类:
      • 使用LinkedList实现链表
  • 二、底层逻辑
  • 三.LinkedList与ArrayList的区别:
      • 代码示例:
  • 总结

前言

同学们,今天我们一起来看看List接口的另一种实现LinkedList,看看如何实现对LinkedList链表的搭建.我们需要结合底层的逻辑,更深层次的熟悉链表数据结构.最后比较我们前面讲到的ArrayList动态数组实现,各自应用场景的不同.


一、LinkedList类:

在Java中,可以使用LinkedList类实现链表数据结构。链表是一种动态数据结构,与数组不同,链表的大小可以动态增长或缩小。

使用LinkedList实现链表

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个LinkedList
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加元素到链表
        linkedList.add("Java");
        linkedList.add("Python");
        linkedList.add("C++");

        // 打印链表中的元素
        System.out.println("Linked List: " + linkedList);

        // 在指定位置插入元素
        linkedList.add(1, "JavaScript");

        // 打印修改后的链表
        System.out.println("Updated Linked List: " + linkedList);

        // 获取链表中的元素
        String element = linkedList.get(2);
        System.out.println("Element at index 2: " + element);

        // 移除链表中的元素
        linkedList.remove("Python");

        // 打印最终的链表
        System.out.println("Final Linked List: " + linkedList);
    }
}

二、底层逻辑

LinkedList 是 Java 中的一个双向链表实现,实际上,它是一个由节点(Node)组成的链表结构。每个节点都包含了数据元素和对前一个节点和后一个节点的引用。

底层逻辑主要包括以下几个方面:

节点结构: LinkedList 中的节点是一个包含数据和两个引用的对象。每个节点有一个指向前一个节点的引用(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 通过头指针(first)和尾指针(last)来标识链表的起始和结束。这些指针指向链表的第一个节点和最后一个节点。

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

添加元素: 在链表末尾或开头添加元素时,可以通过调整节点的引用来实现。添加到末尾时,修改last节点的next引用;添加到开头时,修改first节点的prev引用。
获取元素: 可以通过索引或迭代的方式获取链表中的元素。索引获取时,可以根据索引从头或尾开始遍历链表。
删除元素: 删除元素时,同样通过调整节点的引用来实现。如果删除的是中间节点,需要修改前一个节点的next引用和后一个节点的prev引用。
迭代器: LinkedList 提供了迭代器(ListIterator)来方便地遍历链表。

三.LinkedList与ArrayList的区别:

LinkedList 和 ArrayList 是 Java 中 List 接口的两个不同实现,它们在内部实现和性能特点上有一些区别。以下是它们之间的主要区别以及适用场景:
1.内部实现:

  • ArrayList 使用动态数组来存储元素,支持通过索引直接访问元素,因此对于随机访问和按索引查找性能较好。
  • LinkedList 使用双向链表来存储元素,对于插入和删除元素的操作较为高效,但对于随机访问性能较差。

2.随机访问性能:

  • ArrayList 对于随机访问非常高效,因为它可以通过索引直接访问数组元素,时间复杂度为 O(1)。
  • LinkedList 对于随机访问的性能相对较差,因为需要从链表的头部或尾部开始遍历,时间复杂度为 O(n),其中 n 是链表的长度。

3.插入和删除性能:

  • ArrayList 在中间插入或删除元素时,需要移动元素,因此效率较低,时间复杂度为 O(n)。
  • LinkedList 在插入和删除元素时,由于只需要调整相邻节点的引用,因此效率较高,时间复杂度为 O(1)。

4.空间复杂度:

  • ArrayList 的空间复杂度较小,因为它只需存储元素和数组的一些元信息。
  • LinkedList 的空间复杂度相对较大,因为每个节点都需要额外的空间存储两个引用。

5.适用场景:

  • 使用 ArrayList:
    1.当需要频繁进行随机访问和按索引查找时。
    2.数据集的大小是已知的或者相对固定的情况下。
  • 使用 LinkedList:
    1.当需要频繁进行插入和删除操作时,尤其是在中间位置。
    2.当数据集的大小可能动态变化,并且对内存占用不是主要关注点时。

代码示例:

ArrayList 示例:

import java.util.ArrayList;

public class ArrayList示例 {
    public static void main(String[] args) {
        // 创建一个 ArrayList
        ArrayList<String> arrayList = new ArrayList<>();

        // 向 ArrayList 中添加元素
        arrayList.add("Java");
        arrayList.add("Python");
        arrayList.add("C++");

        // 使用索引访问元素
        System.out.println("索引 1 处的元素: " + arrayList.get(1));

        // 遍历 ArrayList
        System.out.print("ArrayList 中的元素: ");
        for (String element : arrayList) {
            System.out.print(element + " ");
        }

        // 移除一个元素
        arrayList.remove("Python");

        // 移除后的最终 ArrayList
        System.out.print("
移除后的 ArrayList: ");
        for (String element : arrayList) {
            System.out.print(element + " ");
        }
    }
}

LinkedList 示例:

import java.util.LinkedList;

public class LinkedList示例 {
    public static void main(String[] args) {
        // 创建一个 LinkedList
        LinkedList<String> linkedList = new LinkedList<>();

        // 向 LinkedList 中添加元素
        linkedList.add("Java");
        linkedList.add("Python");
        linkedList.add("C++");

        // 使用索引访问元素
        System.out.println("索引 1 处的元素: " + linkedList.get(1));

        // 遍历 LinkedList
        System.out.print("LinkedList 中的元素: ");
        for (String element : linkedList) {
            System.out.print(element + " ");
        }

        // 在开头添加一个元素
        linkedList.addFirst("JavaScript");

        // 添加后的最终 LinkedList
        System.out.print("
添加后的 LinkedList: ");
        for (String element : linkedList) {
            System.out.print(element + " ");
        }
    }
}

总结

在学习List接口的两种不同的实现方式时,我们要尝试比较,在未来的应用时,选择合适的数据结构要取决于不同的应用场景.前提是大家对这两种结构的熟练程度是非常高的,希望大家可以对找点题目练练手,加深印象.

感谢大家阅读博主的文章,新人博主希望大家多多关注,我希望和大家一同进步,祝福大家在未来学习工作的路上一帆风顺,加油!!!