Java如何实现LinkedList？核心步骤是什么？-杰瑞科技汇

理解链表结构

我们需要明确链表的两个核心组成部分：

（图片来源网络，侵删）

节点：链表中的每个元素都是一个节点，它包含两部分：
- 数据：节点存储的实际值。
- 指针：指向下一个节点（前驱指针 prev）和上一个节点（后继指针 next），对于单向链表，只需要后继指针；对于双向链表，两者都需要。
链表本身：链表对象本身并不存储所有数据，它只持有对头节点的引用，通过头节点，我们可以遍历到链表中的任何一个节点。

实现步骤

我们将分三步来实现：

创建 Node 内部类。
创建 MyLinkedList 类，并定义其基本属性和构造方法。
在 MyLinkedList 类中实现各种操作方法。

完整代码实现

下面是一个完整的、可运行的 MyLinkedList 实现。

（图片来源网络，侵删）

import java.util.NoSuchElementException;
/**
 * 一个自定义的、基于 Java 的双向链表实现。
 * @param <T> 链表中存储的数据类型
 */
public class MyLinkedList<T> {
    /**
     * 内部 Node 类，代表链表中的一个节点。
     */
    private static class Node<T> {
        T data;      // 节点存储的数据
        Node<T> prev; // 指向前一个节点的指针
        Node<T> next; // 指向后一个节点的指针
        // 构造方法
        Node(T data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }
    private Node<T> head; // 指向链表的头节点
    private Node<T> tail; // 指向链表的尾节点 (优化操作)
    private int size;     // 链表中元素的数量
    /**
     * 构造一个空的链表。
     */
    public MyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }
    // ===== 核心操作方法 =====
    /**
     * 在链表头部添加一个元素。
     * @param data 要添加的元素
     */
    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            // 如果链表为空，新节点既是头也是尾
            head = newNode;
            tail = newNode;
        } else {
            // 链表不为空
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }
    /**
     * 在链表尾部添加一个元素。
     * @param data 要添加的元素
     */
    public void addLast(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            // 如果链表为空，新节点既是头也是尾
            head = newNode;
            tail = newNode;
        } else {
            // 链表不为空
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }
    /**
     * 在指定索引位置插入一个元素。
     * @param index 要插入的位置
     * @param data  要插入的元素
     * @throws IndexOutOfBoundsException 如果索引越界
     */
    public void add(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            addFirst(data);
        } else if (index == size) {
            addLast(data);
        } else {
            // 找到要插入位置的前一个节点
            Node<T> prevNode = getNodeAtIndex(index - 1);
            Node<T> newNode = new Node<>(data);
            Node<T> nextNode = prevNode.next;
            // 重新链接节点
            prevNode.next = newNode;
            newNode.prev = prevNode;
            newNode.next = nextNode;
            nextNode.prev = newNode;
            size++;
        }
    }
    /**
     * 删除并返回头部的元素。
     * @return 被删除的头部元素
     * @throws NoSuchElementException 如果链表为空
     */
    public T removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("List is empty");
        }
        Node<T> toRemove = head;
        if (size == 1) {
            // 只有一个节点
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        size--;
        return toRemove.data;
    }
    /**
     * 删除并返回尾部的元素。
     * @return 被删除的尾部元素
     * @throws NoSuchElementException 如果链表为空
     */
    public T removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("List is empty");
        }
        Node<T> toRemove = tail;
        if (size == 1) {
            // 只有一个节点
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        size--;
        return toRemove.data;
    }
    /**
     * 删除指定索引位置的元素。
     * @param index 要删除元素的索引
     * @return 被删除的元素
     * @throws IndexOutOfBoundsException 如果索引越界
     */
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            return removeFirst();
        } else if (index == size - 1) {
            return removeLast();
        } else {
            Node<T> toRemove = getNodeAtIndex(index);
            // 重新链接前后节点，跳过 toRemove
            toRemove.prev.next = toRemove.next;
            toRemove.next.prev = toRemove.prev;
            size--;
            return toRemove.data;
        }
    }
    /**
     * 获取指定索引位置的元素。
     * @param index 索引
     * @return 索引位置的元素
     * @throws IndexOutOfBoundsException 如果索引越界
     */
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return getNodeAtIndex(index).data;
    }
    /**
     * 更新指定索引位置的元素。
     * @param index   索引
     * @param newData 新的数据
     * @throws IndexOutOfBoundsException 如果索引越界
     */
    public void set(int index, T newData) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        getNodeAtIndex(index).data = newData;
    }
    // ===== 辅助方法 =====
    /**
     * 获取链表的大小（元素数量）。
     * @return 元素数量
     */
    public int size() {
        return size;
    }
    /**
     * 检查链表是否为空。
     * @return 如果链表为空，返回 true；否则返回 false
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 清空链表。
     */
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }
    /**
     * 打印链表内容。
     */
    public void printList() {
        Node<T> current = head;
        System.out.print("List: [");
        while (current != null) {
            System.out.print(current.data);
            if (current.next != null) {
                System.out.print(" -> ");
            }
            current = current.next;
        }
        System.out.println("]");
    }
    /**
     * 根据索引获取 Node 对象（一个辅助方法，避免重复代码）。
     * @param index 索引
     * @return 对应的 Node 对象
     */
    private Node<T> getNodeAtIndex(int index) {
        // 为了提高效率，可以从头或尾开始遍历，选择更近的一端
        Node<T> current;
        if (index < size / 2) {
            // 从头开始遍历
            current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        } else {
            // 从尾开始遍历
            current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
        }
        return current;
    }
    // ===== 主方法：用于测试 =====
    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        System.out.println("初始链表是否为空: " + list.isEmpty());
        list.printList();
        // 添加元素
        System.out.println("\n--- 添加元素 ---");
        list.addFirst(10);
        list.addLast(20);
        list.addLast(30);
        list.add(1, 15); // 在索引1处添加15
        list.printList(); // 预期输出: List: [10 -> 15 -> 20 -> 30]
        System.out.println("当前大小: " + list.size()); // 预期输出: 4
        // 获取和设置元素
        System.out.println("\n--- 获取和设置元素 ---");
        System.out.println("索引 2 的元素是: " + list.get(2)); // 预期输出: 20
        list.set(2, 25);
        System.out.println("将索引 2 的元素修改为 25 后:");
        list.printList(); // 预期输出: List: [10 -> 15 -> 25 -> 30]
        // 删除元素
        System.out.println("\n--- 删除元素 ---");
        list.removeFirst();
        System.out.println("删除第一个元素后:");
        list.printList(); // 预期输出: List: [15 -> 25 -> 30]
        list.removeLast();
        System.out.println("删除最后一个元素后:");
        list.printList(); // 预期输出: List: [15 -> 25]
        list.remove(0);
        System.out.println("删除索引 0 的元素后:");
        list.printList(); // 预期输出: List: [25]
        // 清空链表
        System.out.println("\n--- 清空链表 ---");
        list.clear();
        System.out.println("清空后链表是否为空: " + list.isEmpty());
        list.printList(); // 预期输出: List: []
    }
}

代码解析

`Node` 内部类

这是一个私有的静态内部类。static 意味着 Node 的存在不依赖于外部 MyLinkedList 的实例，它只是一个纯粹的数据结构。
它包含 data, prev, next 三个字段，以及一个简单的构造方法。

`MyLinkedList` 类

属性:
- head, tail: 分别指向链表的头和尾，持有尾指针可以让我们在 addLast() 和 removeLast() 操作时达到 O(1) 的时间复杂度，否则需要遍历整个链表。
- size: 记录链表长度，使得 size() 操作为 O(1)。
核心方法:
- addFirst(data) / addLast(data): 创建新节点，然后根据链表是否为空来处理指针的链接，逻辑清晰直接。
- add(index, data): 先检查索引合法性，如果是在头部或尾部，直接调用 addFirst 或 addLast，如果在中间，则需要先找到 index-1 位置的节点，然后插入新节点并重新链接 next 和 prev 指针。
- removeFirst() / removeLast(): 删除节点后，需要更新 head 或 tail 指针，并处理好边界情况（删除后链表为空）。
- remove(index): 同样先检查索引，删除中间节点时，关键在于让前一个节点的 next 指向后一个节点，同时让后一个节点的 prev 指向前一个节点，从而“绕过”被删除的节点。
- get(index) / set(index, data): 都需要先通过索引找到对应的节点，我们提取了一个辅助方法 getNodeAtIndex(index) 来复用这部分逻辑，并且在 getNodeAtIndex 中做了优化：根据索引位置决定从头还是从尾开始遍历，以减少平均遍历时间。
辅助方法:
- isEmpty(), size(), clear(), printList() 这些方法提供了链表的基本状态信息和调试功能。

与 Java 官方 `LinkedList` 的对比

相似之处：我们实现的 MyLinkedList 与 Java 集合框架中的 java.util.LinkedList 在核心概念（双向链表）和主要方法（add, remove, get, size 等）上非常相似。
不同之处：
- 泛型：官方实现使用了更复杂的泛型写法（如 <E>），但核心思想相同。
- 方法丰富度：官方 LinkedList 还实现了 Deque 和 List 接口，提供了更多方法，如 offer(), poll(), peek() (队列操作)，以及 indexOf(), lastIndexOf() 等。
- 性能：官方实现经过了高度优化和严格测试。
- null 元素：官方 LinkedList 允许存储 null 元素，我们的实现也允许（因为我们没有做特殊限制）。

通过自己动手实现一遍,可以让你对链表的工作原理有更深刻、更直观的理解，这比单纯地使用 API 要有价值得多。

（图片来源网络，侵删）

Java如何实现LinkedList？核心步骤是什么？

理解链表结构

实现步骤

完整代码实现

代码解析

`Node` 内部类

`MyLinkedList` 类

与 Java 官方 `LinkedList` 的对比

99ANYc3cd6

Python jieba库具体怎么用？

matlab2025b安装教程

Mac下Python运行报错怎么办？

atom python运行python环境如何配置？

Mastercam X6安装步骤详解，附常见问题解答？

androidkiller安装教程

Python simpleserver如何快速搭建本地服务？

Python中verbose=False如何生效？

Java long转integer会丢失精度吗？

iPhone6外屏玻璃自己换难不难？

Java POI如何高效读取Excel文件？

python startproject

Python readlines 读取GBK文件乱码怎么办？

ASP.NET MVC 4教程，从入门到实践如何快速掌握？

Python2与Python3如何兼容共存？

Java转字符串数组如何实现？

Java如何实现LinkedList？核心步骤是什么？

理解链表结构

实现步骤

完整代码实现

代码解析

Node 内部类

MyLinkedList 类

与 Java 官方 LinkedList 的对比

相关推荐

androidkiller安装教程

`Node` 内部类

`MyLinkedList` 类

与 Java 官方 `LinkedList` 的对比