如何修改C#有序链表的AddElement方法使其维持有序状态

核心调整前提 #

首先需要给泛型类添加IComparable<T>约束，确保元素支持大小比较，类定义修改为：

class LinkedSortedList<T> where T : IComparable<T>

默认你的Node<T>类已定义public T Data存储节点值、public Node<T> Next存储后继节点指针，示例Node定义如下：

public class Node<T>
{
    public T Data { get; set; }
    public Node<T> Next { get; set; }
    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

AddElement方法重写逻辑 #

原方法直接将新元素追加到链表尾部，无法保证有序，需修改为按元素大小查找对应插入位置，覆盖4种边界场景：

• 链表为空，直接初始化链表
• 新元素小于头节点值，插入到链表头部
• 新元素大于尾节点值，插入到链表尾部
• 新元素大小在中间区间，遍历找到第一个比新元素大的节点，插入到该节点前方

完整修改后代码 #

class LinkedSortedList<T> where T : IComparable<T>
{
    public Node<T> Head { get; set; }
    public Node<T> Tail { get; set; }
    public int Count { get; set; }

    public LinkedSortedList()
    {
        Head = null;
        Tail = null;
        Count = 0;
    }

    public LinkedSortedList(T data)
    {
        CreateList(data);
    }

    public void AddElement(T data)
    {            
        // 空链表直接初始化
        if (Head == null)
        {
            CreateList(data);
            return;
        }

        var newNode = new Node<T>(data);
        // 新元素比头节点小，插入头部
        if (data.CompareTo(Head.Data) < 0)
        {
            newNode.Next = Head;
            Head = newNode;
            Count++;
            return;
        }

        // 新元素比尾节点大，插入尾部
        if (data.CompareTo(Tail.Data) >= 0)
        {
            Tail.Next = newNode;
            Tail = newNode;
            Count++;
            return;
        }

        // 中间位置查找插入点
        Node<T> current = Head;
        // 找到第一个后继节点值大于新元素的节点
        while (current.Next != null && data.CompareTo(current.Next.Data) >= 0)
        {
            current = current.Next;
        }
        // 插入新节点
        newNode.Next = current.Next;
        current.Next = newNode;
        Count++;
    }

    public void CreateList(T data)
    {
        var node = new Node<T>(data);
        Head = node;
        Tail = node;
        Count = 1;
    }
}

可选调整说明 #

• 上述代码默认按升序排列，重复元素插入到相同值节点的后方；如需改为降序，将CompareTo的比较符号反转即可
• 如需重复元素插入到相同值节点的前方，把比较判断中的>=改为>即可

内容的提问来源于stack exchange，提问作者BBB