Several fundamental data structures are frequently used in software development to manage and organize data efficiently.

Array

An array stores a fixed-size sequential collection of elements of the same type. In C#, common variants include Array, ArrayList, and List<T>.

• Accessing an element by index is O(1).
• Searching for a value requires scanning the array: O(N).
• Insertions or deletions (especially in the middle) require shifting elements: O(N).

Linked List

A linked list consists of nodes, where each node holds data and a reference to the next (and possibly previous) node. C# provides LinkedList<T> and LinkedListNode<T>.

• Memory allocation is non-contiguous.
• No direct index-based access—traversal from head is required: O(N) search.
• Insertion or deletion at a known position is O(1), as it only involves updating pointers.

var list = new LinkedList<int>();
list.AddLast(123);
var node = list.Find(123); // Traverses from head

Hash Table

Hash tables store key-value pairs and enable fast lookups using a hash function. In C#, this includes Dictionary<TKey, TValue>, HashSet<T>, and the legacy Hashtable.

• Average-case time complexity for insertion, deletion, and lookup is O(1).
• Does not maintain insertion order (except in specialized implementations).
• Collisions are typically resolved via chaining (e.g., using linked lists) or open addressing.

Queue

A queue follows the First-In-First-Out (FIFO) principle. C# offers Queue<T> for this purpose.

var taskQueue = new Queue<string>();
taskQueue.Enqueue("Log user action");
var task = taskQueue.Dequeue(); // Retrieves the oldest task

Stack

A stack operates on a Last-In-First-Out (LIFO) basis. C# provides Stack<T>.

var navigationStack = new Stack<string>();
navigationStack.Push("/home");
navigationStack.Push("/profile");
var current = navigationStack.Pop(); // Returns "/profile"

Example: Palindrome Check Using Stack and Queue

The following method determines if a singly linked list is a palindrome by leveraging both a stack and a queue:

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public static bool IsPalindrome(ListNode head)
{
    var stack = new Stack<int>();
    var queue = new Queue<int>();

    ListNode current = head;
    while (current != null)
    {
        stack.Push(current.val);
        queue.Enqueue(current.val);
        current = current.next;
    }

    while (stack.Count > 0)
    {
        if (stack.Pop() != queue.Dequeue())
            return false;
    }

    return true;
}

This approach compares elements from both ends simultaneously—stack provides reverse order, while queue maintains original order—enabling a elegant palindrome verification.