Class LinkedListStack<T>

A IStack<T> implementation based on a singly-linked linked list of items.

Inheritance
System.Object
LinkedListStack<T>
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Stacks
Assembly: MoreStructures.dll
Syntax
public class LinkedListStack<T> : IStack<T>
Type Parameters
Name Description
T

Remarks

ADVANTAGES AND DISADVANTAGES
- Compared to an implementation based on an array list, such as ArrayListStack<T>, it has the advantage of not requiring contiguous memory, for the backing structure storing the items to be allocated.
- Items of the linked list are allocated on the heap on demand, one by one, each on requiring only the space to store the value of the item (whose size depends on the definition of the type T), and the reference to the next node in the list (whose size depends on the bit parallelism of the architecture: typically either 32 or 64 bits).
- That minimizes the risk of , due to memory fragmentation, when dealing with large queues. Moreover, it makes the work required for insertion constant and independent from the size of the stack.
- The downside is the number of object allocations, which is constant on an array-based implementation, and as high as the number of items when using a linked list.
- This introduces more stress on the Garbage Collector and also uses way more memory than an array-based implementation, since each object on the heap has a space overhead required for its memory management.
- Moreover the non-contiguous memory layout requires as many "next" references as the number of items in the queue, which can be higher than the amount of memory used for the items: e.g. a queue of n System.Int32 requires n * 4 bytes for the actual data and double that amount on a 64 bit architecture to store next references.

Properties

| Improve this Doc View Source

Count

Declaration
public int Count { get; }
Property Value
Type Description
System.Int32
Remarks

Stored and updated in constant time at each Push(T) and Pop().
Time and Space Complexity are O(1).

Methods

| Improve this Doc View Source

Peek()

Declaration
public T Peek()
Returns
Type Description
T
Remarks

Checks the front of the underlying linked list.
Time and Space Complexity are O(1).

| Improve this Doc View Source

Pop()

Declaration
public T Pop()
Returns
Type Description
T
Remarks

First, it retrieves the item referenced by the head of the underlying linked list.
Then, it updates the reference to the head of the linked list, to point to its "next".
Raises an if the linked list is empty.
Time and Space Complexity are O(1).

| Improve this Doc View Source

Push(T)

Declaration
public void Push(T item)
Parameters
Type Name Description
T item
Remarks

Creates a new node wrapping the provided item and sets it as new head of the linked list of items, making it point to the previous head.
Time and Space Complexity are O(1).

Implements

Extension Methods