/** Initialize your data structure here. */
public MyLinkedList() {
    
    Console.WriteLine("Now instantiating linked list with an empty Head node.");
    
    this.Head = null;
    this.Length = 0;
}

public Node Head {get; set;}
public int Length {get; set;}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int Get(int index) {
    
    Console.WriteLine("getting value at index: " + index);
    Console.WriteLine("current length of linked list: " + this.Length);
    
    if(index > (this.Length - 1) || index < 0) return -1;
    
    return GetNode(index).Val;
}

/** Get the node at the specified index in the linked list. Helper Method */
private Node GetNode(int index) {
    
    if(index < 0) return null;
    
    int curIndex = 0;
    Node curNode = this.Head;
    
    //traverse through linked list until we approach our proper node at index passed in
    while (curIndex < index)
    {
        curNode = curNode.Next;
        curIndex++;
    }
    
    return curNode;
}

private string PrintLinkedList() {
    
    Console.WriteLine("Now printing linked list.");
    
    string stringifiedLinkedList = "";
    Node curNode = this.Head;
    int curIndex = 0;
    
    while(curNode != null)
    {
        stringifiedLinkedList = stringifiedLinkedList + curNode.Val + ", ";
        curIndex += 1;
        curNode = curNode.Next;
    }
    
    return stringifiedLinkedList;
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void AddAtHead(int val) {
    
    Console.WriteLine("Now adding a node at the head of linked list with value of: " + val);
    
    Node newNode = new Node{
        Val = val,
        Next = this.Head
    };
    
    this.Head = newNode;
    this.Length += 1;
    
    Console.WriteLine(this.PrintLinkedList());
    
}

/** Append a node of value val to the last element of the linked list. */
public void AddAtTail(int val) {
    
    Console.WriteLine("Now adding a node at the tail of linked list with value of: " + val);
    
    Node curNode = this.Head;
    
    if(curNode == null) Console.WriteLine("curNode is null, therefore we are adding tail on an empty linked list");
    else Console.WriteLine("head node value: " + curNode.Val);
    
    while(curNode != null && curNode.Next != null)
    {
        curNode = curNode.Next;
    }
    
    if(curNode == null) {
        
        this.Head = new Node{
            Val = val,
            Next = null
        };
    }
    else
    {
        curNode.Next = new Node{
            Val = val,
            Next = null
        };
    
    }
    

    this.Length += 1;
    
    //Console.WriteLine("New Tail node: " + curNode.Next.Val);
    
    Console.WriteLine(this.PrintLinkedList());
}



/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void AddAtIndex(int index, int val) {
    
    Console.WriteLine("Now adding at index " + index + " with a value: " + val);
    
    if(index == 0)
    {
        Node newNode = new Node{
            Val = val,
            Next = this.Head
        };
        
        this.Head = newNode;
    }
    else
    {
        Node prevNode = GetNode(index - 1);
        Node nextNode = prevNode.Next;
    
        Node newNode = new Node{
            Val = val,
            Next = nextNode
        };
    
        prevNode.Next = newNode;
    }
    

    
    this.Length += 1;
    
    Console.WriteLine(this.PrintLinkedList());
}

/** Delete the index-th node in the linked list, if the index is valid. */
public void DeleteAtIndex(int index) {
    
    Console.WriteLine("Now deleting at index: " + index);
    
    Node prevNode = null;
    Node toDelete = null;
    Node toJoin = null;
    
    prevNode = GetNode(index - 1);
    
    //handle where there is no prevIndex - meaning it's index zero and we simply need to point the new                 this.Head to toDelete.Next
    if(prevNode == null)
    {
        Console.WriteLine("No previous node, deleting the first index");
        
        toDelete = GetNode(index);
        
        Console.WriteLine("toDelete value: " + toDelete.Val);
        
        if(toDelete != null)
        {
            this.Head = toDelete.Next;
        }
        
        this.Length -= 1;
    }
    //handle where there is a prevNode - in this case we point prevNode.Next = toJoin
    else
    {
        toDelete = prevNode.Next;
        
        if(toDelete != null)
        {
            toJoin = toDelete.Next;
            
            //if no toDelete.Next - then prevNode.Next = null
            if(toDelete.Next == null) prevNode.Next = null;
            //else prevNode.Next = toJoin
            else prevNode.Next = toJoin;
        }
        
        this.Length -= 1;
    }
    
    Console.WriteLine(this.PrintLinkedList());
}

//Each node contains a value and a pointer to the next node in the singly linked list
public class Node {
    
    public int Val {get; set;}
    
    public Node Next {get; set;}
}