Java链表实现详解：单链表、双链表与循环链表的完整指南

admin 2025-06-26 阅读:14 评论:0

在Java编程中，链表是最基础也是最重要的数据结构之一。与数组不同，链表通过节点之间的引用来实现元素的存储，这种动态数据结构在内存利用和操作效率上具有独特优势。本文将全面解析Java中链表的实现方式，涵盖单链表、双链表和循环链表等多种形式，...

在Java编程中，链表是最基础也是最重要的数据结构之一。与数组不同，链表通过节点之间的引用来实现元素的存储，这种动态数据结构在内存利用和操作效率上具有独特优势。本文将全面解析Java中链表的实现方式，涵盖单链表、双链表和循环链表等多种形式，并深入探讨其在实际开发中的应用场景。

一、链表的基本概念与优势

链表是由一系列节点组成的数据结构，每个节点包含数据域和指针域。与数组相比，链表的主要优势在于：
1. 动态大小：无需预先知道数据规模
2. 高效插入/删除：时间复杂度为O(1)
3. 内存利用率高：按需分配内存空间

二、单链表的Java实现

单链表是最简单的链表形式，我们首先定义节点类：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

然后实现单链表的基本操作：

Java链表实现详解：单链表、双链表与循环链表的完整指南

class SinglyLinkedList {
    private ListNode head;

    // 插入操作
    public void insert(int data) {
        ListNode newNode = new ListNode(data);
        if(head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while(current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 删除操作
    public void delete(int key) {
        ListNode current = head;
        ListNode prev = null;

        while(current != null && current.val != key) {
            prev = current;
            current = current.next;
        }

        if(current == null) return;

        if(prev == null) {
            head = head.next;
        } else {
            prev.next = current.next;
        }
    }
}

三、双链表的实现与优化

双链表在单链表基础上增加了前驱指针，使得双向遍历成为可能：

Java链表实现详解：单链表、双链表与循环链表的完整指南

class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;

    DoublyListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode tail;

    // 头部插入
    public void insertAtHead(int data) {
        DoublyListNode newNode = new DoublyListNode(data);
        if(head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // 删除特定节点
    public void deleteNode(DoublyListNode node) {
        if(node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }

        if(node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }
}

四、循环链表的特殊应用

循环链表将尾节点指向头节点，形成环形结构，特别适合需要循环访问的场景：

class CircularLinkedList {
    private ListNode last;

    // 插入到空链表
    public void insertToEmpty(int data) {
        ListNode newNode = new ListNode(data);
        last = newNode;
        newNode.next = newNode; // 指向自身形成环
    }

    // 在末尾插入
    public void insertAtEnd(int data) {
        if(last == null) {
            insertToEmpty(data);
            return;
        }

        ListNode newNode = new ListNode(data);
        newNode.next = last.next;
        last.next = newNode;
        last = newNode;
    }
}

五、链表与集合框架

Java集合框架中的LinkedList类就是双链表的实现，它实现了List和Deque接口。我们可以分析其部分源码：

// JDK中的LinkedList节点定义
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;
    }
}