Arrays and Linked Lists in C#:

When learning data structures, two of the most fundamental types are Arrays and Linked Lists. Understanding them deeply helps you build an efficient mindset for coding, especially in C#. Let’s dive into what they are, how they work, and how you can implement them with confidence.

Arrays in C#

What is an Array?

An array is a fixed-size collection of elements, all of the same type, stored in contiguous memory locations. This structure allows constant-time access to any element using its index, making it very efficient for retrieval operations.

int[] numbers = new int[5];
string[] names = { "Alice", "Bob", "Charlie" };

Arrays in C# are zero-based, meaning the first element is at index 0. Once declared, the size of an array cannot change.

Common Operations

• Access: numbers[0] gives the first element
• Update: numbers[2] = 45;
• Iteration:

foreach (var number in numbers)
{
    Console.WriteLine(number);
}

When to Use Arrays

Use arrays when:

• You know the number of elements in advance
• You need fast access by index
• Insertions/deletions are rare

Pros and Cons

Pros	Cons
O(1) access time	Fixed size
Cache-friendly	Insertion and deletion are expensive
Simple syntax	Not flexible for dynamic data

Singly Linked List

What is a Linked List?

A singly linked list is a collection of nodes where each node contains data and a reference to the next node in the list. Unlike arrays, linked lists do not require contiguous memory, and elements can be easily added or removed.

[10 | *] → [20 | *] → [30 | null]

C# Implementation

public class Node
{
    public int Data;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

public class SinglyLinkedList
{
    public Node Head;

    public void AddLast(int data)
    {
        Node newNode = new Node(data);
        if (Head == null)
        {
            Head = newNode;
            return;
        }

        Node current = Head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }

    public void Print()
    {
        Node current = Head;
        while (current != null)
        {
            Console.Write(current.Data + " -> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }
}

When to Use Singly Linked List

• When frequent insertions/deletions are required
• When memory needs to be managed more flexibly

Time Complexity

• Access by index: O(n)
• Insert at head: O(1)
• Insert at end: O(n) without tail reference

Doubly Linked List

What is a Doubly Linked List?

In a doubly linked list, each node has two pointers: one to the next node and one to the previous node. This allows traversal in both directions.

null ← [10] ↔ [20] ↔ [30] → null

C# Implementation

public class DNode
{
    public int Data;
    public DNode Next;
    public DNode Prev;

    public DNode(int data)
    {
        Data = data;
    }
}

public class DoublyLinkedList
{
    public DNode Head;
    public DNode Tail;

    public void AddLast(int data)
    {
        var newNode = new DNode(data);
        if (Head == null)
        {
            Head = Tail = newNode;
            return;
        }

        Tail.Next = newNode;
        newNode.Prev = Tail;
        Tail = newNode;
    }

    public void PrintForward()
    {
        var current = Head;
        while (current != null)
        {
            Console.Write(current.Data + " <-> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }

    public void PrintBackward()
    {
        var current = Tail;
        while (current != null)
        {
            Console.Write(current.Data + " <-> ");
            current = current.Prev;
        }
        Console.WriteLine("null");
    }
}

When to Use Doubly Linked List

• When you need to traverse in both directions
• When quick deletions from both ends are necessary

Time Complexity

• Insert at head/tail: O(1)
• Delete node: O(1) if reference is known

Choosing Between Array, Singly and Doubly Linked List

Operation	Array	Singly Linked List	Doubly Linked List
Access by index	✅ O(1)	❌ O(n)	❌ O(n)
Insert/Delete at start	❌ O(n)	✅ O(1)	✅ O(1)
Insert/Delete at end	❌ O(n)	❌ O(n)	✅ O(1)
Bidirectional Traversal	❌	❌	✅

Practice Tasks

• Create a method to reverse a singly linked list.
• Add a method to delete a node by value in both singly and doubly linked lists.
• Convert an array to a singly linked list.
• Traverse a doubly linked list backward.
• Implement a generic LinkedList<T>.