C#实现双向链表

/// <summary>
    /// 双向链表节点类
    /// </summary>
    /// <typeparam name="T">节点中的存放的数据类型</typeparam>
    public class Node<T>
    {
        /// <summary>
        /// 当前节点的数据
        /// </summary>
        T data;
        /// <summary>
        /// 节点中存放的数据
        /// </summary>
        public T Data
        {
            get { return this.data; }
            set { this.data = value; }
        }
        /// <summary>
        /// 当前节点的下一个节点
        /// </summary>
        Node<T> next;
        /// <summary>
        /// 下一个节点
        /// </summary>
        public Node<T> Next
        {
            get { return this.next; }
            set { this.next = value; }
        }
        /// <summary>
        /// 当前节点的上一个节点
        /// </summary>
        Node<T> prev;
        /// <summary>
        /// 上一个节点
        /// </summary>
        public Node<T> Prev
        {
            get { return prev; }
            set { prev = value; }
        }
        /// <summary>
        /// 无参构造：数据为默认值，下一个节点为null，上一个节点也为null
        /// </summary>
        public Node()
        {
            this.data = default(T);
            this.next = null;
            this.prev = null;
        }
        /// <summary>
        /// 构造方法：数据为传过来的t，下一个节点为null，上一个节点也为null
        /// </summary>
        /// <param name="t">传入的元素值</param>
        public Node(T t)
        {
            this.data = t;
            this.next = null;
            this.prev = null;
        }
        /// <summary>
        /// 构造方法：数据为t，下一个节点为node
        /// </summary>
        /// <param name="t">传入的元素值</param>
        /// <param name="next">上一个节点</param>
        /// <param name="prev">下一个节点</param>
        public Node(T t, Node<T> next,Node<T> prev)
        {
            this.data = t;
            this.next = next;
            this.prev = prev;
        }


        /// <summary>
        /// 此方法在调试过程中使用，可以删掉
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            T p = this.prev == null ? default(T) : this.prev.data;
            T n = this.next == null ? default(T) : this.next.data;
            string s = string.Format("Data:{0},Prev:{1},Next:{2}",data,p,n);
            return s;
        }
    }
    /// <summary>
    /// 双向链表接口
    /// </summary>
    /// <typeparam name="T">链表中元素的类型</typeparam>
    public interface ILinkList<T>
    {
        void AddFirst(T t);
        void AddLast(T t);
        void Clear();
        int Count { get; }
        Node<T> Head { get; set; }
        Node<T> Tail { get;set;}
        void Insert(int index, T t);
        bool IsEmpty { get; }
        void RemoveAt(int index);
        void RemoveFirst();
        void RemoveLast();
        Node<T> this[int index] { get; }
    }




    /// <summary>
    /// 双向链表操作类
    /// </summary>
    /// <typeparam name="T">链表中元素的类型</typeparam>
    public class LinkList<T> : ILinkList<T>
    {
        /// <summary>
        /// 链表头节点
        /// </summary>
        Node<T> head;
        /// <summary>
        /// 链表头节点
        /// </summary>
        public Node<T> Head
        {
            get { return head; }
            set { head = value; }
        }
        /// <summary>
        /// 链表尾节点
        /// </summary>
        Node<T> tail;
        /// <summary>
        /// 链表尾节点
        /// </summary>
        public Node<T> Tail
        {
            get { return tail; }
            set { tail = value; }
        }
        /// <summary>
        /// 链表大小
        /// </summary>
        int size = 0;


        /// <summary>
        /// 添加节点到链表的开头
        /// </summary>
        /// <param name="t">要添加的数据</param>
        public void AddFirst(T t)
        {
            Node<T> node = new Node<T>(t);
            //如果头为null
            if (head == null)
            {
                //把头节点设置为node
                head = node;
                //因为是空链表，所以头尾一致
                tail = node;
                //大小加一
                size++;
                return;
            }
            //原来头节点的上一个为新节点
            head.Prev = node;
            //新节点的下一个为原来的头节点
            node.Next = head;
            //新头节点为新节点
            head = node;
            //大小加一
            size++;
        }


        /// <summary>
        /// 添加节点到链表的末尾
        /// </summary>
        /// <param name="t">要添加的数据</param>
        public void AddLast(T t)
        {
            Node<T> node = new Node<T>(t);
            //如果头为null
            if (head == null)
            {
                //把头节点设置为node
                head = node;
                //因为是空链表，所以头尾一致
                tail = node;
                //大小加一
                size++;
                return;
            }
            //将原尾节点的下一个设置为新节点
            tail.Next = node;
            //将新节点的上一个设置为原尾节点
            node.Prev = tail;
            //将尾节点重新设置为新节点
            tail = node;
            //大小加一
            size++;
        }
        /// <summary>
        /// 在给定的索引处插入数据
        /// </summary>
        /// <param name="index">索引</param>
        /// <param name="t">要插入的数据</param>
        public void Insert(int index, T t)
        {
            Node<T> node = new Node<T>(t);
            //索引过小
            if (index < 0)
            {
                throw new IndexOutOfRangeException();
            }
            //索引过大
            if (index >= Count)
            {
                throw new IndexOutOfRangeException();
            }
            //如果链表是空的，而且索引大于0
            if (IsEmpty && index > 0)
            {
                throw new IndexOutOfRangeException();
            }
            //如果索引为0，意味着向链表头部添加节点。
            if (index == 0)
            {
                AddFirst(t);
                return;
            }
            //要插入位置的节点
            Node<T> current = head;
            int i = 0;
            while (true)
            {
                if (i == index)
                {
                    break;
                }
                i++;
                current = current.Next;
            }
            //此处非常重要，特别要注意先后次序
            //当前节点的上一个的下一个设置为新节点
            current.Prev.Next = node;
            //新节点的上一个设置为当前节点的上一个
            node.Prev = current.Prev;
            //新节点的下一个设置为当前节点
            node.Next = current;
            //当前节点的上一个设置为新节点
            current.Prev = node;
            //大小加一
            size++;
        }
        /// <summary>
        /// 移除链表中的节点
        /// </summary>
        /// <param name="index">要移除的节点的索引</param>
        public void RemoveAt(int index)
        {
            //链表头节点是空的
            if (IsEmpty)
            {
                throw new Exception("链表是空的。");
            }
            //索引过小
            if (index < 0)
            {
                throw new IndexOutOfRangeException();
            }
            //索引过大
            if (index >= Count)
            {
                throw new IndexOutOfRangeException();
            }
            //如果要移除的是头节点
            if (index == 0)
            {
                RemoveFirst();
                return;
            }
            if (index==size-1)
            {
                RemoveLast();
                return;
            }
            //要移除的节点
            Node<T> current = head;
            int i = 0;
            while (true)
            {
                if (i == index)
                {
                    break;
                }
                i++;
                current = current.Next;
            }
            //当前节点的上一个的Next设置为当前节点的Next
            current.Prev.Next = current.Next;
            //当前节点的下一个的Prev设置为当前节点的Prev
            current.Next.Prev = current.Prev;
            //大小减一
            size--;
        }
        /// <summary>
        /// 移除头节点
        /// </summary>
        public void RemoveFirst()
        {
            //链表头节点是空的
            if (IsEmpty)
            {
                throw new Exception("链表是空的。");
            }
            //如果size为1，那就是清空链表。
            if (size==1)
            {
                Clear();
                return;
            }
            //将头节点设为原头结点的下一个节点，就是下一个节点上移
            head = head.Next;
            //处理上一步遗留问题，原来的第二个节点的上一个是头结点，现在第二个要变成头节点，那要把它的Prev设为null才能成为头节点
            head.Prev = null;
            //大小减一
            size--;
        }
        /// <summary>
        /// 移除尾节点
        /// </summary>
        public void RemoveLast()
        {
            //链表头节点是空的
            if (IsEmpty)
            {
                throw new Exception("链表是空的。");
            }
            //如果size为1，那就是清空链表。
            if (size == 1)
            {
                Clear();
                return;
            }
            //尾节点设置为倒数第二个节点
            tail = tail.Prev;
            //将新尾节点的Next设为null，表示它是新的尾节点
            tail.Next = null;
            //大小减一
            size--;
        }
        /// <summary>
        /// 判断链表是否是空的
        /// </summary>
        public bool IsEmpty
        {
            get
            {
                return head == null;
            }
        }
        /// <summary>
        /// 链表中元素的个数
        /// </summary>
        public int Count
        {
            get
            {
                ////也可以采用遍历的方法获得长度，遍历可以从前向后，也可以从后向前
                //int count = 0;
                ////取得链表头部节点
                //Node<T> current = new Node<T>();
                //current = head;
                ////遍历整个链表，直到最后一个Next为null的节点为止
                //while (current!=null)
                //{
                //    count++;
                //    current = current.Next;
                //}
                //return count;
                return size;
            }
        }
        /// <summary>
        /// 清除链表中的数据
        /// </summary>
        public void Clear()
        {
            head = null;
            tail = null;
            size = 0;
        }
        /// <summary>
        /// 根据索引获取链表中的节点
        /// </summary>
        /// <param name="index">整型索引</param>
        /// <returns>节点</returns>
        public Node<T> this[int index]
        {
            get
            {
                //链表头节点是空的
                if (head == null)
                {
                    throw new Exception("链表是空的。");
                }
                //索引过小
                if (index < 0)
                {
                    throw new IndexOutOfRangeException();
                }
                //索引过大
                if (index >= Count)
                {
                    throw new IndexOutOfRangeException();
                }
                //取得头节点
                Node<T> current = new Node<T>();
                //如果索引在前一半，那么从前向后找
                if (index<size/2)
                {
                    current = head;
                    int i = 0;
                    //遍历链表
                    while (true)
                    {
                        //找到第index个节点
                        if (i == index)
                        {
                            break;
                        }
                        current = current.Next;
                        i++;
                    }
                    return current;
                }
                else//如果索引在后一半，那么从后向前找
                {
                    current = tail;
                    int i = size;
                    //遍历链表
                    while (true)
                    {
                        //找到第index个节点
                        if (i == index)
                        {
                            break;
                        }
                        current = current.Prev;
                        i--;
                    }
                    return current.Next;
                }
            }
        }
    }