| | | 1 | | namespace MoreStructures.Stacks; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="IStack{T}"/> implementation based on a singly-linked linked list of items. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <typeparam name="T"><inheritdoc cref="IStack{T}"/></typeparam> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// <para id="advantages"> |
| | | 9 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 10 | | /// <br/> |
| | | 11 | | /// - Compared to an implementation based on an array list, such as <see cref="ArrayListStack{T}"/>, it has the |
| | | 12 | | /// advantage of not requiring contiguous memory, for the backing structure storing the items to be allocated. |
| | | 13 | | /// <br/> |
| | | 14 | | /// - Items of the linked list are allocated on the heap on demand, one by one, each on requiring only the space |
| | | 15 | | /// to store the value of the item (whose size depends on the definition of the type <typeparamref name="T"/>), |
| | | 16 | | /// and the reference to the next node in the list (whose size depends on the bit parallelism of the |
| | | 17 | | /// architecture: typically either 32 or 64 bits). |
| | | 18 | | /// <br/> |
| | | 19 | | /// - That minimizes the risk of <see cref="OutOfMemoryException"/>, due to memory fragmentation, when dealing with |
| | | 20 | | /// large queues. Moreover, it makes the work required for insertion constant and independent from the size of |
| | | 21 | | /// the stack. |
| | | 22 | | /// <br/> |
| | | 23 | | /// - The downside is the number of object allocations, which is constant on an array-based implementation, and as |
| | | 24 | | /// high as the number of items when using a linked list. |
| | | 25 | | /// <br/> |
| | | 26 | | /// - This introduces more stress on the Garbage Collector and also uses way more memory than an array-based |
| | | 27 | | /// implementation, since each object on the heap has a space overhead required for its memory management. |
| | | 28 | | /// <br/> |
| | | 29 | | /// - Moreover the non-contiguous memory layout requires as many "next" references as the number of items in the |
| | | 30 | | /// queue, which can be higher than the amount of memory used for the items: e.g. a queue of n <see cref="int"/> |
| | | 31 | | /// requires n * 4 bytes for the actual data and double that amount on a 64 bit architecture to store next |
| | | 32 | | /// references. |
| | | 33 | | /// </para> |
| | | 34 | | /// </remarks> |
| | | 35 | | public class LinkedListStack<T> : IStack<T> |
| | | 36 | | { |
| | 148 | 37 | | private sealed record Node(T Value, Node? Next); |
| | | 38 | | |
| | 185 | 39 | | private Node? Head { get; set; } = null; |
| | | 40 | | |
| | | 41 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 42 | | /// <remarks> |
| | | 43 | | /// Stored and updated in constant time at each <see cref="Push(T)"/> and <see cref="Pop"/>. |
| | | 44 | | /// <br/> |
| | | 45 | | /// Time and Space Complexity are O(1). |
| | | 46 | | /// </remarks> |
| | 127 | 47 | | public int Count { get; private set; } = 0; |
| | | 48 | | |
| | | 49 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 50 | | /// <remarks> |
| | | 51 | | /// Checks the front of the underlying linked list. |
| | | 52 | | /// <br/> |
| | | 53 | | /// Time and Space Complexity are O(1). |
| | | 54 | | /// </remarks> |
| | | 55 | | public T Peek() |
| | 4 | 56 | | { |
| | 4 | 57 | | if (Head == null) |
| | 1 | 58 | | throw new InvalidOperationException($"Can't {nameof(Peek)} on an empty stack."); |
| | | 59 | | |
| | 3 | 60 | | return Head.Value; |
| | 3 | 61 | | } |
| | | 62 | | |
| | | 63 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 64 | | /// <remarks> |
| | | 65 | | /// First, it retrieves the item referenced by the head of the underlying linked list. |
| | | 66 | | /// <br/> |
| | | 67 | | /// Then, it updates the reference to the head of the linked list, to point to its "next". |
| | | 68 | | /// <br/> |
| | | 69 | | /// Raises an <see cref="InvalidOperationException"/> if the linked list is empty. |
| | | 70 | | /// <br/> |
| | | 71 | | /// Time and Space Complexity are O(1). |
| | | 72 | | /// </remarks> |
| | | 73 | | public T Pop() |
| | 28 | 74 | | { |
| | 28 | 75 | | if (Head == null) |
| | 2 | 76 | | throw new InvalidOperationException($"Can't {nameof(Pop)} on an empty stack."); |
| | | 77 | | |
| | 26 | 78 | | var head = Head.Value; |
| | 26 | 79 | | Head = Head.Next; |
| | 26 | 80 | | Count--; |
| | 26 | 81 | | return head; |
| | 26 | 82 | | } |
| | | 83 | | |
| | | 84 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 85 | | /// <remarks> |
| | | 86 | | /// Creates a new node wrapping the provided <paramref name="item"/> and sets it as new head of the linked list of |
| | | 87 | | /// items, making it point to the previous head. |
| | | 88 | | /// <br/> |
| | | 89 | | /// Time and Space Complexity are O(1). |
| | | 90 | | /// </remarks> |
| | | 91 | | public void Push(T item) |
| | 31 | 92 | | { |
| | 31 | 93 | | Head = new Node(item, Head); |
| | 31 | 94 | | Count++; |
| | 31 | 95 | | } |
| | | 96 | | } |