using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/**
 * 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
 * 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
 * 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
 * 相比于线性表顺序结构，操作复杂。
 * **/
namespace NETTest
{
    public class NodeTable
    {
    }

    /// <summary>
    /// 这个类仅包含一个表示员工名字的字符串类型，一个设置员工名字的构造函数，一个返回Employee名字的ToString()方法。
    /// </summary>
    public class Employee
    {
        private string name;
        public Employee(string name)
        {
            this.name = name;
        }

        public override string ToString()
        {
            return this.name;
        }
    }

    public class Node<T>
    {
        Object data;
        Node<T> next;

        //注意构造函数将私有的数据成员设置成传递进来的对象，并且将 next 字段设置成null。
        public Node(Object data)
        {
            this.data = data;
            this.next = null;
        }

        public Object Data
        {
            get { return this.data; }
            set { data = value; }
        }

        public Node<T> Next
        {
            get { return this.next; }
            set { this.next = value; }
        }


        /// <summary>
        /// 首先检测当前Node的next字段，看它是不是null。
        /// 如果是，那么当前Node就是最后一个Node，我们将当前Node的next属性指向传递进来的新结点，
        /// 这样，我们就把新Node插入到了链表的尾部。
        /// 如果当前Node的next字段不是null，说明当前node不是链表中的最后一个node。
        /// 因为next字段的类型也是node，所以我们调用next字段的Append方法(注：递归调用)，再一次传递Node参数，这样继续下去，直到找到最后一个Node为止。
        /// </summary>
        /// <param name="newNode"></param>
        public void Append(Node<T> newNode)
        {
            if (this.next == null)
            {
                this.next = newNode;
            }
            else
            {
                next.Append(newNode);
            }
        }

        /// <summary>
        /// Node 类中的 ToString() 方法也被覆盖了，用于输出 data 中的值，并且调用下一个 Node 的 ToString()方法(译注：再一次递归调用)。
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            string output = data.ToString();

            if (next != null)
            {
                output += ", " + next.ToString();
            }

            return output;
        }
    }

    /**
     * LinkedList 类本身只包含对一个Node的引用，这个Node称作 HeadNode，是链表中的第一个Node，初始化为null。
     * **/
    public class LinkedList<T>
    {
        Node<T> headNode = null;

        /// <summary>
        /// LinkedList 类不需要构造函数(使用编译器创建的默认构造函数)，
        /// 但是我们需要创建一个公共方法，Add()，这个方法把 data存储到线性链表中。
        /// 这个方法首先检查headNode是不是null，
        /// 如果是，它将使用data创建结点，并将这个结点作为headNode，
        /// 如果不是null，它将创建一个新的包含data的结点，并调用headNode的Append方法
        /