.NET中‘双指针列表’是什么？如何实现并使用该O(1)删除的List<T>？

Hey there! Great question about this lesser-known List<T> variant—double-pointer lists are super handy when you need fast deletions without the overhead of shifting elements like a regular List<T> does. Let's walk through exactly what they are, how to implement one, and how to use it.

A double-pointer list (often called a doubly linked list with a List<T>-like interface) is a data structure where each element (node) keeps track of both its previous and next element in the list. Unlike a standard List<T>—which stores elements in a contiguous array and requires O(n) time to delete elements (since all elements after the deleted one have to be shifted left)—a double-pointer list lets you delete any node in O(1) time. You just adjust the pointers of the neighboring nodes to skip over the deleted one.

• Each node contains three parts: T Value (the actual data), Node<T> Previous (pointer to the prior node), Node<T> Next (pointer to the next node)
• The list itself tracks the Head (first node) and Tail (last node) to make adding elements to either end fast
• To unlock O(1) deletions, you need direct access to the node (not just its index or value). If you delete by index/value, it's still O(n) because you have to traverse to find the node first—but with a node reference, deletion is instant.

Here's a production-ready implementation that mirrors common List<T> methods while leveraging double-pointer logic:

public class DoublePointerList<T>
{
    // Internal node class to hold data and pointers
    private class Node<TNode>
    {
        public TNode Value { get; set; }
        public Node<TNode> Previous { get; set; }
        public Node<TNode> Next { get; set; }

        public Node(TNode value)
        {
            Value = value;
            Previous = null;
            Next = null;
        }
    }

    private Node<T> _head;
    private Node<T> _tail;
    public int Count { get; private set; }

    // Add an element to the end of the list
    public void Add(T value)
    {
        var newNode = new Node<T>(value);
        if (_tail == null)
        {
            // List is empty, head and tail are the same
            _head = newNode;
            _tail = newNode;
        }
        else
        {
            _tail.Next = newNode;
            newNode.Previous = _tail;
            _tail = newNode;
        }
        Count++;
    }

    // Add an element to the start of the list
    public void AddFirst(T value)
    {
        var newNode = new Node<T>(value);
        if (_head == null)
        {
            _head = newNode;
            _tail = newNode;
        }
        else
        {
            _head.Previous = newNode;
            newNode.Next = _head;
            _head = newNode;
        }
        Count++;
    }

    // Delete a node by reference (O(1) time)
    public bool Remove(Node<T> nodeToRemove)
    {
        if (nodeToRemove == null)
            return false;

        // Update head if we're deleting the first node
        if (nodeToRemove == _head)
            _head = nodeToRemove.Next;

        // Update tail if we're deleting the last node
        if (nodeToRemove == _tail)
            _tail = nodeToRemove.Previous;

        // Adjust neighboring pointers to skip the deleted node
        if (nodeToRemove.Previous != null)
            nodeToRemove.Previous.Next = nodeToRemove.Next;

        if (nodeToRemove.Next != null)
            nodeToRemove.Next.Previous = nodeToRemove.Previous;

        Count--;
        return true;
    }

    // Delete by value (O(n) time—we have to find the node first)
    public bool Remove(T value)
    {
        var current = _head;
        while (current != null)
        {
            if (EqualityComparer<T>.Default.Equals(current.Value, value))
            {
                return Remove(current);
            }
            current = current.Next;
        }
        return false;
    }

    // Get node by index (O(n) time—optimized to start from head/tail)
    public Node<T> GetNode(int index)
    {
        if (index < 0 || index >= Count)
            throw new ArgumentOutOfRangeException(nameof(index));

        Node<T> current;
        // Traverse from the closer end to save time
        if (index < Count / 2)
        {
            current = _head;
            for (int i = 0; i < index; i++)
                current = current.Next;
        }
        else
        {
            current = _tail;
            for (int i = Count - 1; i > index; i--)
                current = current.Previous;
        }
        return current;
    }

    // Get value by index
    public T Get(int index)
    {
        return GetNode(index).Value;
    }

    // Traverse the list forward
    public IEnumerable<T> TraverseForward()
    {
        var current = _head;
        while (current != null)
        {
            yield return current.Value;
            current = current.Next;
        }
    }

    // Traverse the list backward
    public IEnumerable<T> TraverseBackward()
    {
        var current = _tail;
        while (current != null)
        {
            yield return current.Value;
            current = current.Previous;
        }
    }
}

Here's a quick example showing common operations, including the O(1) deletion magic:

// Initialize a new list
var myList = new DoublePointerList<string>();

// Add elements
myList.Add("Apple");
myList.Add("Banana");
myList.AddFirst("Orange");

// Get the second node (Banana)
var bananaNode = myList.GetNode(1);

// Remove it in O(1) time—no element shifting needed!
myList.Remove(bananaNode);

// Traverse forward to see the result
foreach (var item in myList.TraverseForward())
{
    Console.WriteLine(item); // Output: Orange, Apple
}

// Remove by value (O(n) time since we search first)
myList.Remove("Orange");

// Traverse backward
foreach (var item in myList.TraverseBackward())
{
    Console.WriteLine(item); // Output: Apple
}

• O(1) deletion only works if you have a node reference: Deleting by index/value is still O(n) because you need to find the node first.
• No O(1) random access: Unlike List<T>, getting an element by index requires traversal (though we optimized it to start from the closer end).
• Perfect for dynamic collections: This shines in scenarios where you frequently delete elements you're currently iterating over (like event handlers or managing active objects).

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