C#基于LinkedList实现自定义Dictionary泛型类

设计思路与目标

标准的 System.Collections.Generic.Dictionary 基于哈希表实现，查找速度快但不保证顺序且 Key 必须唯一。本实例旨在创建一个名为 MyDictionary<TKey, TValue> 的自定义类，具备以下特性：

• 底层结构：采用双向链表 (LinkedList) 存储 KeyValuePair，保留插入顺序（除非显式排序）。
• 基本操作：支持增加、修改、删除键值对，并处理重复主键异常。
• 便捷访问：实现索引器 (Indexer)，允许通过 [key] 语法获取 Value。
• 数据导出：可将内部链表转换为 List，并支持正常顺序、按键值升序或降序输出。

准备工作

创建一个新的 C# 控制台应用程序或类库项目。确保项目中包含对 System.Collections.Generic 和 System.Linq 的引用（虽然本示例主要使用核心 LINQ 方法和基础集合类，但现代开发中建议保持标准引入）。

代码实现步骤

第1步：定义泛型类与内部变量

首先定义类的骨架，声明用于存储数据的 LinkedList 实例。该类接受两个泛型参数：TKey（键类型）和 TValue（值类型）。

class MyDictioinary<TKey, TValue>
{
    // 内部使用双向链表存储键值对
    LinkedList<KeyValuePair<TKey, TValue>> llDictionary
        = new LinkedList<KeyValuePair<TKey, TValue>>();
    
    // ... 后续方法将在此处添加
}

第2步：实现索引器访问

为了让类的使用方式更像原生字典，需要重载索引器。遍历链表查找匹配的 Key，若找到则返回对应的 Value；若未找到则返回默认值。

public TValue this[TKey tk]
{
    get
    {
        foreach(KeyValuePair<TKey, TValue> kvp in llDictionary)
        {
            if (tk.Equals(kvp.Key))
            {
                return kvp.Value;
            }
        }
        return default(TValue);
    }
}

第3步：实现增删改逻辑

增加 (Add)： 检查 Key 是否已存在，若存在抛出异常以保证 Key 的唯一性，否则追加至链表尾部。

public void Add(TKey tk, TValue tv)
{
    foreach (KeyValuePair<TKey, TValue> kvp in llDictionary)
    {
        if (tk.Equals(kvp.Key))
        {
            throw new Exception("新增失败：主键已经存在");
        }
    }
    llDictionary.AddLast(new KeyValuePair<TKey, TValue>(tk, tv));
}

删除 (Delete)： 遍历寻找匹配的节点，移除后返回；若未找到则抛出异常。

public void Delete(TKey tk)
{
    foreach (KeyValuePair<TKey, TValue> kvp in llDictionary)
    {
        if (tk.Equals(kvp.Key))
        {
            llDictionary.Remove(kvp);
            return;
        } 
    }
    throw new Exception("删除失败：不存在这个主键");
}

修改 (Modify)： 找到指定 Key 的节点，先插入新节点，再移除旧节点，以保持链表结构的完整性。

public void Modify(TKey tk, TValue tv)
{
    LinkedListNode<KeyValuePair<TKey, TValue>> lln = llDictionary.First;
    while(lln != null )
    {
        if (tk.Equals(lln.Value.Key))
        {
            llDictionary.AddBefore(lln, new KeyValuePair<TKey, TValue>(tk, tv));
            llDictionary.Remove(lln);
            return;
        }
        lln = lln.Next;
    }
    throw new Exception("修改失败：不存在这个主键");
}

第4步：实现数据排序与导出

定义一个枚举 PrintType 控制排序行为。核心的 ToList 方法需要区分 Key 的类型（字符串或数字），手动实现插入排序逻辑以构建新的有序链表。

public enum PrintType
{
    Normal = 0,
    Ascend = 1, 
    Descend = 2 
};

public List<KeyValuePair<TKey, TValue>> ToList(PrintType printType = PrintType.Normal)
{
    switch (printType)
    {
        case PrintType.Normal:
            return llDictionary.ToList();
            
        case PrintType.Ascend:
            // 此处省略详细的插入排序逻辑（见上文草稿）
            // 逻辑简述：遍历原链表，将每个元素与新有序链表的元素逐个比较，
            // 根据字符串大小或浮点数转换后的数值确定插入位置。
            break;
        
        case PrintType.Descend:
            // 类似升序，但比较符号取反
            break;
    }
    return null;
}

// 升序具体实现片段参考
if (llDictionary.Count == 0) return null;
LinkedList<KeyValuePair<TKey, TValue>> newll = 
 new LinkedList<KeyValuePair<TKey, TValue>>();
try
{
    LinkedListNode<KeyValuePair<TKey, TValue>> lln = llDictionary.First;
    while (lln != null)
    {
        LinkedListNode<KeyValuePair<TKey, TValue>> lln2 = newll.First;
        while (lln2 != null)
        {
            //Key是字符串的情况
            if (llDictionary.First.Value.Key.GetType() == 
             "string".GetType())
            {
                if (string.Compare(lln2.Value.Key.ToString(),
                 lln.Value.Key.ToString()) > 0)
                {
                    newll.AddBefore(lln2, new LinkedListNode
                     <KeyValuePair<TKey, TValue>>(lln.Value));
                    break;
                }
            }
            else //Key可以被转化为浮点数的情况
            {
                if (double.Parse(lln2.Value.Key.ToString()) >
                 double.Parse(lln.Value.Key.ToString()))
                {
                    newll.AddBefore(lln2, new LinkedListNode
                     <KeyValuePair<TKey, TValue>>(lln.Value));
                    break;
                }
            }
            lln2 = lln2.Next;
        }
        if (lln2 == null)
        {
            newll.AddLast(new LinkedListNode
             <KeyValuePair<TKey, TValue>>(lln.Value));
        }
        lln = lln.Next;
    }
}
catch (Exception ex)
{
    Console.WriteLine(ex.Message);
}
return newll.ToList();

调用示例与结果

在 Main 函数中实例化 MyDictionary<string, string> 进行测试。依次执行添加、删除、修改、读取及排序操作。

static void Main(string[] args)
{
    MyDictioinary<string, string> dic = new MyDictioinary<string, string>();
    
    // 插入两组数据
    dic.Add("1", "MERCURY");
    dic.Add("2", "VENUS");
    
    // 尝试插入重复主键
    try { dic.Add("1", "EARTH"); } catch (Exception ex) { Console.WriteLine(ex.Message); }
    
    // 删除、新增、修改
    dic.Delete("1");
    dic.Add("1", "MARS");
    dic.Modify("1", "JUPITER");
    dic.Modify("2", "SATURN");
    
    // 添加更多数据
    dic.Add("6", "SUN");
    dic.Add("5", "MOON");
    dic.Add("8", "URANUS");
    dic.Add("9", "NEPTUNE");
    
    // 打印原始数据
    dic.PrintData();
    
    // 索引器测试
    Console.WriteLine("key为6的元素value为：" + dic["6"]);
    Console.WriteLine("key为3的元素value为：" + dic["3"]);
    
    // 获取升序列表
    List<KeyValuePair<string, string>> l;
    l = dic.ToList(MyDictioinary<string, string>.PrintType.Ascend);
    Console.WriteLine("升序排列后的List：");
    for (int i = 0; i < l.Count; i++)
    {
        Console.WriteLine(l[i].Key.ToString() + "\t:" + l[i].Value.ToString());
    }
    
    Console.ReadLine();
}

上述代码展示了从基础数据结构操作到复杂逻辑处理的完整过程。自定义 Dictionary 类有助于深入理解泛型约束、迭代器模式以及排序算法在实际业务中的应用。