| | | 1 | | namespace MoreStructures.Queues; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="IQueue{T}"/> implementation based on a singly-linked linked list of items. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <typeparam name="T"><inheritdoc cref="IQueue{T}"/></typeparam> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// <para id="advantages"> |
| | | 9 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 10 | | /// <br/> |
| | | 11 | | /// - The advantages and disadvantages of using a linked list over an array-based implementation are the same |
| | | 12 | | /// as the ones described in <see cref="Stacks.LinkedListStack{T}"/>. |
| | | 13 | | /// </para> |
| | | 14 | | /// </remarks> |
| | | 15 | | public class LinkedListQueue<T> : IQueue<T> |
| | | 16 | | { |
| | 863 | 17 | | private sealed record Node(T Value, Node? Next) |
| | 286 | 18 | | { |
| | 836 | 19 | | public Node? Next { get; set; } = Next; |
| | 286 | 20 | | } |
| | | 21 | | |
| | 1470 | 22 | | private Node? Head { get; set; } = null; |
| | 863 | 23 | | private Node? Last { get; set; } = null; |
| | | 24 | | |
| | | 25 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 26 | | /// <remarks> |
| | | 27 | | /// Stored and updated in constant time at each <see cref="Enqueue(T)"/> and <see cref="Dequeue"/>. |
| | | 28 | | /// <br/> |
| | | 29 | | /// Time and Space Complexity are O(1). |
| | | 30 | | /// </remarks> |
| | 1228 | 31 | | public int Count { get; private set; } = 0; |
| | | 32 | | |
| | | 33 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 34 | | /// <remarks> |
| | | 35 | | /// Checks the front of the underlying linked list. |
| | | 36 | | /// <br/> |
| | | 37 | | /// Time and Space Complexity are O(1). |
| | | 38 | | /// </remarks> |
| | | 39 | | public T Peek() |
| | 9 | 40 | | { |
| | 9 | 41 | | if (Head == null) |
| | 3 | 42 | | throw new InvalidOperationException($"Cannot {nameof(Peek)} on an empty queue."); |
| | | 43 | | |
| | 6 | 44 | | return Head.Value; |
| | 6 | 45 | | } |
| | | 46 | | |
| | | 47 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 48 | | /// <remarks> |
| | | 49 | | /// First, it retrieves the item referenced by the front of the underlying linked list. |
| | | 50 | | /// <br/> |
| | | 51 | | /// Then it updates the reference to the head of the linked list, to point to its "next". |
| | | 52 | | /// The reference to the last item is also updated, if the head is set to point to null. |
| | | 53 | | /// <br/> |
| | | 54 | | /// Time and Space Complexity are O(1). |
| | | 55 | | /// </remarks> |
| | | 56 | | public T Dequeue() |
| | 288 | 57 | | { |
| | 288 | 58 | | if (Head == null) |
| | 3 | 59 | | throw new InvalidOperationException($"Can't {nameof(Dequeue)} on an empty queue."); |
| | | 60 | | |
| | 285 | 61 | | var head = Head.Value; |
| | 285 | 62 | | Head = Head.Next; |
| | 285 | 63 | | Count--; |
| | 285 | 64 | | if (Head == null) |
| | 20 | 65 | | Last = null; |
| | 285 | 66 | | return head; |
| | 285 | 67 | | } |
| | | 68 | | |
| | | 69 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 70 | | /// <remarks> |
| | | 71 | | /// Creates a new node wrapping the provided <paramref name="item"/>. |
| | | 72 | | /// <br/> |
| | | 73 | | /// Then, it appends it to the back of the linked list of items, updating the reference to the last item of the |
| | | 74 | | /// list. |
| | | 75 | | /// <br/> |
| | | 76 | | /// It also updates the head, if the list was previously empty, to point to the newly created item. |
| | | 77 | | /// <br/> |
| | | 78 | | /// Time and Space Complexity are O(1). |
| | | 79 | | /// </remarks> |
| | | 80 | | public void Enqueue(T item) |
| | 286 | 81 | | { |
| | 286 | 82 | | var node = new Node(item, null); |
| | 286 | 83 | | if (Last == null) |
| | 21 | 84 | | { |
| | 21 | 85 | | Last = Head = node; |
| | 21 | 86 | | } |
| | | 87 | | else |
| | 265 | 88 | | { |
| | 265 | 89 | | Last.Next = node; |
| | 265 | 90 | | Last = node; |
| | 265 | 91 | | } |
| | 286 | 92 | | Count++; |
| | 286 | 93 | | } |
| | | 94 | | } |