Java 核心数据结构：LinkedList 原理与手动实现

前言

本文探讨链表结构与 Java 中 LinkedList 的实现细节。若已掌握顺序表基础，理解这部分会更加顺畅。我们将结合集合框架理论，深入分析其特性与应用。

一、Java 集合框架概览

Java 集合体系用于存储和操作对象，核心分为 Collection（单列） 和 Map（双列）。

核心接口分类

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

LinkedList 定位

LinkedList 实现了 List 接口（列表操作）和 Deque 接口（双端队列特性，支持栈/队列行为）。

核心特性

• 结构：双向链表，节点存储前驱和后继引用，无固定容量限制。
• 访问效率：随机访问（get(i)）需遍历，时间复杂度 O(n)。
• 增删效率：在两端或已知节点附近操作效率高，时间复杂度 O(1)。
• 线程安全：非线程安全，多线程环境需外部同步。

二、链表数据结构解析

链表使用非连续存储单元，通过指针链接节点。

关键概念

• 节点（Node）：包含数据域（业务数据）和指针域（指向下一节点地址）。
• 头指针：指向第一个节点的引用，是访问入口。
• 尾节点：最后一个节点，指针域通常指向 null。

三、手动实现单向链表

为了深入理解底层机制，我们可以尝试手动实现一个无头结点的单向链表。这有助于掌握指针操作与内存管理。

节点定义

static class ListNode {
    int val;
    ListNode next;

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

public ListNode head;

核心方法实现

// 创建测试链表
public ListNode createList() {
    ListNode node0 = new 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);
     (ret == ) {
        System.out.println();
        ;
    }
       ret.next;
    ret.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();
}