如何修改自定义双向链表CustDoublyLinkedList实现高效插入？

出于学习目的，我在白板上实现了一个自定义双向链表CustDoublyLinkedList类，该类包含嵌套的Node类。但当前指定索引的Insert方法需要循环遍历至目标索引才能执行插入操作，我希望能像Add或PushFront方法那样直接完成插入，无需使用循环。此外，我还为该链表添加了IndexOf和Contain方法。

以下是我的实现代码：

CustDoublyLinkedList<int> myList = new();

myList.Add(12);
myList.Add(13);
myList.Add(14);
myList.Add(45);
myList.Add(28);
myList.Add(120);

myList.PushFront(32);
myList.Insert(3,1500);

for (int i = 0; i < myList.Count; i++)
{
    Console.WriteLine(myList[i]);
}

class CustDoublyLinkedList<T>
{
    private class Node
    {
        public T Element { get; set; }
        public Node NextNode { get; set; }
        public Node PrevNode { get; set; }

        public Node(T data)
        {
            this.Element = data;
            this.PrevNode = null;
            this.NextNode = null;
        }

        public Node(T data, Node prevNode): this(data)
        {
            prevNode.NextNode = this;
        }

        public Node(T data, Node prevNode, Node nextNode) : this(data, prevNode)
        {
            nextNode.PrevNode = this;
        }
    }

    private Node head;
    private Node tail;
    private int counter;

    public CustDoublyLinkedList()
    {
        this.head = null;
        this.tail = null;
        this.counter = 0;
    }

    public void Insert(int index, T item)
    {
        if (index == 0)
        {
            throw new ArgumentOutOfRangeException("You Can Push with PushFront Method at Index: " + index);
        }

        if (index < 0 || index >= this.counter)
        {
            throw new ArgumentOutOfRangeException("invalid Index: " + index);
        }

        Node newNode = new(item);
        Node currentNode = this.head;

        for (int i = 0; i < index - 1; i++)
        {
            currentNode = currentNode.NextNode;
        }

        newNode.NextNode = currentNode.NextNode;
        newNode.PrevNode = currentNode.PrevNode;
        currentNode.NextNode = newNode;

        this.counter++;
    }

    public void Add(T item)
    {
        if (this.head == null)
        {
            this.head = new(item);
            this.tail = this.head;
        }
        else
        {
            Node newNode = new(item, this.tail);
            this.tail = newNode;
        }

        this.counter++;
    }

    public void PushFront(T item)
    {
        Node newNode = new(item);
        newNode.NextNode = this.head;
        newNode.PrevNode = null;

        if(this.head != null)
        {
            this.head.PrevNode = newNode;
        }

        this.head = newNode;
        this.counter++;
    }

    public bool Contain(T item)
    {
        int index = IndexOf(item);
    
        if (index != -1)
        {
            return true;
        }

        return false;
    }

    public int IndexOf(T item)
    {
        Node currentNode = this.head;
        int index = 0;

        while(currentNode != null)
        {
            if (object.Equals(currentNode.Element, item))
            {
                return index;
            }

            currentNode = currentNode.NextNode;
            index++;
        }

        return -1;
    }

    public int Count
    {
        get { return this.counter; }
    }

    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= this.counter)
            {
                throw new IndexOutOfRangeException("Invalid Index: " + index);
            }

            Node currentNode = this.head;

            for (int i = 0; i < index; i++)
            {
                currentNode = currentNode.NextNode;
            }

            return currentNode.Element;
        }
        set
        {
            if (index < 0 || index >= this.counter)
            {
                throw new IndexOutOfRangeException("Invalid Index: " + index);
            }

            Node currentNode = this.head;

            for (int i = 0; i < index; i++)
            {
                currentNode = currentNode.NextNode;
            }

            currentNode.Element = value;
        }
    }
}

首先明确：双向链表本身不支持随机访问，没办法直接通过索引定位到目标节点——除非维护额外的辅助结构，但这会违背链表的设计初衷。不过我们可以优化遍历逻辑，减少不必要的循环步数，同时修复原方法的bug：

优化后的Insert方法 #

public void Insert(int index, T item)
{
    if (index < 0 || index > counter)
    {
        throw new ArgumentOutOfRangeException(nameof(index), $"索引无效: {index}");
    }

    // 插入头部直接复用已实现的PushFront
    if (index == 0)
    {
        PushFront(item);
        return;
    }
    // 插入尾部直接复用已实现的Add
    if (index == counter)
    {
        Add(item);
        return;
    }

    Node newNode = new Node(item);
    Node targetNode;

    // 根据索引位置选择从头部或尾部遍历，减少遍历次数
    if (index <= counter / 2)
    {
        targetNode = head;
        for (int i = 0; i < index; i++)
        {
            targetNode = targetNode.NextNode;
        }
    }
    else
    {
        targetNode = tail;
        for (int i = counter - 1; i > index; i--)
        {
            targetNode = targetNode.PrevNode;
        }
    }

    // 调整节点引用完成插入，修复原方法的引用错误
    newNode.PrevNode = targetNode.PrevNode;
    newNode.NextNode = targetNode;
    targetNode.PrevNode.NextNode = newNode;
    targetNode.PrevNode = newNode;

    counter++;
}

优化说明 #

1. 边界复用：直接调用已有的PushFront和Add处理头部、尾部插入，避免重复代码。
2. 双向遍历优化：根据索引位置选择从头部或尾部开始遍历，最坏情况下只需要遍历链表的一半长度，提升效率。
3. 修复bug：原方法中newNode.PrevNode = currentNode.PrevNode的逻辑错误，优化后正确维护了前后节点的引用关系。

额外说明 #

如果一定要完全避免循环实现随机插入，你需要维护一个List<Node>类型的索引表，每次增删节点时同步更新这个表。但这样会让链表失去动态增删的优势（比如头部/尾部插入的O(1)复杂度会因为更新索引表变成O(n)），除非有特殊需求，否则不建议这么做。

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