public class DoublyLinkedList<T> : ICloneable, IEnumerable where T : ICloneable
{
    private class Node<U>
    {
        public U Value;
        public Node<U> Next;
        public Node<U> Prev;

        public Node(U value, Node<U> next, Node<U> prev)
        {
            Value = value;
            Next = next;
            Prev = prev;
        }

        /// <summary>
        /// Adds a node after this node, then returns the newly created node
        /// </summary>
        /// <param name="value">value to go into the node</param>
        /// <returns>the newly created Node object</returns>
        public Node<U> AddNodeAfter(U value)
        {
            var newNode = new Node<U>(value, this.Next, this);
            Next = newNode;
            return newNode;
        }

        /// <summary>
        /// Adds a node before this node, then returns the newly created node
        /// </summary>
        /// <param name="value">value to go into the node</param>
        /// <returns>the newly created Node object</returns>
        public Node<U> AddNodeBefore(U value)
        {
            var newNode = new Node<U>(value, this, this.Prev);
            Prev = newNode;
            return newNode;
        }
    }

    private Node<T> head;
    private Node<T> tail;

    public DoublyLinkedList()
    {
        head = null;
        tail = null;
    }

    // copy constructor
    public DoublyLinkedList(DoublyLinkedList<T> list)
    {
        head = list.head;
        if (head == null)
        {
            tail = null;
            return;
        }

        var position = head;
        while (position.Next != null)
        {
            position.Next = new Node<T>((T) position.Next.Value.Clone(), position.Next.Next, position.Next.Prev);
            position = position.Next;
        }
        tail = position;
    }

    public void Append(T value)
    {
        if (tail == null)
        {
            head = tail = new Node<T>(value, null, null);
        }
        else
        {
            var newNode = tail.AddNodeAfter(value);
            tail.Next = newNode;
            tail = newNode;
        }
    }

    public void Prepend(T value)
    {
        if (tail == null)
        {
            head = tail = new Node<T>(value, null, null);
        }
        else
        {
            var newNode = head.AddNodeBefore(value);
            head = newNode;
        }
    }

    public object Clone()
    {
        return new DoublyLinkedList<T>(this);
    }

    // basically like an iterator
    public IEnumerator<T> GetEnumerator()
    {
        // This is C# syntax... not sure if Java has "yield return"
        var node = head;
        while (node != null)
        {
            yield return node.Value;
            node = node.Next;
        }
    }

    // C# likes to be pedantic about this... this doesn't really matter but I need it to
    // officially "implement" IEnumerable
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    // "new" is pedantic, but I wanted to remove the compiler warning.
    public new string ToString()
    {
        var builder = new StringBuilder();
        builder.Append("[ ");
        foreach (var value in this)
        {
            builder.Append(value);
            builder.Append(" ");
        }
        builder.Append("]");
        return builder.ToString();
    }
}