707.Design Linked List

📘 LeetCode 707: Design Linked List

📌 Problem Overview

• Problem Number: 707
• Problem Name: Design Linked List
• Difficulty: Medium
• Category: Linked List
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Linked List algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/707-Design-Linked-List/:

LinkedList list = new LinkedList();
list.Add(1);
list.Add(2);
list.Add(3);
list.ToString();
list.Delete(0);
list.ToString();
 
class Node(int data)
{
    public Node Next { get; set; }
    public int Value { get; set; } = data;
}
 
class LinkedList
{
    private Node _head;
    private int count = 0;
    public void Add(int value)
    {
        Node newNode = new Node(value);
        if (_head == null)
        {
            _head = newNode;
        }
        else
        {
            Node current = _head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
        count++;
    }
 
    public void Delete(int index)
    {
        if (index < 0 || index > count) return;
        if (index == 0)
        {
            _head = _head.Next;
        }
        else
        {
            Node current = _head;
            int i = index - 1;
            while (i > 0)
            // for (int i = 0; i < index - 1; i++)
            {
                current = current.Next;
                i--;
            }
            current.Next = current.Next?.Next;
        }
        count--;
    }
 
    public void ToString()
    {
        Node current = _head;
        string result = "";
        while (current != null)
        {
            result += current.Value.ToString();
            if (current.Next != null)
            {
                result += " > ";
            }
            current = current.Next;
        }
        System.Console.WriteLine(result);
    }
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.