作为一名对技术充满热情的学习者，我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代，我远非专家，而是一位不断追求进步的旅行者。通过这篇博客，我想分享我在某个领域的学习经验，与大家共同探讨、共同成长。请大家以开放的心态阅读，相信你们也会在这段知识之旅中找到启示。
前言
同学们,今天我们一起来看看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("\n移除后的 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("\n添加后的 LinkedList: "); for (String element : linkedList) { System.out.print(element + " "); } } }
总结
在学习List接口的两种不同的实现方式时,我们要尝试比较,在未来的应用时,选择合适的数据结构要取决于不同的应用场景.前提是大家对这两种结构的熟练程度是非常高的,希望大家可以对找点题目练练手,加深印象.
感谢大家阅读博主的文章,新人博主希望大家多多关注,我希望和大家一同进步,祝福大家在未来学习工作的路上一帆风顺,加油!!!
