[자료구조] Double Linked List (C#)

using UnityEngine;

public class DoubleLinkedList
{
    private class Node
    {
        public string data;
        public Node prev;
        public Node next;

        public Node(string data)
        {
            this.data = data;
            prev = null;
            next = null;
        }
    }

    public int Length { get; private set; }
    private Node head;
    private Node tail;

    public DoubleLinkedList()
    {
        Length = 0;
        head = null;
        tail = null;
    }

    public void Append(string data)
    {
        Node newNode = new Node(data);
        Length++;

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

    public int Remove(string value)
    {
        if (Length == 0)
        {
            return -1;
        }
        else if (Length == 1)
        {
            if (IsIncluded(value) == true)
            {
                head = null;
                tail = null;
                Length--;
                return 0;
            }
            else
            {
                return -1;
            }
        }
        else //if Length >= 2
        {
            Node current = head;
            for (int i = 0; i < Length; i++)
            {
                if (current.data == value)
                {
                    if (current == head)
                    {
                        head.next.prev = null;
                        head = head.next;
                        Length--;
                        return 0;
                    }
                    else if (current == tail)
                    {
                        tail.prev.next = null;
                        tail = tail.prev;
                        Length--;
                        return 0;
                    }
                    else
                    {
                        current.next.prev = current.prev;
                        current.prev.next = current.next;
                        Length--;
                        return 0;
                    }
                }
                current = current.next;
            }
            return -1;
        }
    }

    public void Clear() // == RemoveAll()
    {
        // 어짜피 Garbage Collector 때문에 굳이 free를 안 해줘도 다 지워질 운명임.
        Length = 0;
        head = null;
        tail = null;
    }

    public int Insert(string data, int index) // == InsertAfter
    {
        if (index < 0 || index >= Length) // index : 0 ~ (Length - 1), Length >= 1
        {
            return -1;
        }
        else
        {
            Node newNode = new Node(data);
            if (index == 0) // insert after head
            {
                if (head.next == null)
                {
                    Append(data);
                    return 0;
                }
                else
                {
                    newNode.next = head.next;
                    head.next.prev = newNode;
                    head.next = newNode;
                    newNode.prev = head;
                    Length++;
                    return 0;
                }
            }
            else if (index == Length - 1) // insert after tail
            {
                Append(data);
                return 0;
            }
            else // insert at middle
            {
                Node current = head;
                for (int i = 0; i < index; i++)
                {
                    current = current.next;
                }
                newNode.next = current.next;
                current.next.prev = newNode;
                current.next = newNode;
                newNode.prev = current;
                Length++;
                return 0;
            }
        }
    }

    public int Replace(int index, string value)
    {
        if (Length == 0 || index < 0 || index >= Length)
        {
            return -1;
        }
        else 
        {
            Node current = head;
            for (int i = 0; i < index; i++)
            {
                current = current.next;
            }
            current.data = value;
            return 0;
        }
    }

    public string GetData(int index)
    {
        if (Length == 0 || index < 0 || index >= Length)
        {
            return "null";
        }
        else
        {
            Node current = head;
            for (int i = 0; i < index; i++)
            {
                current = current.next;
            }
            return current.data;
        }
    }

    public int GetIndex(string value)
    {
        Node current = head;
        for (int i = 0; i < Length; i++)
        {
            if (current.data == value)
            {
                return i;
            }
            current = current.next;
        }
        return -1;
    }

    // GetLength는 필요없음. 왜냐하면 { get; private set; }을 통해 밖에서도 보이는 값으로 만들어놨기 때문.

    public bool IsIncluded(string value)
    {
        Node current = head;
        for (int i = 0; i < Length; i++)
        {
            if (current.data == value)
            {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public void PrintList()
    {
        Node current = head;
        for (int i = 0; i < Length; i++)
        {
            Debug.Log(current.data);
            current = current.next;
        }
    }
}