什么是Java单链表

单链表(Linked List)是一种常见的基础数据结构，它由一系列节点(Node)组成，每个节点包含两个部分：数据域(data)和指针域(next)。在Java中，单链表通常通过自定义类来实现，相比数组，它具有动态内存分配的优势。

单链表的基本特点

  1. 动态大小：不需要预先指定大小，可以动态增长和缩减
  2. 内存效率：只在需要时分配内存，避免内存浪费
  3. 插入删除高效：时间复杂度为O(1)，前提是知道操作位置
  4. 随机访问低效：访问特定元素需要从头遍历，时间复杂度为O(n)

Java单链表的基本实现

节点类定义

```java
public class ListNode {
int val; // 数据域
ListNode next; // 指针域

Java单链表：从基础实现到高级应用全解析

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

}


### 单链表类框架

```java
public class SinglyLinkedList {
    private ListNode head;  // 头节点

    public SinglyLinkedList() {
        this.head = null;
    }

    // 各种操作方法将在下面实现
}

Java单链表的常用操作

插入操作

头部插入

public void insertAtHead(int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head;
    head = newNode;
}

尾部插入

public void insertAtTail(int val) {
    ListNode newNode = new ListNode(val);
    if (head == null) {
        head = newNode;
        return;
    }

    ListNode current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
}

指定位置插入

public void insertAtIndex(int index, int val) {
    if (index < 0) {
        throw new IllegalArgumentException("索引不能为负数");
    }

    if (index == 0) {
        insertAtHead(val);
        return;
    }

    ListNode newNode = new ListNode(val);
    ListNode current = head;
    for (int i = 0; i < index - 1 && current != null; i++) {
        current = current.next;
    }

    if (current == null) {
        throw new IndexOutOfBoundsException("索引超出链表长度");
    }

    newNode.next = current.next;
    current.next = newNode;
}

删除操作

删除头节点

public void deleteAtHead() {
    if (head == null) {
        return;
    }
    head = head.next;
}

删除尾节点

public void deleteAtTail() {
    if (head == null || head.next == null) {
        head = null;
        return;
    }

    ListNode current = head;
    while (current.next.next != null) {
        current = current.next;
    }
    current.next = null;
}

删除指定值节点

public void deleteValue(int val) {
    if (head == null) {
        return;
    }

    if (head.val == val) {
        head = head.next;
        return;
    }

    ListNode current = head;
    while (current.next != null && current.next.val != val) {
        current = current.next;
    }

    if (current.next != null) {
        current.next = current.next.next;
    }
}

Java单链表的高级应用

链表反转

public void reverse() {
    ListNode prev = null;
    ListNode current = head;
    ListNode next = null;

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

    head = prev;
}

检测环

public boolean hasCycle() {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode slow = head;
    ListNode fast = head.next;

    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }

    return true;
}

合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    current.next = (l1 != null) ? l1 : l2;

    return dummy.next;
}

Java单链表的性能优化

使用虚拟头节点(Dummy Node)

在处理链表问题时，使用虚拟头节点可以简化边界条件处理：

public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode current = dummy;

    while (current.next != null) {
        if (current.next.val == val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }

    return dummy.next;
}

快慢指针技巧

快慢指针是解决链表问题的强大工具，常用于：

Java单链表：从基础实现到高级应用全解析

  1. 找到链表的中间节点
  2. 检测链表是否有环
  3. 找到环的入口点
public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

Java单链表在实际项目中的应用

实现LRU缓存

单链表可以用于实现简单的LRU(最近最少使用)缓存算法：

public class LRUCache {
    private final int capacity;
    private final Map<Integer, ListNode> map;
    private final ListNode dummyHead;
    private final ListNode dummyTail;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.dummyHead = new ListNode(-1);
        this.dummyTail = new ListNode(-1);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        this.size = 0;
    }

    // 其他方法实现...
}

浏览器历史记录

单链表适合模拟浏览器的前进后退功能：

public class BrowserHistory {
    private ListNode current;

    public BrowserHistory(String homepage) {
        current = new ListNode(homepage);
    }

    public void visit(String url) {
        ListNode newNode = new ListNode(url);
        current.next = newNode;
        newNode.prev = current;
        current = newNode;
    }

    public String back(int steps) {
        while (steps-- > 0 && current.prev != null) {
            current = current.prev;
        }
        return current.val;
    }

    public String forward(int steps) {
        while (steps-- > 0 && current.next != null) {
            current = current.next;
        }
        return current.val;
    }
}

Java单链表的常见面试题

  1. 反转链表：如何高效地反转一个单链表？
  2. 环检测：如何判断链表是否有环？如果有，如何找到环的入口？
  3. 相交链表：如何找到两个单链表相交的起始节点？
  4. 删除倒数第N个节点：如何一次遍历删除链表的倒数第N个节点？
  5. 排序链表：如何在O(nlogn)时间复杂度和常数级空间复杂度下对链表进行排序？

掌握这些问题的解法，能够帮助你在技术面试中游刃有余地应对链表相关问题。

Java单链表：从基础实现到高级应用全解析

总结

Java单链表作为一种基础数据结构，在算法和实际应用中都有广泛使用。通过本文的学习，你应该已经掌握了单链表的基本实现、常用操作、高级应用以及性能优化技巧。在实际开发中，根据具体需求选择合适的链表变体（如双向链表、循环链表等）可以进一步提高程序效率。

记住，理解数据结构的核心在于实践。建议你动手实现本文中的代码示例，并尝试解决一些LeetCode上的链表相关问题，这将帮助你更深入地掌握Java单链表的精髓。

《Java单链表：从基础实现到高级应用全解析》.doc
将本文下载保存，方便收藏和打印
下载文档