设计自定义数据结构的过程

在开发应用程序时，我们可能会遇到这样的情况，即我们无法使用的数据结构真正适合我们要完成的任务。 最近，我遇到了这种情况，正在开发一项功能，该功能要求使用事件监听器的集合。 今天，我想我会借此机会分享设计自定义数据结构背后的思考过程，并提出一些在实现它之前可能要回答的问题。

步骤1：要求

每个设计过程的第一步都是实际确定您希望新结构能够完成的工作。 这包括写下绝对必须要做的事情，以及在哪些方面我们可以摆脱“次优”表现。 让我们针对我们的侦听器列表进行此操作。

• 在我们的列表有效期内，听众可能会分配，也可能不会分配。 我们不希望我们的列表成为对象保留在内存中的原因（并有可能以意想不到的方式操纵我们的程序），因此我们将需要一些保持弱引用的对象。
• 由于侦听器对象可能已释放，因此我们需要一种清除这些对象的方法。 清理结构最多需要O （n）时间，并且应该可以将清理作为其他操作的一部分进行。
• 使用侦听器列表时，将对象插入列表比删除对象更常见。 因此，插入将需要尽可能快，但是移除将不是关键。 我们将采用O （1）的插入复杂度和最多O （n）的移除复杂度。
• 通知列表中的听众将是我们列表中的重要任务。 由于我们需要通知列表中的每个侦听器，因此O （n）是我们可以避免的最快的复杂性。

在满足所有要求之后，我们可以开始考虑使用什么基础数据结构。

步骤2：设计

查看标准库中的可用内容，我们遇到了NSPointerArray —一个可以保存指向对象的弱指针的数组。 这满足了我们的第一个要求。 实际上，此数组几乎可以满足我们上面印刷的所有要求。 唯一不满足的要求是第二个要求。 当我们在其上调用.compact()方法时，有很多nil指针的情况下，运行时复杂度（基于实现细节的假设）最终将是二次方的，这不是我们想要的。

如果我们考虑自己设计自定义数据结构怎么办？ 什么是合适的？ 让我们看一下链接列表。

链接列表满足第一个要求，因为我们可以设计节点以保留对其对象的弱引用。 通过将新节点添加到列表的根端，我们可以在恒定时间内插入新对象。 删除对象将是O （n）操作，因为我们需要遍历列表并查找引用。 这是可以接受的，因为这是我们在要求中指定的内容。 通知我们的侦听器对象就像遍历列表一样简单，这是一个O （n）操作。 另外，我们可以使用相同的遍历查找零引用并将其删除。 如果我们在通知周期的一部分中实现删除，那么这将与重新分配一些节点指针一样容易，并且将是O （1）操作。 考虑一下，这种结构实际上听起来很适合我们的目的。

步骤3：实施

我们将花费一些时间来查看自定义结构的一些实现细节。 首先，让我们看一下链接列表的“协议”（严格来说，这只是出于说明的目的，因为为这样一个特定的实现制定协议实际上没有任何意义，并且其中包含了我们不会通常要公开）。 这些方法将是非常基本的，并且我敢肯定您自己实现这些方法不会遇到任何问题，但是我将花几行.notify()讨论一种很好的方法，以将一种清除列表的方法合并到.notify()方法。

 协议WeakReferenceLinkedList { 
  relatedtype数据类型：AnyObject 
  var root：WeakRefNode ？ 
  func insert（_ object：DataType）->无效 
  func remove（_ object：DataType）-> DataType？ 
  func notify（）->无效 
  } 

将要保留我们弱引用的节点将如下所示：

 类WeakRefNode  { 
 弱var参考：DataType？ 
  var next：WeakRefNode ？ 
  } 

到目前为止，这是一个非常标准的链接列表，但允许在任何时候取消分配引用。

有趣的部分是实现.notify()方法时。 由于我们希望此调用断开所有包含nil引用的节点的连接，因此我们可以将其实现为递归方法的包装方法，该方法的作用取决于当前节点是否具有nil引用。 递归方法将这样声明：

  func notifyAndClean（node：inout WeakRefNode ？）-> WeakRefNode ？ 

即将发生的是.notify()将使用根节点作为参数调用此方法，并将返回值分配给root变量。 然后notifyAndClean(node:)方法的反应如下：

  func notifyAndClean（node：inout WeakRefNode ？）-> WeakRefNode ？  { 
 如果让节点=节点{ 
  //当前节点存在， 
  //表示我们还没有 
  //到达列表的末尾 

 如果让reference = node.reference { 
  //当前节点具有有效的引用， 
  //因此，在通知之后， 
  //递归调用并分配返回值 
  //将值赋给下一个变量，然后 
  //将当前节点返回到我们的 
  //父项。 
  reference.performListenerAction（） 
  node.next = notifyAndClean（node.next） 
 返回节点 

  }其他{ 
  //当前节点的引用为nil 
  //并应绕过，因此我们返回 
  //下一个可用节点回到我们的父节点。 
 返回notifyAndClean（node.next） 

  } 
  }其他{ 
  //当前节点为nil，我们已经 
  //到达列表的末尾。 
 返回零 
  } 
  } 

这不是很多代码，但是递归调用很棘手，因此请确保您注意并阅读注释以了解实际情况。

从高层的角度来看，这就像在整个递归调用中构建一个节点链。 递归结束后，我们会折叠链，绕过所有我们不想保留的节点。
请注意，每次调用.notify()时，我们都会重新分配大多数（或全部） .next指针以及.notify()变量。 这似乎是不必要的事情，因为某些（或全部）指针不会改变。 但是，重新分配指针的开销很小，它使我们可以编写一种简短易懂的方法，因此我们可以接受。

这次就是这样！ 如果您有任何疑问，请随时发表评论，然后继续获取有关未来文章的通知。