C#进阶学习（五）单向链表和双向链表，循环链表（中）双向链表

发布于：2025-04-18 ⋅ 阅读:(28) ⋅ 点赞:(0)

     

目录

一、双向链表的声明

1. 节点类声明

 2. 链表类框架声明

3、实现其中的每一个函数 

增删操作（核心方法组）

删除操作（核心方法组）

查询操作（辅助方法）

维护方法（内部逻辑）

二、测试：

三、C#中的双向链表

复杂度对比表

  有了前面实现单链表的基础，那么今天的我们实现双向链表简直就是简简单单，请往下看。

一、双向链表的声明

1. 节点类声明

/// <summary>
/// 双向链表节点类（核心数据结构）
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class DoublyLinkedListNode<T>
{
    // 节点存储的实际数据
    public T Value { get; set; }

    // 前驱节点指针（关键特性）
    public DoublyLinkedListNode<T> Previous { get; set; }

    // 后继节点指针（关键特性）
    public DoublyLinkedListNode<T> Next { get; set; }

    /// <summary>
    /// 构造函数（初始化数据域）
    /// </summary>
    public DoublyLinkedListNode(T value)
    {
        Value = value;
        Previous = null;  // 初始化前驱指针
        Next = null;     // 初始化后继指针
    }
}

关键特性说明：

        双指针结构：同时维护Previous和Next指针，实现双向遍历

        泛型设计：支持任意数据类型存储

        独立节点：每个节点独立管理前后连接关系

 2. 链表类框架声明

/// <summary>
/// 双向链表容器类（核心操作实现）
/// </summary>
public class DoublyLinkedList<T>
{
    // 头尾指针（核心成员）
    private DoublyLinkedListNode<T> _head;
    private DoublyLinkedListNode<T> _tail;
    
    // 计数器（重要属性）
    public int Count { get; private set; }
    public bool IsEmpty => Count == 0;

    // 索引器（特色功能）
    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= Count)
                throw new IndexOutOfRangeException();
            
            var current = _head;
            for (int i = 0; i < index; i++)
                current = current.Next;
            
            return current.Value;
        }
    }

    // 增删操作（核心方法组）
    public void AddFirst(T value) { /* 实现略 */ }
    public void AddLast(T value) { /* 实现略 */ }
    public void InsertAt(int index, T value) { /* 实现略 */ }
    
    // 删除操作（核心方法组）
    public bool Remove(T value) { /* 实现略 */ }
    public void RemoveAt(int index) { /* 实现略 */ }
    public void RemoveFirst() { /* 实现略 */ }
    public void RemoveLast() { /* 实现略 */ }

    // 查询操作（辅助方法）
    public bool Contains(T value) { /* 实现略 */ }
    public int Find(T value) { /* 实现略 */ }

    // 维护方法（内部逻辑）
    private DoublyLinkedListNode<T> GetNodeAt(int index) { /* 实现略 */ }
    private void RemoveNode(DoublyLinkedListNode<T> node) { /* 实现略 */ }
}

3、实现其中的每一个函数 

增删操作（核心方法组）

（1）public void AddFirst(T value)

/// <summary>
/// 添加元素到链表头部
/// </summary>
/// <param name="value">要添加的数据</param>
public void AddFirst(T value)
{
    DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<T>(value);

    if (IsEmpty)
    {
        _head = _tail = newNode;
    }
    else
    {
        newNode.Next = _head;
        _head.Previous = newNode;
        _head = newNode;
    }
    Count++;
}

（2）public void AddLast(T value)

/// <summary>
/// 添加元素到链表尾部
/// </summary>
/// <param name="value">要添加的数据</param>
public void AddLast(T value)
{
    DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<T>(value);

    if (IsEmpty)
    {
        _head = _tail = newNode;
    }
    else
    {
        _tail.Next = newNode;
        newNode.Previous = _tail;
        _tail = newNode;
    }
    Count++;
}

（3）public void InsertAt(int index, T value)

/// <summary>
/// 在指定位置插入元素
/// </summary>
/// <param name="index">插入位置索引</param>
/// <param name="value">要插入的数据</param>
/// <exception cref="ArgumentOutOfRangeException">索引越界异常</exception>
public void InsertAt(int index, T value)
{
    if (index < 0 || index > Count)
        throw new ArgumentOutOfRangeException(nameof(index));

    if (index == 0)
    {
        AddFirst(value);
    }
    else if (index == Count)
    {
        AddLast(value);
    }
    else
    {
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<T>(value);
        DoublyLinkedListNode<T> current = GetNodeAt(index);

        newNode.Previous = current.Previous;
        newNode.Next = current;
        current.Previous.Next = newNode;
        current.Previous = newNode;

        Count++;
    }
}

删除操作（核心方法组）

（4）public bool Remove(T value)

/// <summary>
/// 删除第一个匹配的元素
/// </summary>
/// <param name="value">要删除的数据</param>
/// <returns>是否删除成功</returns>
public bool Remove(T value)
{
    DoublyLinkedListNode<T> current = _head;

    while (current != null)
    {
        if (EqualityComparer<T>.Default.Equals(current.Value, value))
        { 
    // 当T是int时：执行值比较（无需装箱）
    // 当T是string时：执行值内容比较
    // 当T是自定义类：优先使用IEquatable实现
    // 自动处理null值情况（current.Value或value为null时不会报错）
    //这里的if里面就相当于是一种更加安全的判断数据是否相等，不管是地址还是内容
            RemoveNode(current);
            return true;
        }
        current = current.Next;
    }
    return false;
}

这里的RemoveNode在下面哦 

（5）public void RemoveAt(int index)

/// <summary>
/// 删除指定位置的元素
/// </summary>
/// <param name="index">要删除的位置索引</param>
/// <exception cref="ArgumentOutOfRangeException">索引越界异常</exception>
public void RemoveAt(int index)
{
    if (index < 0 || index >= Count)
        throw new ArgumentOutOfRangeException(nameof(index));

    DoublyLinkedListNode<T> nodeToRemove = GetNodeAt(index);
    RemoveNode(nodeToRemove);
}

（6）public void RemoveFirst()

/// <summary>
/// 删除头节点
/// </summary>
/// <exception cref="InvalidOperationException">空链表异常</exception>
public void RemoveFirst()
{
    if (IsEmpty)
        throw new InvalidOperationException("链表为空");

    RemoveNode(_head);
}

（7）public void RemoveLast()

/// <summary>
/// 删除尾节点
/// </summary>
/// <exception cref="InvalidOperationException">空链表异常</exception>
public void RemoveLast()
{
    if (IsEmpty)
        throw new InvalidOperationException("链表为空");

    RemoveNode(_tail);
}

查询操作（辅助方法）

（8）public bool Contains(T value)

/// <summary>
/// 查找元素是否存在
/// </summary>
/// <param name="value">要查找的数据</param>
/// <returns>是否存在</returns>
public bool Contains(T value)
{
    return Find(value) != -1;
}

（9）public int Find(T value)

/// <summary>
/// 查找元素位置
/// </summary>
/// <param name="value">要查找的数据</param>
/// <returns>元素索引（未找到返回-1）</returns>
public int Find(T value)
{
    DoublyLinkedListNode<T> current = _head;
    int index = 0;

    while (current != null)
    {
        if (EqualityComparer<T>.Default.Equals(current.Value, value))
        {
            return index;
        }
        current = current.Next;
        index++;
    }
    return -1;
}

维护方法（内部逻辑）

（10） private DoublyLinkedListNode<T> GetNodeAt(int index)

// 私有辅助方法
private DoublyLinkedListNode<T> GetNodeAt(int index)
{
    if (index < 0 || index >= Count)
        throw new ArgumentOutOfRangeException(nameof(index));

    DoublyLinkedListNode<T> current = _head;
    for (int i = 0; i < index; i++)
    {
        current = current.Next;
    }
    return current;
}

（11） private void RemoveNode(DoublyLinkedListNode<T> node)

private void RemoveNode(DoublyLinkedListNode<T> nodeToRemove)
{
    if (nodeToRemove.Previous != null)
    {
        nodeToRemove.Previous.Next = nodeToRemove.Next;
    }
    else
    {
        _head = nodeToRemove.Next;
    }

    if (nodeToRemove.Next != null)
    {
        nodeToRemove.Next.Previous = nodeToRemove.Previous;
    }
    else
    {
        _tail = nodeToRemove.Previous;
    }

    Count--;
}

二、测试：

class Program
{
    static void Main(string[] args)
    {
        DoublyLinkedList<int> list = new DoublyLinkedList<int>();

        // 添加测试
        list.AddLast(1);
        list.AddFirst(0);
        list.InsertAt(2, 2);
        list.AddLast(3);

        Console.WriteLine("正向遍历：");
        list.PrintForward();  // 0 -> 1 -> 2 -> 3 -> null

        Console.WriteLine("\n反向遍历：");
        list.PrintBackward(); // 3 -> 2 -> 1 -> 0 -> null

        // 查找测试
        Console.WriteLine($"\n元素2的位置：{list.Find(2)}"); // 2
        Console.WriteLine($"是否存在元素5：{list.Contains(5)}"); // False

        // 修改测试
        list.Remove(2);
        list.RemoveAt(0);
        Console.WriteLine("\n删除元素2和头节点后的链表：");
        list.PrintForward(); // 1 -> 3 -> null

        // 清空测试
        list.Clear();
        Console.WriteLine($"\n清空后链表长度：{list.Count}"); // 0
    }
}

测试结果：

三、C#中的双向链表

        其实我们大可不必自己苦哈哈的实现双向链表，C#中已经给我们封装好了这样的一个类，下面一起来看看吧。

官方实现：System.Collections.Generic.LinkedList<T>

        1. 节点类：LinkedListNode<T>：

类名 类型 名称 描述
LinkedListNode<T> 属性 List 获取节点所属的LinkedList<T>对象
属性 Value 获取或设置节点存储的值
属性 Next 获取下一个节点（尾节点时返回null）
属性 Previous 获取上一个节点（头节点时返回null）
构造函数 new(T value) 创建独立节点（未关联到链表时使用）

        2. 链表类：LinkedList<T> 

类名 类型 名称 描述
LinkedList<T> 属性 Count 获取链表中实际包含的节点数量
属性 First 获取链表的第一个节点（头节点）
属性 Last 获取链表的最后一个节点（尾节点）
方法 AddFirst(T value) 在链表头部添加包含指定值的新节点
方法 AddFirst(LinkedListNode<T>) 将现有节点添加到链表头部
方法 AddLast(T value) 在链表尾部添加包含指定值的新节点
方法 AddLast(LinkedListNode<T>) 将现有节点添加到链表尾部
方法 AddAfter(LinkedListNode<T>, T) 在指定节点之后插入包含值的新节点
方法 AddBefore(LinkedListNode<T>, T) 在指定节点之前插入包含值的新节点
方法 Remove(T value) 删除第一个匹配值的节点（返回bool）
方法 Remove(LinkedListNode<T>) 删除指定节点（O(1)操作）
方法 RemoveFirst() 删除头节点
方法 RemoveLast() 删除尾节点
方法 Find(T value) 从头部开始查找第一个匹配值的节点（返回LinkedListNode<T>或null）
方法 Contains(T value) 判断链表是否包含指定值
方法 Clear() 清空所有节点

复杂度对比表

操作 时间复杂度 说明
AddFirst/AddLast O(1) 头尾指针直接操作
AddAfter/AddBefore O(1) 已知节点时的指针修改
Remove(节点) O(1) 直接修改相邻节点指针
Remove(值) O(n) 需要遍历查找
Find O(n) 最差情况需遍历整个链表
Contains O(n) 依赖Find实现

好的 那么双向链表的实现就到此了，接着我们回去看看循环链表。

附本文实现的双向链表：

using System;

/// <summary>
/// 双向链表节点类
/// </summary>
/// <typeparam name="T">节点数据类型</typeparam>
public class DoublyLinkedListNode<T>
{
    /// <summary>
    /// 节点数据值
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 前驱节点指针
    /// </summary>
    public DoublyLinkedListNode<T>? Previous { get; set; }

    /// <summary>
    /// 后继节点指针
    /// </summary>
    public DoublyLinkedListNode<T>? Next { get; set; }

    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="value">节点数据</param>
    public DoublyLinkedListNode(T value)
    {
        Value = value;
        Previous = null;
        Next = null;
    }
}

/// <summary>
/// 双向链表类
/// </summary>
/// <typeparam name="T">链表数据类型</typeparam>
public class DoublyLinkedList<T>
{
    /// <summary>
    /// 头节点
    /// </summary>
    private DoublyLinkedListNode<T>? _head;

    /// <summary>
    /// 尾节点
    /// </summary>
    private DoublyLinkedListNode<T>? _tail;

    /// <summary>
    /// 链表长度
    /// </summary>
    public int Count { get; private set; }

    /// <summary>
    /// 判断链表是否为空
    /// </summary>
    public bool IsEmpty => Count == 0;

    /// <summary>
    /// 索引器：通过索引访问元素
    /// </summary>
    /// <param name="index">元素位置</param>
    /// <returns>节点数据</returns>
    /// <exception cref="ArgumentOutOfRangeException">索引越界异常</exception>
    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= Count)
                throw new ArgumentOutOfRangeException(nameof(index));

            DoublyLinkedListNode<T>? current = _head;
            for (int i = 0; i < index; i++)
            {
                current = current.Next;
            }
            return current.Value;
        }
    }

    /// <summary>
    /// 添加元素到链表头部
    /// </summary>
    /// <param name="value">要添加的数据</param>
    public void AddFirst(T value)
    {
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<T>(value);

        if (IsEmpty)
        {
            _head = _tail = newNode;
        }
        else
        {
            newNode.Next = _head;
            _head.Previous = newNode;
            _head = newNode;
        }
        Count++;
    }

    /// <summary>
    /// 添加元素到链表尾部
    /// </summary>
    /// <param name="value">要添加的数据</param>
    public void AddLast(T value)
    {
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<T>(value);

        if (IsEmpty)
        {
            _head = _tail = newNode;
        }
        else
        {
            _tail.Next = newNode;
            newNode.Previous = _tail;
            _tail = newNode;
        }
        Count++;
    }

    /// <summary>
    /// 在指定位置插入元素
    /// </summary>
    /// <param name="index">插入位置索引</param>
    /// <param name="value">要插入的数据</param>
    /// <exception cref="ArgumentOutOfRangeException">索引越界异常</exception>
    public void InsertAt(int index, T value)
    {
        if (index < 0 || index > Count)
            throw new ArgumentOutOfRangeException(nameof(index));

        if (index == 0)
        {
            AddFirst(value);
        }
        else if (index == Count)
        {
            AddLast(value);
        }
        else
        {
            DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<T>(value);
            DoublyLinkedListNode<T> current = GetNodeAt(index);

            newNode.Previous = current.Previous;
            newNode.Next = current;
            current.Previous.Next = newNode;
            current.Previous = newNode;

            Count++;
        }
    }

    /// <summary>
    /// 删除第一个匹配的元素
    /// </summary>
    /// <param name="value">要删除的数据</param>
    /// <returns>是否删除成功</returns>
    public bool Remove(T value)
    {
        DoublyLinkedListNode<T> current = _head;

        while (current != null)
        {
            if (EqualityComparer<T>.Default.Equals(current.Value, value))
            {
                RemoveNode(current);
                return true;
            }
            current = current.Next;
        }
        return false;
    }

    /// <summary>
    /// 删除指定位置的元素
    /// </summary>
    /// <param name="index">要删除的位置索引</param>
    /// <exception cref="ArgumentOutOfRangeException">索引越界异常</exception>
    public void RemoveAt(int index)
    {
        if (index < 0 || index >= Count)
            throw new ArgumentOutOfRangeException(nameof(index));

        DoublyLinkedListNode<T> nodeToRemove = GetNodeAt(index);
        RemoveNode(nodeToRemove);
    }

    /// <summary>
    /// 删除头节点
    /// </summary>
    /// <exception cref="InvalidOperationException">空链表异常</exception>
    public void RemoveFirst()
    {
        if (IsEmpty)
            throw new InvalidOperationException("链表为空");

        RemoveNode(_head);
    }

    /// <summary>
    /// 删除尾节点
    /// </summary>
    /// <exception cref="InvalidOperationException">空链表异常</exception>
    public void RemoveLast()
    {
        if (IsEmpty)
            throw new InvalidOperationException("链表为空");

        RemoveNode(_tail);
    }

    /// <summary>
    /// 查找元素是否存在
    /// </summary>
    /// <param name="value">要查找的数据</param>
    /// <returns>是否存在</returns>
    public bool Contains(T value)
    {
        return Find(value) != -1;
    }

    /// <summary>
    /// 查找元素位置
    /// </summary>
    /// <param name="value">要查找的数据</param>
    /// <returns>元素索引（未找到返回-1）</returns>
    public int Find(T value)
    {
        DoublyLinkedListNode<T> current = _head;
        int index = 0;

        while (current != null)
        {
            if (EqualityComparer<T>.Default.Equals(current.Value, value))
            {
                return index;
            }
            current = current.Next;
            index++;
        }
        return -1;
    }

    /// <summary>
    /// 清空链表
    /// </summary>
    public void Clear()
    {
        _head = null;
        _tail = null;
        Count = 0;
    }

    /// <summary>
    /// 遍历打印链表（正向）
    /// </summary>
    public void PrintForward()
    {
        DoublyLinkedListNode<T> current = _head;
        while (current != null)
        {
            Console.Write($"{current.Value} -> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }

    /// <summary>
    /// 遍历打印链表（反向）
    /// </summary>
    public void PrintBackward()
    {
        DoublyLinkedListNode<T> current = _tail;
        while (current != null)
        {
            Console.Write($"{current.Value} -> ");
            current = current.Previous;
        }
        Console.WriteLine("null");
    }

    // 私有辅助方法
    private DoublyLinkedListNode<T> GetNodeAt(int index)
    {
        if (index < 0 || index >= Count)
            throw new ArgumentOutOfRangeException(nameof(index));

        DoublyLinkedListNode<T> current = _head;
        for (int i = 0; i < index; i++)
        {
            current = current.Next;
        }
        return current;
    }

    private void RemoveNode(DoublyLinkedListNode<T> nodeToRemove)
    {
        if (nodeToRemove.Previous != null)
        {
            nodeToRemove.Previous.Next = nodeToRemove.Next;
        }
        else
        {
            _head = nodeToRemove.Next;
        }

        if (nodeToRemove.Next != null)
        {
            nodeToRemove.Next.Previous = nodeToRemove.Previous;
        }
        else
        {
            _tail = nodeToRemove.Previous;
        }

        Count--;
    }
}

// 示例使用
class Program
{
    static void Main(string[] args)
    {
        DoublyLinkedList<int> list = new DoublyLinkedList<int>();

        // 添加测试
        list.AddLast(1);
        list.AddFirst(0);
        list.InsertAt(2, 2);
        list.AddLast(3);

        Console.WriteLine("正向遍历：");
        list.PrintForward();  // 0 -> 1 -> 2 -> 3 -> null

        Console.WriteLine("\n反向遍历：");
        list.PrintBackward(); // 3 -> 2 -> 1 -> 0 -> null

        // 查找测试
        Console.WriteLine($"\n元素2的位置：{list.Find(2)}"); // 2
        Console.WriteLine($"是否存在元素5：{list.Contains(5)}"); // False

        // 修改测试
        list.Remove(2);
        list.RemoveAt(0);
        Console.WriteLine("\n删除元素2和头节点后的链表：");
        list.PrintForward(); // 1 -> 3 -> null

        // 清空测试
        list.Clear();
        Console.WriteLine($"\n清空后链表长度：{list.Count}"); // 0
    }
}

 

 

网站公告

今日签到

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

热门文章

最新发布