Java 链表基础与 LinkedList 核心原理

Java 集合框架概览

Java 集合框架是存储和操作对象的核心体系，主要分为 Collection（单列集合） 和 Map（双列集合）。

核心接口与分类

• Collection：单列集合的根接口，定义增删改查及遍历等基本操作。其子接口包括 List（有序可重复）、Set（无序不可重复）和 Queue（队列）。
• Map：存储键值对（Key-Value），Key 唯一，Value 可重复。子接口包含 SortedMap（键有序）。

今天我们重点探讨 Collection 下的 LinkedList。

LinkedList 特性

1. 实现的接口
   • 实现了 List 接口，具备列表的增删改查能力。
   • 实现了 Deque 接口，兼具双端队列特性，可作为栈或队列使用。
2. 核心结构
   • 基于双向链表，每个节点存储前驱和后继节点的引用，无容量限制。
3. 性能特点
   • 随机访问：通过索引 get(i) 效率较低（时间复杂度 O(n)），需从头遍历。
   • 增删操作：在链表两端或已知节点附近增删元素效率高（时间复杂度 O(1)）。
   • 线程安全：非线程安全，多线程环境下需手动同步。

作为 List 接口的实现，它继承了有序集合的基础行为；作为 Deque 的实现，它支持首尾双向操作。相比 ArrayList（数组实现），LinkedList 在频繁的首尾插入删除场景下更具优势，但随机访问性能较弱。

数据结构中的链表

链表是用非连续存储单元存储元素的线性表。理解其底层结构有助于掌握 LinkedList 的行为。

• 节点（Node）：基本存储单元，包含数据域（业务数据）和指针域（指向下一个/上一个节点的引用）。
• 头指针：指向链表第一个节点的引用，是访问入口。
• 尾节点：最后一个节点，指针域通常指向 null（单向）或头节点（循环）。

手动实现单链表

为了深入理解，我们可以尝试手动实现一个无头结点的单项链表。虽然 Java 提供了 LinkedList，但手写过程能清晰展示内存引用的变化逻辑。

以下代码分为成员变量、构造辅助方法、核心业务方法三部分。

节点定义与成员变量

static class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public ListNode head;

核心操作方法

这里展示了创建链表、头插法、尾插法、指定位置插入以及查找删除等基础逻辑。

// 创建测试链表
 ListNode  {
        ();
        ();
        ();
        ();
        ();
    
    node0.next = node1;
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    head = node0;
     head;
}


   {
        (data);
    node.next = head;
    head = node;
}


   {
        (data);
     (head == ) {
        head = node;
        ;
    }
       head;
     (cur.next != ) {
        cur = cur.next;
    }
    cur.next = node;
}


   {
     (index <  || index > size()) {
        System.out.println();
        ;
    }
     (index == ) {
        addFirst(data);
        ;
    }
     (index == size()) {
        addLast(data);
        ;
    }
       findIndex(index - );
        (data);
    node.next = cur.next;
    cur.next = node;
}


 ListNode  {
       head;
       ;
     (count != index) {
        cur = cur.next;
        count++;
    }
     cur;
}


   {
       head;
     (cur != ) {
         (cur.val == key) {
             ;
        }
        cur = cur.next;
    }
     ;
}


   {
     (head == ) {
        System.out.println();
        ;
    }
    
     (head.val == key) {
        head = head.next;
        ;
    }
    
       search(key);
     (prev == ) {
        System.out.println();
        ;
    }
       prev.next;
    prev.next = del.next;
}


 ListNode  {
       head;
     (cur.next != ) {
         (cur.next.val == val) {
             cur;
        }
        cur = cur.next;
    }
     ;
}


   {
     (head == ) {
        System.out.println();
        ;
    }
    
     (head !=  && head.val == key) {
        head = head.next;
    }
     (head == ) ;
    
       head;
       head.next;
     (cur != ) {
         (cur.val == key) {
            prev.next = cur.next;
        }  {
            prev = cur;
        }
        cur = cur.next;
    }
}


   {
       ;
       head;
     (cur != ) {
        count++;
        cur = cur.next;
    }
     count;
}


   {
       head;
     (cur != ) {
           cur.next;
        cur.next = ; 
        cur = next;
    }
    head = ;
}


   {
       head;
     (cur != ) {
        System.out.print(cur.val + );
        cur = cur.next;
    }
    System.out.println();
}