I was reading around for undo/redo techniques, I understand how should it be implemented (I found it intuitive).
However I'm thinking about the collection that should be used as history,
A lot of people use stack, but C# stack is implemented as an array, and this is a problem: If I use a "limited" history (for example, for 2000 commands), when the limit is reached I don't have a way to remove items from the end of the stack, and if I find a way to do it, I have to move all elements of the array (and this for each time a command is done).
A LinkedList looks good, but it wastes a lot of memory.
My last option is a custom implementation of a linkedlist, a SingleLinkedList. A node of this list consist of Value property and a NextNode pointer property so I'm using double memory for each item (but nothing more,except if I'm using things smaller than "sizeof(void*)").
I'm also storing a pointer to the first element and a pointer to the last element in the collection.
I can easily add commands to the history and move them to the redohistory in this way, however I can't create a "limited" history because RemoveLast is not allowed (I have to go through the whole collection to remove the last item).
So my question is: Should I use a LinkedList or my custom SingleLinkedList?
Update 1:
Thanks for answers at the moment, in my situation I don't have a memory problem, well, I don't know who I am targeting, I'm creating an utility program and in my own idea of "utility program", they should waste least cpu/memory possible (obviusly don't tell me "write it in c++ so", because there is a big difference).
In my opinion, the singlelinkedlist works well, I don't really like to limit the History, I'm thinking about Photoshop where your history is "unlimited".
I'm only feared from what could happen when the undo history becomes really big, like 8 hours of use. That's why I was thinking about limiting it through a LinkedList.
As someone else stated however, if I limit the linkedlist to a big size, around 60000 commands (I think they should be enough), I'm only wasting a small amount of memory, (4 bytes * 60000) compared to singlelinkedlist.
That said, I think I'll use the LinkedList, however just to be sure, would have been ok if I've used an history without limit?
Update 2:
@Akash Kava Well, what you say it's important but you misunderstood WHY I want use a LinkedList and why I don't want use a stack. The main problem with Stack is that it's necessary to limit it's size, and there isn't a fast way to remove older commands when this limit is reached (it's an array and doubling it's dimension every time it's not something that we want).
A single linked list (think about how it's built) is fast as a stack (all stack operations are O(1)) and doesn't have a limit. However in this case it's needed not to have a limit, otherwise we have the same problem as stack, we don't have a fast way to remove last element of our singlelinkedlist (which behaves like a stack),because we don't know our previous node element from the last node.
In this case it's quite easy, so, to think about a LinkedList, where you have the Previous pointer. However we are using 2 additional pointers for each element of our "Stack" (which is built through a linkedlist this time), which is like using 3 times more memory than what it's necessary to store a Command (with an array we have normal memory usage, singlelinkedlist has 2 times memory usage and linkedlist has 3 times memory usage).
So what I was basically asking is which is the "best" collection to implement a stack for undo-redo pattern.
Your answer made me think that even if I create 60000 command in 1 program it's around 5MB of memory in a program, which is not so much.
Basically if you want to limit your undo/redo history you need a LinkedList, otherwise a SingleLinkedList is better.
Use a LinkedList, or any standard solution, for now, but be careful how you implement it. Put all your undo/redo actions behind a well designed abstraction. Then, if the extra memory that LinkedList is consuming really proves to be a problem (unlikely), you can replace it with your own implementation.
We do this all the time; wrap existing functionality in an abstraction so we can tinker with it if needs be because sometimes domain-specific conditions may offer a chance for extra efficiency. This is your case here; the linked list will work, but your problem domain suggests efficiencies may be possible at the cost of implementation.