实现Undo/Redo的好收藏？

Question

我正在阅读撤消/重做技术,我明白应该如何实现(我发现它很直观).

但是我正在考虑应该用作历史的集合,

很多人使用堆栈,但C#堆栈实现为数组,这是一个问题:如果我使用"有限"历史记录(例如,对于2000命令),当达到限制时我没有从堆栈末尾删除项目的方法,如果我找到了一种方法,我必须移动数组的所有元素(这是每次命令完成时).

LinkedList看起来不错,但它浪费了大量内存.

我的最后一个选项是链表的自定义实现,SingleLinkedList.此列表的一个节点由Value属性和NextNode指针属性组成,因此我为每个项目使用双重内存(但除此之外,除非我使用的内容小于"sizeof(void*)").

我还存储了指向第一个元素的指针和指向集合中最后一个元素的指针.

我可以轻松地将命令添加到历史记录中并以这种方式将它们移动到重做历史,但是我无法创建"有限"历史记录,因为不允许使用RemoveLast(我必须通过整个集合来删除最后一项).

所以我的问题是:我应该使用LinkedList还是我的自定义SingleLinkedList？

更新1:

感谢您的回答,在我的情况下,我没有内存问题,好吧,我不知道我的目标是谁,我正在创建一个实用程序,并且在我自己的"实用程序"的想法中,他们应该浪费最少的CPU /内存(显然不要告诉我"用c ++写它",因为有很大的区别).

在我看来,单链接列表效果很好,我真的不想限制历史,我在考虑你的历史是"无限"的Photoshop.

我只担心撤消历史变得非常大时会发生什么,比如使用8小时.这就是我考虑通过LinkedList限制它的原因.

然而,正如其他人所说,如果我将链表限制在一个大的大小,大约60000个命令(我认为它们应该足够),我只会浪费少量内存,(4个字节*60000)与singlelinkedlist相比.

也就是说,我想我会使用LinkedList,但只是为了确定,如果我使用无限制的历史记录会没问题吗？

更新2:

@Akash Kava嗯,你说它很重要,但你误解为什么我想使用LinkedList以及为什么我不想使用堆栈.Stack的主要问题是必须限制它的大小,并且当达到这个限制时,没有一种快速的方法来删除旧的命令(它是一个数组,并且每当它不是我们想要的东西时它的尺寸加倍).

单个链表(考虑它是如何构建的)作为堆栈是快速的(所有堆栈操作都是O(1))并且没有限制.但是在这种情况下,它不需要有限制,否则我们遇到与堆栈相同的问题,我们没有快速的方法来删除我们的singlelinkedlist的最后一个元素(它的行为就像一个堆栈),因为我们不知道我们上一个节点的前一个节点元素.

在这种情况下,考虑一个LinkedList,你可以很容易地使用Previous指针.然而,我们为"Stack"的每个元素使用了2个额外的指针(这次是通过链表制作的),这就像使用3倍于存储命令所需的内存(使用数组我们有正常的内存)用法,singlelinkedlist有2倍的内存使用量,链表有3倍的内存使用量).

所以我基本上要问的是哪个是"最佳"集合来实现undo-redo模式的堆栈.

你的回答让我觉得,即使我在一个程序中创建60000命令,它在一个程序中大约是5MB的内存,这不是那么多.

基本上,如果要限制撤消/重做历史记录,则需要使用LinkedList,否则SingleLinkedList会更好.

Answer 1

现在使用 LinkedList 或任何标准解决方案，但要小心如何实现它。将所有撤消/重做操作置于精心设计的抽象后面。然后，如果 LinkedList 消耗的额外内存确实被证明是一个问题（不太可能），您可以用自己的实现替换它。

我们一直这样做；将现有功能包装在抽象中，以便我们可以在需要时对其进行修改，因为有时特定于领域的条件可能会提供额外效率的机会。这就是你的情况；链接列表可以工作，但是您的问题域表明效率可能会以实施为代价。