双向链表实现

• 下载源文件 - 51 Kb

引言

前几天我用 C# 编写代码时，意识到我需要一个链表来简化我正在做的事情。我想要一个可以围绕移除的对象收缩的列表，并且不依赖于数组。我自然而然地转向了 .NET Framework 和 System.Collections 命名空间，查看我原本以为会存在的 .NET 链表。令我惊讶的是，并没有。我简直不敢相信。然后我搜索 MSDN，想看看它是否被放在了另一个命名空间。没有；它只是不存在于 .NET Framework 中。最后，我搜索了互联网，但仍然找不到用 C# 实现的链表。

这启发了我编写自己的链表。不是普通的单向链表，而是双向链表。在双向链表中，每个节点都有一个指向下一个节点和前一个节点的引用。普通的单向链表只有一个指向下一个节点的引用。有了双向链表，就可以轻松地向前和向后遍历列表，并以常数时间删除一个节点。

分解

我的双向链表，我们以后就称它为 LinkedList，首先实现了以下接口。

• IList（它是 ICollection 和 IEnumerable 的基类）
• ICloneable

在这个公共接口之下，我们有很多非常重要的私有成员，它们完成了大部分工作。

• class Node
• class LinkedListEnumerator

• FindNodeAt(int)
• Remove(Node)

• Node headerNode
• int modifications

一些细节

Node 类是一个非常简单的类，但它是 LinkedList 的关键部分。它封装了一个对象，并保存了指向下一个节点和前一个节点的引用。Node 类对 LinkedList 的用户是隐藏的，因此它就像 .NET Framework 中的任何其他集合一样工作。

类型为 Node 的 headerNode 成员变量在列表中作为起始点起着重要作用。这个 Node 包含一个 null 引用，用户永远无法访问或移除它。它不计入列表中对象的总数。这个 Node 在双向链表中很重要，因为它在技术上是列表的开始和结束。

FindNodeAt(int index) 方法包含通过 index 访问列表的搜索算法。目前，它将列表分成两半，并根据哪个半部分最接近请求的 index 从开头或结尾开始搜索。此方法被所有直接或间接需要通过 index 访问 object 的其他方法使用。这有助于使搜索更快。对于大型列表，通过进一步划分再搜索有可能进行改进，但会以牺牲小型列表为代价。目前，这似乎是大多数用法的最佳折衷方案。用于查找 Node 的当前算法如下。

    Node node = headerNode;

    if (index < (count / 2))
    {
      for (int i = 0; i <= index; i++)
        node = node.NextNode;
    }
    else
    {
      for (int i = count; i > index; i--)
        node = node.PreviousNode;
    }

Remove(Node value) 方法很重要，因为它通过压缩列表来调整剩余的 Node。这可以通过简单地获取需要移除的 Node，并将其前一个 Node 的 next Node 引用更改为其下一个 Node，并将其下一个 Node 的 previous Node 引用更改为其前一个 Node，然后让它被垃圾回收器处理来实现。通过查看此方法中使用的算法，可以更容易地理解这一点。

    if (value != headerNode)
    {
      value.PreviousNode.NextNode = value.NextNode;
      value.NextNode.PreviousNode = value.PreviousNode;

      count--;
      modifications++;
    }

类型为 int 的 modifications 成员变量在每次修改列表结构时都会递增。然后，LinkedListEnumerator 使用该变量来防止在枚举过程中对列表进行并发修改。

LinkedList 类 **不是线程安全的**（设计上）。如果需要线程安全，可以扩展该类来提供它。

LinkedListEnumerator 类是 **故障快速（fail-fast）** 的。这意味着它使用创建时传递的 modifications 变量来知道在枚举期间是否发生了任何修改。在 MoveNext() 方法中，在递增到下一个值之前会进行检查。如果检测到修改，它将抛出一个 SystemException，然后可以捕获并相应地处理。

private class LinkedListEnumerator : IEnumerator
{
  private LinkedList  linkedList;
  private int         validModificationCount;
  private Node        currentNode;
  
  public LinkedListEnumerator(LinkedList linkedList)
  {
    this.linkedList         = linkedList;
    validModificationCount  = linkedList.modifications;
    currentNode             = linkedList.headerNode;
  }
  
  public object Current
  {
    get
    {
      return currentNode.CurrentNode;
    }
  }
  
  public void Reset()
  {
    currentNode = linkedList.headerNode;
  }

  public bool MoveNext()
  {
    bool moveSuccessful = false;

    if (validModificationCount != linkedList.modifications)
      throw new SystemException(
          "A concurrent modification occured to the LinkedList " + 
          "while accessing it through it's enumerator.");

    currentNode = currentNode.NextNode;

    if (currentNode != linkedList.headerNode)
      moveSuccessful = true;

    return moveSuccessful;
  }
}

LinkedList(ICollection) 构造函数以及 AddAll(ICollection) 和 InsertAll(int, ICollection) 是为了方便列表用户而提供的。此构造函数调用 AddAll(ICollection)，后者又调用 InsertAll(int, ICollection)。下面是此方法的代码。

public virtual void InsertAll(int index, ICollection collection)
{
  if (collection != null)
  {
    if (0 < collection.Count)
    {
      modifications++;

      Node startingNode = (index == count ? 
                  headerNode : FindNodeAt(index));
      Node previousNode = startingNode.PreviousNode;

      foreach (object obj in collection)
      {
        Node node             = new Node(obj, 
                  startingNode, previousNode);
        previousNode.NextNode = node;
        previousNode          = node;
      }

      startingNode.PreviousNode = previousNode;

      count += collection.Count;            
    }
    else
      throw new ArgumentOutOfRangeException("index", 
                   index, "less than zero");
  }
  else
    throw new ArgumentNullException("collection");
}

LinkedList 提供了两种克隆方法。第一种是 ICloneable 接口的 Clone() 方法。它提供了 LinkedList 的浅拷贝。第二种是 Clone(bool attemptDeepCopy)。如果传入 true，它会尝试对列表进行深拷贝；如果传入 false，则会进行浅拷贝。如果列表中的 object 不是 ICloneable，则会抛出 SystemException。返回的 **尝试** 深拷贝列表 **不能保证** 是 **真正的** 深拷贝。它将克隆委托给对象自身的 Clone() 方法。这是这两种方法的源代码。

public virtual object Clone()
{
  LinkedList listClone = new LinkedList();

  for (Node node = headerNode.NextNode; node != headerNode; 
          node = node.NextNode)
    listClone.Add(node.CurrentNode);

  return listClone;
}

public virtual LinkedList Clone(bool attemptDeepCopy)
{
  LinkedList listClone;

  if (attemptDeepCopy)
  {
    listClone = new LinkedList();

    object currentObject;

    for (Node node = headerNode.NextNode; node != headerNode; 
           node = node.NextNode)
    {
      currentObject = node.CurrentNode;

      if (currentObject == null)
        listClone.Add(null);
      else if (currentObject is ICloneable)
        listClone.Add(((ICloneable)currentObject).Clone());
      else
        throw new SystemException("The object of type [" + 
                     currentObject.GetType() + 
                     "] in the list is not an ICloneable, cannot attempt " + 
                     "a deep copy.");
    } 
  }
  else
    listClone = (LinkedList)this.Clone();

  return listClone;
}

结论

我认为这是一个学习如何实现自定义集合的绝佳类。它本身也非常有用，并且已准备好包含到您的下一个项目中。该类的其余部分对于列表集合来说相当直接。该类使用 XML 注释标签进行了很好的注释。经验丰富的开发人员和中级开发人员应该能够轻松理解该类。

这个 LinkedList 是我正在开发的 .NET 工具集的一部分，并且已经根据 GNU General Public License (GPL) 以 开源 项目的形式发布。我的完整项目可以在 Source Forge 上找到。