using System;

public class Program

{

    public static void Main()

    {

        listNode head = new listNode { Value = 1 };

        // add sentinal

        // both below methods produce identical results

        head = AddSentinalToHead(head);

        //AddSentinalToHead(head);

        listNode tail = AddSentinalToTail(head);

        // add additional nodes to the start

        AddNodeToStart(head, 2);

        AddNodeToStart(head, 3);

        AddNodeToStart(head, 4);

        // add additional nodes to the end

        AddNodeToEnd(tail, 5);

        AddNodeToEnd(tail, 6);

        AddNodeToEnd(tail, 7);

        //Console.WriteLine(head.Value);

        // print all node values 

        while (head.Next != null && head.Next != tail) {

            Console.WriteLine(head.Next.Value);

            head = head.Next;

        }

    }

    public class listNode

    {

        public int Value { get; set; }

        public listNode Next { get; set; }

        public listNode Prev { get; set; }

    }

    // Adds null value pointer node to start of the list

    public static listNode AddSentinalToHead(listNode head)

    {

        listNode newNode = new listNode { Next = head };

        head.Prev = newNode;

        return newNode;

    }

    // Adds null value pointer node to start of the list

    public static void AddSentinalToHead(ref listNode head)

    {

        listNode newNode = new listNode { Next = head };

        head.Prev = newNode;

        head = newNode;

    }

    // Adds null value pointer node to start of the list

    public static listNode AddSentinalToTail(listNode head)

    {

        listNode newNode = new listNode();

        while (head.Next != null)

            head = head.Next;

        head.Next = newNode;

        newNode.Prev = head;

        return newNode;

    }

    // Adds new node to start of list

    public static void AddNodeToStart(listNode head, int val)

    {

        listNode newNode = new listNode { Value = val };

        newNode.Next = head.Next;

        head.Next = newNode;

        newNode.Next.Prev = newNode;

        newNode.Prev = head;

    }

    // Adds new node to end of list

    public static void AddNodeToEnd(listNode tail, int val)

    {

        listNode newNode = new listNode { Value = val };

        newNode.Prev = tail.Prev;

        tail.Prev = newNode;

        newNode.Prev.Next = newNode;

        newNode.Next = tail;

    }

    // Add new node after node passed in argument

    public static void AddNodeAfter(listNode node, int val)

    {

        listNode newNode = new listNode { Value = val };

        newNode.Next = node.Next;

        node.Next = newNode;

        newNode.Next.Prev = newNode;

        newNode.Prev = node;

    }

    // Adds new node before node passed in argument

    public static void AddNodeBefore(listNode node, int val)

    {

        listNode newNode = new listNode { Value = val };

        newNode.Prev = node.Prev;

        node.Prev = newNode;

        newNode.Prev.Next = newNode;

        newNode.Next = node;

    }

    // Removes node after node passed in argument

    public static void DeleteNodeAfter(listNode node)

    {

        if (node.Next != null) {

            node.Next = node.Next.Next;

            if (node.Next != null)

                node.Next.Prev = node;

        }

    }

    // Removes node before node passed in argument

    public static void DeleteNodeBefore(listNode node)

    {

        if (node.Prev != null) {

            node.Prev = node.Prev.Prev;

            if (node.Prev != null)

                node.Prev.Next = node;

        }

    }

    // Returns node with matching value or null if none exist

    public static listNode FindNodeByValue(listNode head, int val)

    {

        while (head.Next != null)

        {

            if (head.Next.Value == val)

                return head.Next;

            head = head.Next;

        }

        return null;

    }

    // Returns node that comes before node with matching value or null if none exist

    public static listNode FindPrevNodeByValue(listNode head, int val)

    {

        while (head.Next != null)

        {

            if (head.Next.Value == val)

                return head;

            head = head.Next;

        }

        return null;

    }

}