初识数据结构——深入理解LinkedList与链表：吃透LinkedList与链表的终极指南

📌 深入理解LinkedList与链表：从原理到实战应用

🌟 引言

在Java集合框架中，LinkedList和ArrayList是最常用的两种列表结构。它们各有优劣，适用于不同的场景。本文将带你深入探索LinkedList的底层实现——链表，并通过丰富的代码示例和对比分析，帮助你全面掌握其特性和应用场景。

📚 1. ArrayList的缺陷

ArrayList底层基于动态数组实现，虽然支持高效的随机访问（时间复杂度为O(1)），但在任意位置插入或删除元素时，需要搬移后续元素，导致时间复杂度为O(n)。例如：

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // 添加到末尾，O(1)
list.add(0, 0); // 插入到头部，O(n)

缺陷总结：

• 插入/删除效率低（尤其是头部或中间位置）。
• 扩容时需要拷贝数据，额外开销大。

🔗 2. 链表：LinkedList的底层结构

2.1 链表的概念

链表是一种物理存储非连续的数据结构，通过节点的引用（指针）实现逻辑上的连续性。

特点：

• 节点包含数据域和指针域。
• 物理上不连续，逻辑上连续。

2.2 链表的分类

链表有多种结构组合，常见的两种：

1. 无头单向非循环链表：结构简单，常用于面试题。

2. 无头双向循环链表：Java中LinkedList的底层实现。

双向链表节点定义：

class Node {
    int val;
    Node prev;
    Node next;
}

⚙️ 3. LinkedList的模拟实现

以下是一个简化版的双向链表实现：

public class MyLinkedList {
    private Node head;
    private Node tail;
    private int size;

    // 头插法
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    // 删除指定值的节点
    public void remove(int key) {
        Node cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) head.prev = null;
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) cur.next.prev = cur.prev;
                }
                size--;
                return;
            }
            cur = cur.next;
        }
    }
}

🛠️ 4. LinkedList的使用

4.1 Java集合框架部分：LinkedList继承体系（思维导图）

4.2 常用方法

4.3 遍历方式

// 1. for-each循环
for (int num : list) {
    System.out.print(num + " ");
}

// 2. 迭代器
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    System.out.print(it.next() + " ");
}

// 3. 反向迭代器
Iterator<Integer> rit = list.descendingIterator();
while (rit.hasNext()) {
    System.out.print(rit.next() + " ");
}

🧩 5. 经典链表OJ题解析

5.1 反转链表

题目：反转一个单链表。
代码：

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

5.2 判断链表是否有环

快慢指针法：

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

📊 6. ArrayList vs LinkedList

选择建议：

• 需要快速随机访问？选ArrayList！
• 频繁在头部或中间插入/删除？选LinkedList！

💡 7.记忆技巧

Iterable是根源，
Collection分三派(List/Queue/Set)，
List有三各不同：
数组实现ArrayList，
链表实现LinkedList，
线程安全Vector顶。

标记接口要记清：
Serializable可序列，
Cloneable能复制，
RandomAccess随机快。

🎯 总结

• 链表通过节点引用实现逻辑连续，适合频繁修改的场景。
• LinkedList在Java中基于双向链表实现，提供了高效的插入/删除操作。
• 理解链表的核心在于掌握指针操作和边界条件处理。

通过本文的学习，相信你对链表和LinkedList有了更深入的理解！快去LeetCode上挑战更多链表题目吧！

💬 互动话题：你在项目中用过LinkedList吗？遇到过哪些坑？欢迎评论区分享！