[자료구조] DoubleLinkedList

// DoubleLinkedList

public class LinkedList<T>
{
    // Dump - node - node - Dump

    public LinkedList() 
    {
        size = 0;
        T data = default(T);
        Node<T> dumpNode = new Node<T>(data);
        head = tail = dumpNode;
        head.next = tail;
        tail.prev = head;
    }

    public Node<T> FirstInsert(T data)
    {
        Node<T> newNode = new Node<T>(data);

        if(head.next == tail)
        {
            head.next = tail.prev = newNode;
            newNode.prev = head;
            newNode.next = tail;
        }
        else
        {
            Node<T> rightNode = head.next;
            head.next = newNode;
            newNode.prev = head;
            newNode.next = rightNode;
            rightNode.prev = newNode;
        }

        size++;
        return newNode;
    }

    public Node<T> LastInsert(T data)
    {
        Node<T> newNode = new Node<T>(data);

        if (tail.prev == head)
        {
            head.next = tail.prev = newNode;
            newNode.prev = head;
            newNode.next = tail;
        }
        else
        {
            Node<T> leftNode = tail.prev;
            tail.prev = newNode;
            newNode.next = tail;
            newNode.prev = leftNode;
            leftNode.next = newNode;
        }

        size++;
        return newNode;
    }

    public Node<T> Insert(Node<T> node, T data)
    {
        if (node == null)
            return null;

        Node<T> newNode = new Node<T>(data);

        Node<T> rightNode = node.next;

        newNode.next = rightNode;
        rightNode.prev = newNode;

        newNode.prev = node;
        node.next = newNode;

        size++;
        return newNode;
    }

    public void FirstRemove()
    {
        if (size == 0)
            return;

        Node<T> removeNode = head.next;
        Node<T> rightNode = removeNode.next;

        if(rightNode == tail)
        {
            head.next = tail;
            tail.prev = head;
        }
        else
        {
            rightNode.prev = head;
            head.next = rightNode;
        }

        removeNode = null;
        size--;
    }

    public void LastRemove()
    {
        if (size == 0)
            return;

        Node<T> removeNode = tail.prev;
        Node<T> leftNode = removeNode.prev;

        if (leftNode == head)
        {
            head.next = tail;
            tail.prev = head;
        }
        else
        {
            leftNode.next = tail;
            tail.prev = leftNode;
        }

        removeNode = null;
        size--;
    }

    public void Remove(Node<T> node)
    {
        if (size == 0)
            return;

        Node<T> leftNode = node.prev;
        Node<T> rightNode = node.next;

        leftNode.next = rightNode;
        rightNode.prev = leftNode;

        node = null;
        size--;
    }

    public Node<T> FirstPeek()
    {
        if (head.next == tail)
            return null;

        return head.next;
    }

    public Node<T> LastPeek()
    {
        if (tail.prev == head)
            return null;

        return tail.prev;
    }

    public void PrintLinkedList()
    {
        for (Node<T> node = head.next; node != tail; node = node.next)
            Console.Write($"{node.data} -> ");
        Console.WriteLine();
    }

    int size;
    Node<T> head;
    Node<T> tail;
}

public class Node<T>
{
    public Node(T value)
    {
        data = value;
        prev = next = null;
    }

    public T data { get; set; }
    public Node<T> prev { get; set; }
    public Node<T> next { get; set; }
}