C#实现双向链表

原文:http://www.cnblogs.com/skywang12345/p/3561803.html\#a33
没有C#本子的。。是未是格外在。。不过图和说明很好,引用一下

双向链表

双向链表(双链表)是链表的平等栽。和单链表一样,双链表也是由于节点组成,它的每个数据结点中还出些许个指针,分别指向直接后继和直接前驱。所以,从对通往链表中之妄动一个结点开始,都足以充分便利地看它的先驱者结点和晚结点。一般我们都组织双向循环链表。

双双链表的示意图如下:

图片 1

表头为空,表头的后继节点为”节点10″(数据也10底节点);”节点10″的后继节点是”节点20″(数据吧10之节点),”节点20″的前继节点是”节点10″;”节点20″的后继节点是”节点30″,”节点30″的前继节点是”节点20″;…;末尾节点的后继节点是表头。

双链表删除节点

图片 2

删除”节点30″
去之前:”节点20″的后继节点为”节点30″,”节点30″
的前继节点也”节点20″。”节点30″的后继节点为”节点40″,”节点40″
的前继节点也”节点30″。
去后:”节点20″的后继节点为”节点40″,”节点40″
的前继节点吧”节点20″。

 偶链表添加节点

 图片 3

当”节点10″与”节点20″之间添加”节点15″
累加之前:”节点10″的后继节点为”节点20″,”节点20″
的前继节点也”节点10″。
长后:”节点10″的后继节点为”节点15″,”节点15″
的前继节点吧”节点10″。”节点15″的后继节点为”节点20″,”节点20″
的前继节点吧”节点15″。

代码

    /// <summary>
    /// 双向链表节点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BdNode<T>
    {
        public T Data { set; get; }
        public BdNode<T> Next { set; get; } 
        public BdNode<T> Prev { set; get; } 
        public BdNode(T val, BdNode<T> prev, BdNode<T> next)
        {
            this.Data = val;
            this.Prev = prev;
            this.Next = next;
        }
    }

链表操作:

 public class DoubleLink<T>
    {
        //表头
        private readonly BdNode<T> _linkHead;
        //节点个数
        private int _size;
        public DoubleLink()
        {
            _linkHead = new BdNode<T>(default(T), null, null);//双向链表 表头为空
            _linkHead.Prev = _linkHead;
            _linkHead.Next = _linkHead;
            _size = 0;
        }
        public int GetSize() => _size;
        public bool IsEmpty() => (_size == 0);
        //通过索引查找
        private BdNode<T> GetNode(int index)
        {
            if (index < 0 || index >= _size)
                throw new IndexOutOfRangeException("索引溢出或者链表为空");
            if (index < _size / 2)//正向查找
            {
                BdNode<T> node = _linkHead.Next;
                for (int i = 0; i < index; i++)
                    node = node.Next;
                return node;
            }
            //反向查找
            BdNode<T> rnode = _linkHead.Prev;
            int rindex = _size - index - 1;
            for (int i = 0; i < rindex; i++)
                rnode = rnode.Prev;
            return rnode;
        }
        public T Get(int index) => GetNode(index).Data;
        public T GetFirst() => GetNode(0).Data;
        public T GetLast() => GetNode(_size - 1).Data;
        // 将节点插入到第index位置之前
        public void Insert(int index, T t)
        {
            if (_size < 1 || index >= _size)
                throw new Exception("没有可插入的点或者索引溢出了");
            if (index == 0)
                Append(_size, t);
            else
            {
                BdNode<T> inode = GetNode(index);
                BdNode<T> tnode = new BdNode<T>(t, inode.Prev, inode);
                inode.Prev.Next = tnode;
                inode.Prev = tnode;
                _size++;
            }
        }
        //追加到index位置之后
        public void Append(int index, T t)
        {
            BdNode<T> inode;
            if (index == 0)
                inode = _linkHead;
            else
            {
                index = index - 1;
                if (index < 0)
                    throw new IndexOutOfRangeException("位置不存在");
                inode = GetNode(index);
            }
            BdNode<T> tnode = new BdNode<T>(t, inode, inode.Next);
            inode.Next.Prev = tnode;
            inode.Next = tnode;
            _size++;
        }
        public void Del(int index)
        {
            BdNode<T> inode = GetNode(index);
            inode.Prev.Next = inode.Next;
            inode.Next.Prev = inode.Prev;
            _size--;
        }
        public void DelFirst() => Del(0);
        public void DelLast() => Del(_size - 1); 
        public void ShowAll()
        {
            Console.WriteLine("******************* 链表数据如下 *******************");
            for (int i = 0; i < _size; i++)
                Console.WriteLine("(" + i + ")=" + Get(i));
            Console.WriteLine("******************* 链表数据展示完毕 *******************\n");
        }
    }

测试:

DoubleLink<int> dlink = new DoubleLink<int>();// 创建双向链表
            Console.WriteLine("将 20 插入到表头之后");
            dlink.Append(0, 10);   
            dlink.ShowAll();
            Console.WriteLine("将 40 插入到表头之后");
            dlink.Append(1, 30);   
            dlink.ShowAll();
            Console.WriteLine("将 10 插入到表头之前");
            dlink.Insert(0, 40);  
            dlink.ShowAll();
            Console.WriteLine("将 30 插入到第一个位置之前");
            dlink.Insert(1, 20);     
            dlink.ShowAll();
            Console.WriteLine("展示第一个:" + dlink.GetFirst()); 
            Console.WriteLine("删除第一个");
            dlink.DelFirst();
            Console.WriteLine("展示第一个:" + dlink.GetFirst());
            Console.WriteLine("展示最后一个:" + dlink.GetLast());
            Console.WriteLine("删除最后一个");
            dlink.DelLast();
            Console.WriteLine("展示最后一个:" + dlink.GetLast());
            dlink.ShowAll();
            Console.ReadKey();

 

相关文章