C#实现双链表（线性表）

双链表同单链表的不同在于结点类增加了一个“前驱结点”属性，此外，给双链表增加一个“尾结点”的属性。在获取某一结点对象时，双链表同单链表几乎没有区别，函数同单链表相似。但在添加结点、插入结点、删除结点、倒序排列等功能上不同。

其中，由于双链表有尾结点属性，在末尾添加结点会更加方便，时间复杂度为O(1)，而单链表时间复杂度为O(n)。

插入结点、删除结点的原理与单链表的相关操作相似，只是增加前驱结点的设置。删除结点时，由于被删除结点的前驱和后继都设置为null，引用数目为0，GC会自动回收资源。

在这里，要求链表的头结点的前驱结点为null，这既符合常理，另外，如果不设置为null，则前驱结点仍有引用，GC无法自动回收，造成额外开销。

双链表的接口定义：

    public interface IListDS<T>
    {
        int GetLength();
        void Insert(T item, int i);
        void Add(T item);
        bool IsEmpty();
        T GetElement(int i);
        void Delete(int i);
        void Clear();
        int LocateElement(T item);
        void Reverse();
    }

双链表的节点类：

    class DbNode<T>
    {
        private T tData;
        private DbNode<T> nNext;//后继
        private DbNode<T> nPrevious;//前驱
        public T Data
        {
            get { return this.tData; }
            set { this.tData = value; }
        }
        public DbNode<T> Next
        {
            get { return this.nNext; }
            set { this.nNext = value; }
        }
        public DbNode<T> Prev
        {
            get { return this.nPrevious; }
            set { this.nPrevious = value; }
        }
        //构造函数
        public DbNode()
        {
            this.nNext = null;
            this.nPrevious = null;
        }
        public DbNode(T data)
        {
            this.Data = data;
            this.nNext = null;
            this.nPrevious = null;
        }
        public DbNode(T data,DbNode<T> next)
        {
            this.Data = data;
            this.nNext = next;
            this.nPrevious = null;
        }
        public DbNode(T data, DbNode<T> next,DbNode<T> prev)
        {
            this.Data = data;
            this.nNext = next;
            this.nPrevious = prev;
        }
    }

双链表类：

    class DbLinkedList<T>:IListDS<T>
    {
        private DbNode<T> nHead;
        private DbNode<T> nTail;//既然DbNode有前驱属性，则双向链表也最好要有一个尾结点
        public DbNode<T> Head
        {
            get { return this.nHead; }
            set { this.nHead = value; }
        }
        public DbNode<T> Tail
        {
            get { return this.nTail; }
            set { this.nTail = value; }
        }
        //构造函数
        public DbLinkedList()
        {
            this.nHead = null;
            this.nTail = null;
        }
        
        //之所以规定head必须没有前驱结点才可以做为双链表的头结点，是因为
        //如果有前驱的话，这些前驱对该双链表是多余的，而且由于head对这些前驱仍有引用，所以GC
        //不会自动回收，造成额外的内存开销。另外，既然是头结点，前驱理应为null
        public DbLinkedList(DbNode<T> head)
        {
            this.nHead = head;
            this.nTail = head;
            this.nTail.Next = null;
            this.nHead.Prev = null;
        }
        #region IListDS<T> 成员
        public int GetLength()
        {
            //同单链表
        }
        public void Insert(T item, int i)
        {
            //同单链表相同，想从后面计数再插入是徒劳，因为计数就要全循环所有结点
        }
        public void Add(T item)
        {
            //爽链表的Add较单链表优势明显，无需循环到尾结点，而是可以直接获取尾结点
            DbNode<T> node = new DbNode<T>(item);
            node.Prev = this.Tail;
            this.Tail.Next = node;
            this.Tail = node;
        }
        public bool IsEmpty()
        {
            return this.nHead == null;
        }
        public T GetElement(int i)
        {
            //同单链表相似
        }
        public void Delete(int i)
        {
            if (i < 1 || i > this.GetLength())
            {
                Console.WriteLine("位置错误！");
                return;
            }
            else
            {
                if (this.GetLength() == 1)
                {
                    this.nHead = null;
                    this.nTail = null;
                    return;
                }
                if (i == 1)
                {
                    DbNode<T> node = this.nHead;
                    this.nHead = this.nHead.Next;
                    node.Next = null;
                    this.nHead.Prev = null;
                    return;
                }
                if (i == this.GetLength())
                {
                    DbNode<T> node = this.nTail.Prev;
                    node.Next = null;
                    this.nTail.Prev = null;//取消引用
                    this.nTail = node;
                    return;
                }
                DbNode<T> node = this.GetElement(i);
                node.Next.Prev = node.Prev;
                node.Prev.Next = node.Next;
            }
        }
        public void Clear()
        {
            this.nHead = null;
            this.nTail = null;
        }
        public int LocateElement(T item)
        {
            //同单链表相似
        }
        public void Reverse()
        {
            if (this.GetLength() == 1)
            {
                //不变
                return;
            }
            //if (this.GetLength == 2)
            //{
            //    DbNode<T> tmp = new DbNode<T>();
               
            //    tmp = this.nTail;
            //    this.nTail = this.nHead;
            //    this.nHead = tmp;
            //    this.nHead.Prev = null;
            //    this.nHead.Next = this.nTail;
            //    this.nTail.Prev = this.nHead;
            //    this.nTail.Next = null;
            //    return;
            //}
            DbNode<T> node1 = this.nHead;
            DbNode<T> node2 = node1.Next;
            DbNode<T> node3 = node2.Next;
            while (node3 != null)//如果length=2时，这个循环不执行
            {
                node2.Next = this.nHead;
                this.nHead.Prev = node2;
                node2.Prev = null;
                
                node1.Next = node3;
                node3.Prev = node2;
                this.nHead = node2;
                node2 = node1.Next;
                node3 = node2.Next;
            }
            node2.Next = this.nHead;//最后一定会循环到node3=null
            node2.Prev = null;
            this.nHead = node2;
            node1.Next = null;
            this.nTail = node1;
        }
        #endregion
    }