单链表的基本原理与实现

发布于：2025-09-03 ⋅ 阅读:(16) ⋅ 点赞:(0)

什么是单链表

单链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用。与数组的连续存储不同，单链表的节点可分散在内存中，通过指针连接形成链式结构。以下是单链表节点的典型定义：

Java 示例：

/**
 * 单链表节点定义
 * @param <E> 节点数据类型
 */
public class ListNode<E> {
    /** 节点存储的数据 */
    E data;
    /** 指向下一个节点的引用 */
    ListNode<E> next;
    
    /**
     * 构造函数
     * @param data 节点数据
     */
    public ListNode(E data) {
        this.data = data;
        this.next = null;
    }
    
    /**
     * 带后继节点的构造函数
     * @param data 节点数据
     * @param next 后继节点
     */
    public ListNode(E data, ListNode<E> next) {
        this.data = data;
        this.next = next;
    }
}

C# 示例：

/// <summary>
/// 单链表节点定义
/// </summary>
/// <typeparam name="T">节点数据类型</typeparam>
public class ListNode<T>
{
    /// <summary>
    /// 节点存储的数据
    /// </summary>
    public T Data { get; set; }
    
    /// <summary>
    /// 指向下一个节点的引用
    /// </summary>
    public ListNode<T> Next { get; set; }
    
    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="data">节点数据</param>
    public ListNode(T data)
    {
        Data = data;
        Next = null;
    }
    
    /// <summary>
    /// 带后继节点的构造函数
    /// </summary>
    /// <param name="data">节点数据</param>
    /// <param name="next">后继节点</param>
    public ListNode(T data, ListNode<T> next)
    {
        Data = data;
        Next = next;
    }
}

链表的优势与局限性

优势：

  1. 内存利用效率高：节点无需连续存储，可动态分配，适应零散内存。

  2. 无需扩缩容：增删节点只需调整指针，无需数据搬移，理论上容量无限。

局限性：

  • 不支持随机访问：访问第 n 个节点需从头遍历，时间复杂度为 O(n)。

相比之下，数组通过连续内存实现 O(1) 的随机访问，但增删操作可能触发数据搬移和扩缩容（O(n)）。

单链表的基本操作

首先实现创建链表的辅助方法，便于后续操作演示：

Java 示例：

/**
 * 根据数组创建单链表
 * @param array 源数据数组
 * @param <T> 数据类型
 * @return 链表头节点
 */
public static <T> ListNode<T> createLinkedList(T[] array) {
    if (array == null || array.length == 0) {
        return null;
    }
    
    ListNode<T> head = new ListNode<>(array[0]);
    ListNode<T> current = head;
    
    for (int i = 1; i < array.length; i++) {
        current.next = new ListNode<>(array[i]);
        current = current.next;
    }
    
    return head;
}

C# 示例：

/// <summary>
/// 根据数组创建单链表
/// </summary>
/// <typeparam name="T">数据类型</typeparam>
/// <param name="array">源数据数组</param>
/// <returns>链表头节点</returns>
public static ListNode<T> CreateLinkedList<T>(T[] array)
{
    if (array == null || array.Length == 0)
    {
        return null;
    }
    
    var head = new ListNode<T>(array[0]);
    var current = head;
    
    for (int i = 1; i < array.Length; i++)
    {
        current.Next = new ListNode<T>(array[i]);
        current = current.Next;
    }
    
    return head;
}

查与改

遍历与查找

遍历单链表需从头节点开始，沿 next 指针访问：

Java 示例：

ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
for (ListNode p = head; p != null; p = p.next) {
    System.out.println(p.val);
}

C# 示例：

ListNode head = CreateLinkedList(new int[]{1, 2, 3, 4, 5});
for (ListNode p = head; p != null; p = p.next) {
    Console.WriteLine(p.val);
}

查找或修改特定索引的节点需从头遍历，时间复杂度为 O(n)。

增

头部插入

将新节点插入链表头部，更新头指针：

Java 示例：

ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode newNode = new ListNode(0);
newNode.next = head;
head = newNode; // 链表变为 0 -> 1 -> 2 -> 3 -> 4 -> 5

C# 示例：

ListNode head = CreateLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode newNode = new ListNode(0);
newNode.next = head;
head = newNode; // 链表变为 0 -> 1 -> 2 -> 3 -> 4 -> 5

时间复杂度：O(1)。

尾部插入
遍历至尾节点，添加新节点：

Java 示例：

ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
while (p.next != null) {
    p = p.next;
}
p.next = new ListNode(6); // 链表变为 1 -> 2 -> 3 -> 4 -> 5 -> 6

C# 示例：

ListNode head = CreateLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
while (p.next != null) {
    p = p.next;
}
p.next = new ListNode(6); // 链表变为 1 -> 2 -> 3 -> 4 -> 5 -> 6

时间复杂度：O(n)，因需遍历。若持有尾节点引用，可优化为 O(1)。

中间插入

在第 k 个节点后插入，需找到前驱节点：

Java 示例：

ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next; // 定位第 3 个节点
}
ListNode newNode = new ListNode(6);
newNode.next = p.next;
p.next = newNode; // 链表变为 1 -> 2 -> 3 -> 6 -> 4 -> 5

C# 示例：

ListNode head = CreateLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next; // 定位第 3 个节点
}
ListNode newNode = new ListNode(6);
newNode.next = p.next;
p.next = newNode; // 链表变为 1 -> 2 -> 3 -> 6 -> 4 -> 5

时间复杂度：O(n)，因需遍历至前驱节点。

删

头部删除

将头指针移至下一节点：

Java 示例：

ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
head = head.next; // 链表变为 2 -> 3 -> 4 -> 5

C# 示例：

ListNode head = CreateLinkedList(new int[]{1, 2, 3, 4, 5});
head = head.next; // 链表变为 2 -> 3 -> 4 -> 5

时间复杂度：O(1)。在 Java 和 C# 中，旧头节点无引用后会被垃圾回收，无需显式置空 next。

尾部删除

找到倒数第二个节点，置其 next 为 null：

Java 示例：

ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
while (p.next.next != null) {
    p = p.next;
}
p.next = null; // 链表变为 1 -> 2 -> 3 -> 4

C# 示例：

ListNode head = CreateLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
while (p.next.next != null) {
    p = p.next;
}
p.next = null; // 链表变为 1 -> 2 -> 3 -> 4

时间复杂度：O(n)。

中间删除

删除第 k 个节点，需调整前驱节点的指针：

Java 示例：

ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next; // 定位第 3 个节点
}
p.next = p.next.next; // 链表变为 1 -> 2 -> 3 -> 5

C# 示例：

ListNode head = CreateLinkedList(new int[]{1, 2, 3, 4, 5});
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next; // 定位第 3 个节点
}
p.next = p.next.next; // 链表变为 1 -> 2 -> 3 -> 5

时间复杂度：O(n)。

小结

单链表的增删查改操作比数组复杂，因节点非连续存储，需遍历定位前驱或后驱节点。不同位置（头部、尾部、中间）的操作逻辑各异，且需考虑边界情况（如空链表）。

后续章节将介绍双向链表和“虚拟头节点”技巧，以统一操作并简化边界处理。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布