我正在阅读有关撤消/重做技术的信息,我了解应该如何实现它(我发现它很直观)。
但是我在考虑应该作为历史的收藏,
很多人使用堆栈,但 C# 堆栈是作为数组实现的,这是一个问题:如果我使用“有限”历史记录(例如,对于 2000 条命令),当达到限制时我没有从堆栈末尾删除项目的方法,如果我找到了一种方法,我必须移动数组的所有元素(每次命令完成时都会移动)。
LinkedList 看起来不错,但会浪费大量内存。
我的最后一个选择是一个链表的自定义实现,一个 SingleLinkedList。该列表的一个节点由 Value 属性和 NextNode 指针属性组成,因此我为每个项目使用双内存(但仅此而已,除非我使用的东西小于“sizeof(void*)”)。
我还存储了指向集合中第一个元素的指针和指向最后一个元素的指针。
我可以轻松地将命令添加到历史记录并以这种方式将它们移动到重做历史记录,但是我无法创建“有限”历史记录,因为不允许 RemoveLast (我必须遍历整个集合才能删除最后一项)。
所以我的问题是:我应该使用 LinkedList 还是我的自定义 SingleLinkedList?
更新1:
感谢您目前的回答,在我的情况下,我没有记忆问题,好吧,我不知道我的目标是谁,我正在创建一个实用程序,并且按照我自己的“实用程序”理念,他们应该尽可能少地浪费 cpu/内存(显然不要告诉我“用 c++ 编写它”,因为有很大的不同)。
在我看来,单链表效果很好,我真的不喜欢限制历史,我正在考虑你的历史是“无限”的 Photoshop。
我只担心撤消历史变得非常大时会发生什么,比如使用 8 小时。这就是为什么我正在考虑通过 LinkedList 来限制它。
然而,正如其他人所说,如果我将链表限制为较大的大小,大约 60000 个命令(我认为它们应该足够了),与单链表相比,我只会浪费少量内存(4 字节 * 60000)。
就是说,我想我会使用 LinkedList,但是可以肯定的是,如果我无限制地使用历史记录会好吗?
更新 2:
@Akash Kava好吧,你说的很重要,但你误解了我为什么要使用 LinkedList 以及为什么我不想使用堆栈。Stack 的主要问题是有必要限制它的大小,并且当达到这个限制时,没有一种快速的方法来删除旧命令(它是一个数组,每次它不是我们想要的东西时都会加倍它的维度)。
单个链表(想想它是如何构建的)和堆栈一样快(所有堆栈操作都是 O(1))并且没有限制。但是在这种情况下,它不需要有限制,否则我们会遇到与堆栈相同的问题,我们没有快速的方法来删除单链表的最后一个元素(其行为类似于堆栈),因为我们不知道来自最后一个节点的上一个节点元素。
在这种情况下,很容易考虑一个 LinkedList,其中有 Previous 指针。但是,我们为“堆栈”的每个元素使用了 2 个额外的指针(这次是通过链表构建的),这就像使用存储命令所需的内存的 3 倍(使用数组,我们有正常的内存)使用,singlelinkedlist 的内存使用量是 2 倍,linkedlist 的内存使用量是 3 倍)。
所以我基本上要问的是哪个是实现撤销重做模式堆栈的“最佳”集合。
你的回答让我觉得即使我在 1 个程序中创建 60000 个命令,它在一个程序中也有大约 5MB 的内存,这不是那么多。
基本上,如果你想限制你的撤销/重做历史,你需要一个 LinkedList,否则 SingleLinkedList 更好。