连锁类

Question

我创建了 classes 的长链，每个 link(class) 只知道下一个和前一个 link。当索引不重要时，我发现数组比数组有很大优势。

public class ChainLink
{
    public ChainLink previousLink, nextLink;

    // Accessors here
}

问题：

这种技术实际上叫什么？（我不知道要搜索什么）
是否有 .Net class 做同样的事情？
与 Array 或 List 相比，性能有明显影响吗？

我使用的访问器示例

分配给链：

    public ChainLink NextLink {
        get{ return _nextLink;}
        set {
            _nextLink = value;
            if (value != null)
                value._previousLink = this;
        }
    }

    public void InsertNext (ChainLink link)
    {
        link.NextLink = _nextLink;
        link.PreviousLink = this;
    }

缩短链条：

如果我取消分配链的下一个 link，而主程序未引用剩余的 link，垃圾收集器将为我处理数据。

测试循环引用：

    public bool IsCircular ()
    {
        ChainLink link = this;
        while (link != null) {
            link = link._nextLink;
            if (link == this)
                return true;
        }
        return false;
    }

偏移索引：

    public ChainLink this [int offset] {
        get {
            if (offset > 0 && _nextLink != null)
                return _nextLink [offset - 1];
            if (offset < 0 && _previousLink != null)
                return _previousLink [offset + 1];
            return this;
        }
    }

Answer 1

1) 这种结构称为双向链表

2) 通过 LinkedList

在 C# 中存在此实现

3) 关于这个话题有很多文章： here 或 this SO post

Answer 2

其他人已经回答了关于这叫什么以及等效的 .Net class（LinkedList）的问题，但我想我会快速查看您的 [=15] 的速度=] 与数组和 List.

我向您的 ChainLink class 添加了一个方法 Foo() 以便每个对象实例都可以访问：

public class ChainLink
{
    public ChainLink previousLink, nextLink;

    // Accessors here
    public void Foo()
    { }
}

第一种方法创建一个数组，然后计算访问数组中每一项所需的时间：

private void TestArray()
{
    // Setup the Array
    ChainLink[] Test = new ChainLink[1000000];
    for (int i = 0; i < 1000000; i++)
        Test[i] = new ChainLink();

    // Use a Stopwatch to measure time
    Stopwatch SW;
    SW = new Stopwatch();
    SW.Start();

    // Go through items in the array
    for (int i = 0; i < Test.Length; i++)
        Test[i].Foo();

    // Stop timer and report results
    SW.Stop();
    Console.WriteLine(SW.Elapsed);
}

接下来，我创建了一个方法来使用 List<T> 以及访问其中每个项目需要多长时间：

private void TestList()
{
    // Setup the list
    List<ChainLink> Test = new List<ChainLink>();
    for (int i = 0; i < 1000000; i++)
        Test.Add(new ChainLink());

    // Use a Stopwatch to measure time
    Stopwatch SW;
    SW = new Stopwatch();
    SW.Start();

    // Go through items in the list
    for (int i = 0; i < Test.Count; i++)
        Test[i].Foo();

    // Stop timer and report results
    SW.Stop();
    Console.WriteLine(SW.Elapsed);
}

最后，我创建了一个方法来使用您的 ChainLink 并移动到下一个项目，直到没有更多：

private void TestChainLink()
{
    // Setup the linked list
    ChainLink Test = new ChainLink();
    for (int i = 0; i < 1000000; i++)
    {
        Test.nextLink = new ChainLink();
        Test = Test.nextLink;
    }

    // Use a Stopwatch to measure time
    Stopwatch SW;
    SW = new Stopwatch();
    SW.Start();

    // Go through items in the linked list
    while (Test != null)
    {
        Test.Foo();
        Test = Test.nextLink;
    }

    // Stop timer and report results
    SW.Stop();
    Console.WriteLine(SW.Elapsed);
}

运行这些中的每一个都会产生一些有启发性的结果：

TestArray(): 00:00:00.0058576

TestList(): 00:00:00.0103650

TestChainLink(): 00:00:00.0000014

多次迭代得出相似的数字。

总之，您的 ChainLink 比数组快 4,100 倍，比 List 快 7,400 倍。

连锁类

Chain linked classes

c#

arrays

reference

我使用的访问器示例

连锁 类

Chain linked classes

c#

arrays

reference

我使用的访问器示例

连锁类