Хорошая коллекция для реализации Undo / Redo?
Я читал повсюду о методах отмены / повтора, я понимаю, как это должно быть реализовано (я нашел это интуитивно понятным).
Однако я думаю о коллекции, которую следует использовать как историю,
Многие люди используют стек, но стек C # реализован как массив, и это проблема: Если я использовать «ограниченную» историю (например, для 2000 команд), когда предел достигнут, у меня нет способа удалить элементы из конца стека, и если я найду способ сделать это, я должен перемещать все элементы массива (и это каждый раз, когда выполняется команда).
LinkedList выглядит неплохо, но тратит много памяти.
Мой последний вариант - это индивидуальная реализация связанного списка SingleLinkedList. Узел этого списка состоит из свойства Value и свойства указателя NextNode, поэтому я использую двойную память для каждого элемента (но не более того , кроме случаев, когда я использую вещи меньшие, чем sizeof (void *)).
Я также сохраняю указатель на первый элемент и указатель на последний элемент в коллекции.
Я могу легко добавлять команды в историю и перемещать их в повторную историю таким образом, однако я не могу создать «ограниченную» историю, потому что RemoveLast не разрешен (мне нужно просмотреть всю коллекцию, чтобы удалить последнюю элемент).
Итак, мой вопрос: Что мне следует использовать: LinkedList или мой собственный SingleLinkedList?
Обновление 1:
На данный момент спасибо за ответы, в моей ситуации у меня нет проблем с памятью , ну, я не знаю, на кого я нацелен, я создаю служебную программу, и в моем собственном представлении о "служебной программе" они должны тратить как можно меньше ЦП / памяти (очевидно, не говорите мне "напишите это в c ++ so », потому что разница большая).
На мой взгляд, singlelinkedlist работает хорошо, мне не очень нравится ограничивать Историю, я думаю о Photoshop, где ваша история «безгранична».
Меня пугает только то, что может случиться, когда история отмены станет действительно большой, например, 8 часов использования. Вот почему я подумал об ограничении ее с помощью LinkedList.
Однако, как сказал кто-то другой, если я ограничиваю связанный список большим размером, около 60000 команд (я думаю, что их должно быть достаточно), я трачу лишь небольшой объем памяти (4 байта * 60000) по сравнению с singlelinkedlist.
Тем не менее, я думаю, что буду использовать LinkedList, но на всякий случай, было бы хорошо, если бы я использовал историю без ограничений?
Обновление 2:
@Akash Kava Что ж, то, что вы говорите, важно, но вы неправильно поняли, ПОЧЕМУ я хочу использовать LinkedList и почему я не хочу использовать стек. Основная проблема со стеком заключается в том, что необходимо ограничить его размер, и нет быстрого способа удалить старые команды, когда этот предел достигнут (это массив, удваивающий его размер каждый раз, когда это не то, что нам нужно).
Единый связанный список (подумайте о том, как он построен) работает быстро, как стек (все операции со стеком - O (1)) и не имеет ограничений. Однако в этом случае необходимо , чтобы не было ограничения, иначе у нас будет та же проблема, что и у стека, у нас нет быстрого способа удалить последний элемент нашего singlelinkedlist (который ведет себя как стек), потому что мы не знаем наш предыдущий элемент узла от последнего узла.
В этом случае довольно легко подумать о LinkedList, где у вас есть указатель Previous. Однако мы используем 2 дополнительных указателя для каждого элемента нашего "Stack" (который построен с помощью на этот раз связанный список), что похоже на использование в 3 раза большего объема памяти, чем необходимо для хранения команды (с массивом у нас нормальное использование памяти, singlelinkedlist имеет использование памяти в 2 раза, а связанный список имеет использование памяти в 3 раза).
Итак, я в основном спрашивал, какая коллекция является «лучшей» для реализации стека для шаблона отмены-повтора.
Ваш ответ заставил меня подумать, что даже если я создам 60000 команд в 1 программе, это будет около 5 МБ памяти в программе, что не так уж и много.
Обычно, если вы хотите ограничить историю отмен / повторов, вам нужен LinkedList, в противном случае лучше использовать SingleLinkedList.