`

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;
                }
            }
        }
    }
分享到:
评论

相关推荐

    C#实现双向链表C#,.net 链表 双向链表

    这个类是双向链表实现的核心,因为它负责维持链表的结构。 3. **CLists 类**:这是双向链表的主要容器类。它包含对链表头部 (`Head`) 和尾部 (`Tail`) 的引用,以及当前节点 (`curr`) 的引用,用于迭代链表。此外,...

    c#版的双向链表实现

    总结,C#版的双向链表实现涉及到泛型、接口和类设计等多个核心编程概念。通过这些工具,我们可以创建一个灵活、高效且可复用的数据结构,以满足各种程序需求。在实际开发中,理解和掌握这些概念对于提升代码质量至关...

    C#双向链表的实现

    在Ex17_02文件中,我们可以找到上述C#双向链表实现的具体源代码,包括每个方法的完整实现。通过分析和实践这个源码,开发者可以更深入地理解双向链表的工作原理,并掌握在C#中如何有效地操作此类数据结构。 总结来...

    C#,双向链表(Doubly Linked List)归并排序(Merge Sort)算法与源代码

    C#,双向链表(Doubly Linked List)归并排序(Merge Sort)算法与源代码 1 双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一...

    C#实现单向链表C# .net 链表 单向链表

    这里`prev`字段可能是因为后续有双向链表的需求而预留的,但在本例中可以暂时忽略。 #### 三、链表类定义 接下来,我们来看链表类`CList`的定义: ```csharp class CList { public int lstcnt; // 链表长度 ...

    C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码

    C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码。双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始...

    双向链表实现的AOI

    在游戏开发、虚拟环境模拟和实时三维应用中,AOI(Area of Interest...综上所述,通过双向链表实现的AOI系统为大规模实体的范围检测提供了高效且灵活的解决方案,支持动态半径和场景变化,是场景管理中的一个重要工具。

    C#完整的链表应用源码

    本资源提供了C#语言实现的三种不同类型的链表:单链表、双向链表和循环链表的完整源码,这对于理解和实践C#编程中的链表操作极其有价值。 首先,我们来详细探讨单链表。单链表是一种线性数据结构,其中每个节点包含...

    C# 链表实现

    本篇文章将深入探讨C#中的链表实现,包括链表的基本概念、结构以及如何通过`MyLinkedList.cs`和`Node.cs`这两个文件来创建一个自定义链表。 链表是一种线性数据结构,与数组不同,它的元素可以在内存中的任何位置。...

    C#双向链表

    排序 插入 删除 查找 底层代码,内有详细讲解。 初步调试成功

    C#,递归方法实现双向链表(Doubly Linked List)的反转(Reverse)算法与源代码

    C#,递归方法实现双向链表(Doubly Linked List)的反转(Reverse)算法与源代码 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的...

    微软面试题——二元查找树转变成排序的双向链表

    二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4...

    C#双向链表LinkedList排序实现方法

    本文实例讲述了C#双向链表LinkedList排序实现方法。分享给大家供大家参考。具体如下: 1.函数 打印链表函数PrintLinkedList 和 排序函数SortLinkedList 注:下面代码中的链表每项都是double类型,如果换做其他的类型...

    数据结构之链表,C#链表;数据结构之链表,C#链表

    本主题主要关注C#语言中的链表实现。 在C#中,System.Collections.Generic命名空间提供了一个名为LinkedList类,用于实现链表数据结构。LinkedList类包含节点(LinkedListNode)作为链表中的元素,每个节点存储一个...

    C#资料下载

    5. **用C#实现双向链表.txt**:双向链表是一种数据结构,它允许在链表的任一侧进行插入和删除操作。此文件可能包含实现双向链表的C#代码,这对于理解数据结构和算法非常有帮助,也是提升编程能力的关键。 6. **C#...

    C#数据结构之双向链表(DbLinkList)实例详解

    总的来说,`DbLinkList&lt;T&gt;`类提供了一种在C#中实现双向链表的方式,通过`DbNode&lt;T&gt;`类定义节点结构,并通过一系列方法实现链表的基本操作。这种数据结构在实际编程中广泛应用,尤其是在需要高效遍历和修改列表顺序的...

    C#链表操作

    LinkedList类提供了双向链表的实现,允许在两端添加和移除元素。它包含两个节点类:LinkedListNode和LinkedListNode。前者是泛型版本的基类,后者用于存储特定类型的数据。 ### 2. 创建LinkedList 创建一个新的...

    C语言实现的双向动态链表

    在`dplist.h`头文件中,可能会定义一系列操作双向链表的函数,例如: 1. **初始化链表**:创建一个新的空链表。 2. **插入节点**:在链表的开头(头部)、结尾(尾部)或者指定位置插入新的节点。 3. **删除节点**...

    c#链表的合并和反转取中间值操作

    链表分为单向链表和双向链表。在C#中,`LinkedList&lt;T&gt;`类提供了对单向链表的支持。每个节点是`LinkedListNode&lt;T&gt;`类型的实例,包含一个值和对下一个节点的引用。 **链表的合并**: 合并两个链表通常涉及到将一个...

Global site tag (gtag.js) - Google Analytics